M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Algorithms with Python

スプレー木 (splay tree)

[ PrevPage | Python | NextPage ]

はじめに

今回は splay tree (スプレー木、スプレイ木) という二分木を紹介します。今まで説明した AVL 木赤黒木 は二分木をベースにした平衡木で、木のバランスをチェックするための情報を節 (node) に付加し、バランスが崩れたら一定の範囲に収まるように木を修正します。これに対し、1985 年に Sleater と Tarjan が提案したスプレー木はちょっと変わっています。

スプレー木は二分木と同じ構造なので、通常の操作 (探索、挿入、削除など) は二分木と同様に行うことができます。スプレー木の特徴は、このあとに行う操作にあります。スプレー木はアクセスした節を木の根 (ルート) に移動します。この方法を Move to Root といいます。

たとえば線形探索の場合、後ろにあるデータほど探索に時間がかかります。そこで、探索のたびに見つけたデータを少し前に移動します。すると、頻繁に探索されるデータほど前に集まるので、平均探索時間を短くすることができます。この方法を「自己組織化探索 (self-organizing search) 」といいます。特に、見つけたデータを先頭に持っていく方法を Move to Front (MTF) 法といいます。Move to Root は MTF 法の二分木バージョンと考えてください。これにより、頻繁にアクセスする節(データ)ほど木の浅いところに集まるので、平均探索時間は短くなります。

Move to Root は木の回転操作で簡単に実現することができます。しかしながら、この方法では木のバランスを調整することはできません。そこで、スプレー木は節をルートへ移動するときに独自の操作を行います。これを Splay 操作といいます。Splay 操作には zig, zig - zig, zig - zag という 3 つの基本操作があり、木の形状によって適用する操作が決まります。スプレー木の場合、AVL 木や赤黒木のように、木のバランスをチェックするための情報を節に付加する必要はありません。

ただし、スプレー木の場合、他の平衡木のように木の高さが一定の範囲内に収まる保障はありません。データにアクセスする順番によっては、木のバランスが大きく崩れることがあるのです。もしそうなったとしても、その後のデータアクセスによって、スプレー木はバランスを回復することが可能です。

スプレー木は、データ数を N とすると、複数回アクセスしたときの平均実行時間が log N に比例するという面白い性質があります。ようするに、一回あたり長い時間がかかる処理があったとしても、全体で平均してみると O(log N) になるデータ構造というわけです。

O (ビッグ・オー) は O 記法のことで、値の増え方の程度を表します。たとえば、バブルソートのように N2 に比例する場合は O(N2) と書きます。クイックソートなど高速なソートは O(N log N) になります。N に比例する場合は O(N) と書きます。

このように、スプレー木は通常の操作のあとに Splay 操作を行うことで、一時的に木のバランスが崩れることがあっても、トータルとして考えると木のバランスを保つように動作します。このため、スプレー木は「自己調整二分木」と呼ばれています。

今回はスプレー木を簡単に説明して、実際にプログラムを作ってみましょう。スプレー木の詳細は Sleater と Tarjan の論文 "Self adjusting binary search tree" (PDF) をお読みください。なお、本ドキュメントは拙作のページ Common Lisp 入門:番外編「スプレー木」 のプログラムを Python で書き直したものです。内容は重複していますがご了承くださいませ。

●スプレー操作の基本

スプレー木の Splay 操作は、二分木の回転操作が基本になります。回転操作は拙作のページ AVL 木 [1] をお読みください。

Splay 操作は二分木の回転操作を組み合わせたものです。Splay 操作は、次に示す 3 通りの方法があります。

最初に zig から説明します。次の図を見てください。

          Y                X 
        /  \    zig     /  \ 
      X      C ──→ A      Y
    /  \                    /  \ 
  A      B                B      C  


             図 : zig

zig は節 X をルート方向へ一つ移動する操作です。これは二分木の回転操作と全く同じです。

次は zig - zig を説明します。次の図を見てください。


              Z                     Y                    X
            /  \                 /  \                /  \
          Y      D  zig        /      \      zig   A      Y
        /  \       ──→    X          Z   ──→       /  \
      X      C             /  \      /  \            B      Z
    /  \                 A      B  C      D                /  \    
  A      B                                                   C      D  


                                図 : zig - zig

zig - zig は節 X をルート方向へ二つ移動する操作です。X が Z の左部分木にある場合、X < Y < Z であれば zig - zig を適用します。Y < X < Z であれば、次に説明する zig - zag を適用します。zig - zig の特徴は回転操作を適用する順番です。最初に Z を zig で回転し、次に Y を zig で回転します。最初に Y を回転してから Z を回転すると Splay 操作にはなりません。ご注意ください。

最後に zig - zag を説明します。次の図を見てください。

          Z                       Z                     X
        /  \                   /  \                 /  \
      Y      D  zig          X      D  zag        /      \
    /  \       ──→      /  \       ──→    Y          Z
  A      X               Y      C             /  \      /  \
        /  \           /  \                 A      B  C      D  
      B      C       A      B  


                            図:zig - zag

zig - zag も節 X をルート方向へ二つ移動する操作です。X が Z の左部分木にある場合、Y < X < Z であれば zig - zag を適用します。zig - zag は zig - zig とは違って、X の親節 Y を回転してから Z を回転します。zig - zig とは回転操作を適用する順番が異なることに注意してください。

Splay 操作は zig, zig - zig, zig - zag 操作を適用して、アクセスした節をルートまで移動 (Move to Root) する操作です。Move to Root は回転操作だけでも実現することができます。実際、アクセスした節の親節に回転操作を適用していくだけです。けっきょく Splay 操作の場合、zig と zig - zag は回転操作と同じで、異なる操作は zig - zig だけです。次の例を見てください。

                    E                    E                      A
                  /  \                /  \                  /  \
                D                    D                              E
              /  \                /  \                          /  \  
            C          2回転    A            2回転            D
          /  \       ───→ /  \         ───→         /  \  
        B                            C                      C
      /  \                        /  \                  /  \
    A                            B                      B
  /  \                        /  \                  /  \  

           (1)                    (2)                     (3)


                            図 : 回転操作の場合

節 A を回転操作でルートへ移動します。(1) の状態で節 B を右回転し、次に節 C を右回転すると (2) の状態になります。次に節 D を右回転してから節 E を右回転すると、(3) のように節 A をルートへ移動することができます。回転操作の場合、(1) と (3) で木の高さは変化しません。

次は Splay 操作を適用してみましょう。下図を見てください。


                    E                    E                A
                  /  \                /  \            /  \
                D                    D                        D
              /  \                /  \                    /  \
            C         zig-zig    A           zig-zig      /      \
          /  \       ───→ /  \         ───→   B          E
        B                            B                /  \      /  \  
      /  \                        /  \                    C
    A                                    C                /  \
  /  \                                /  \ 

           (1)                    (2)                   (3)


                           図 : Splay 操作の場合

(1) の状態で、部分木 C - B - A に zig - zig を適用すると (2) の状態になります。次に (2) の状態で、部分木 E - D - A に zig - zig を適用すると (3) の状態になり、節 A がルートにきます。(3) は (1) よりも木の高さが 1 つ低くなっていますね。これが Splay 操作の効果です。

●データの探索

それではプログラムを作りましょう。節の定義は二分木と同じです。データを探索する関数 search は次のようになります。

リスト : データの探索

# 定数
LEFT  = 0
RIGHT = 1

# データの探索
def search(node, x):
    path = []
    if node is None: return node, False
    while node is not None:
        if node.data == x:
            return splay(node, path), True
        if x < node.data:
            path.append((node, LEFT))
            node = node.left
        else:
            path.append((node, RIGHT))
            node = node.right
    # 最後にアクセスした節を Splay 操作する
    node, dir = path.pop()
    if len(path) == 0: return node, False
    return splay(node, path), False

たどってきた経路を path に記憶します。path には節と左右どちらの部分木をたどったかを示すデータ (LEFT or RIGTH) をタプルにまとめてセットします。データを見つけたら、節 node と経路 path を関数 splay に渡して Splay 操作を行います。その返り値が新しいルートになります。関数 search は新しいルートと結果を返します。

データが見つからない場合は、最後にアクセスした節をルートに移動します。たとえば、データを x とすると、x が見つからない場合でも、最後にアクセスした節のデータ y は、x より小さなデータの中で一番大きな値か、x よりも大きなデータの中で一番小さな値のどちらかになります。そこで、x が見つからない場合は、この y をルートへ移動することにします。そうすると、データの挿入と削除は、Splay 操作を行ったあとで簡単に実現することができます。

データが見つからない場合、path から最後にアクセスした節を取り出して node にセットします。path が空になった場合、node はルートなのでそのまま返します。そうでなければ、splay を呼び出して Splay 操作を行います。

●Splay 操作

次は Splay 操作を行う関数 splay を作ります。

リスト : Splay 操作 (Bottom-Up)

def splay(node, path):
    while len(path) > 1:
        node, dir = path.pop()
        pnode, pdir = path.pop()
        if dir == pdir:
            # zig-zig
            if dir == LEFT:
                pnode = rotate_right(pnode)
                node = rotate_right(pnode)
            else:
                pnode = rotate_left(pnode)
                node = rotate_left(pnode)
        else:
            # zig-zag
            if dir == LEFT:
                pnode.right = rotate_right(node)
                node = rotate_left(pnode)
            else:
                pnode.left = rotate_left(node)
                node = rotate_right(pnode)
        # 子の付け替え
        if len(path) == 0: return node
        gnode, gdir = path[len(path) - 1]
        if gdir == LEFT:
            gnode.left = node
        else:
            gnode.right = node
    # zig
    if len(path) == 0: return node
    node, dir = path.pop()
    if dir == LEFT:
        node = rotate_right(node)
    else:
        node = rotate_left(node)
    return node

プログラムリストは少し長いですが、処理内容はそれほど難しくありません。path からデータを 2 つ取り出して、node, dir と pnode, pdir にセットします。dir と pdir が等しい場合は zig - zig を適用し、そうでなければ zig - zag を適用します。zig - zig の場合、dir が LEFT の場合は、pnode を左回転して、その返り値を再び左回転します。dir が RIGHT の場合は回転操作を右にするだけです。

zig - zag の場合は node, pnode の順番で回転操作を行います。dir が LEFT の場合、node は pnode の右の子になります。node を右回転した結果を pnode.right にセットします。それから pnode を左回転します。dir が RIGHT の場合は、node を左回転した結果を pnode.left にセットしてから、pnode を右回転します。これらの回転操作の結果は node にセットしておきます。

回転操作が終わったら子の付け替えを行います。path にデータがない場合は、ルートに到達したので node をそのまま返します。そうでなければ、path から親節 gnode, gdir を取り出して、その gdir 側の子を node に書き換えます。

最後に zig 操作を行います。path にデータがない場合は node をそのまま返します。そうでなければ、path からデータを取り出して、node, dir にセットします。dir が LEFT であれば右回転、RIGHT であれば左回転します。あとは、その結果を return で返すだけです。

●データの挿入

次はデータを挿入する関数 insert を作ります。

リスト : データの挿入

def insert(node, x):
    if node is None: return Node(x)
    node, result = search(node, x)
    if result: return node
    new_node = Node(x)
    if x < node.data:
        new_node.right = node
        new_node.left = node.left
        node.left = None
    else:
        new_node.left = node
        new_node.right = node.right
        node.right = None
    return new_node

node が None の場合は空の木なので、新しい節を Node(x) で作って返します。そうでなければ、関数 search を呼び出して x を探索します。result が True の場合は x と同じデータがあるので、search の返り値 node をそのまま返します。search は Splay 操作を行っていることに注意してください。

同じデータがない場合は、x をルートに挿入します。まず、新しい節を Node(x) で作成して new_node にセットします。x が node.data よりも小さい場合は、new_node の右の子に node をセットします。node の左部分木は x よりも小さなデータしかないので、node の左部分木を new_node の左の子にセットし、node の左の子を None に書き換えます。これで node の左部分木の高さを 1 つ低くすることができます。

逆に、x が node.data よりも大きい場合は、new_node の左の子に node をセットします。node の右部分木は x よりも大きなデータしかないので、node の右部分木を new_node の右の子にセットし、node の右の子を None に書き換えます。これで node の右部分木の高さを 1 つ低くすることができます。最後に new_node を返します。

●データの削除

最後にデータを削除する関数 delete を作ります

リスト : データの削除

def delete(node, x):
    if node is None: return node, False
    node, result = search(node, x)
    if not result: return node, False
    # データあり
    if node.left is None:
        return node.right, True
    elif node.right is None:
        return node.left, True
    else:
        node1, result = search(node.left, x)
        node1.right = node.right
        return node1, True

引数 node が None の場合、スプレー木は空なので None, False を返します。そうでなければ、関数 search でデータ x を探索します。このとき Splay 操作が行われます。結果 result が False の場合、スプレー木に x はないので node, False を返します。そうでなければ node を削除します。

データを削除するとき、node の子が 0 または 1 個の場合は簡単です。右の子がない場合は左の子を返し、左の子がない場合は右の子を返すだけです。子がない場合は None が返されるので、スプレー木は空になります。

二分木の場合、子が 2 つあるデータを削除する処理はちょっと複雑になりますが、スプレー木の場合は Splay 操作を行うと簡単に実現できます。node の左部分木に対し、x を与えて Splay 操作 (search) を行います。node の左部分木は x よりも小さなデータしかありません。したがって、search(node.left, x) を実行すると、返り値 node1 は左部分木の中で一番大きなデータになり、node1 の右部分木は空の木になります。あとは、node1 の右の子に node の右の子をセットして node1 を返すだけです。

●簡単なテスト

それでは、ここで簡単なテストを行ってみましょう。テストプログラムは次のようになります。

リスト : スプレー木の簡単なテスト

# coding: utf-8
import snode0

# スプレー木の表示
def print_splay_tree(node, x):
    if node is not None:
        print_splay_tree(node.left, x + 1)
        print "    " * x, node.data
        print_splay_tree(node.right, x + 1)

# テスト
a = None
buff = range(8) # [random.randint(0, 100) for _ in xrange(8)]
for x in buff:
    print 'insert', x
    a = insert(a, x)
    print_splay_tree(a, 0)
for x in buff:
    print 'search', x,
    a, r = search(a, x)
    print r
    print_splay_tree(a, 0)
for x in buff:
    print 'delete', x
    a, r = delete(a, x)
    print r
    print_splay_tree(a, 0)

実行結果は次のようになります。

insert 0
 0
insert 1
     0
 1
insert 2
         0
     1
 2
insert 3
             0
         1
     2
 3
insert 4
                 0
             1
         2
     3
 4
insert 5
                     0
                 1
             2
         3
     4
 5
insert 6
                         0
                     1
                 2
             3
         4
     5
 6
insert 7
                             0
                         1
                     2
                 3
             4
         5
     6
 7

スプレー木の場合、ソート済みのデータを順番に挿入すると、データは左右に均等に分配されず偏った木になってしまいます。ここで、他の操作を行うと、スプレー木はバランスを取るように働きます。データの探索を行うと、スプレー木の状態は次のように変化していきます。

search 0 True
 0
                 1
                     2
             3
                 4
         5
             6
     7
search 1 True
     0
 1
             2
         3
                 4
             5
                 6
     7
search 2 True
         0
     1
 2
     3
                 4
             5
                 6
         7
search 3 True
             0
         1
     2
 3
             4
         5
             6
     7
search 4 True
                 0
             1
         2
     3
 4
     5
             6
         7
search 5 True
                     0
                 1
             2
         3
     4
 5
         6
     7
search 6 True
                         0
                     1
                 2
             3
         4
     5
 6
     7
search 7 True
                             0
                         1
                     2
                 3
             4
         5
     6
 7

Splay 操作を行うことでスプレー木の状態が変化していく様子がよくわかると思います。今回はデータを挿入した順番で探索を行ったので、最後はバランスが崩れた元の状態に戻ってしまいました。このように、一時的に木のバランスが崩れることがあっても、トータルとして考えると木のバランスを保つように動作するのがスプレー木の特徴です。ただし、一時的に偏った状態になることがあるので、木を巡回するときに再帰呼び出しを使う場合は注意が必要です

データの削除は次のようになります。

delete 0
True
             1
                 2
         3
             4
     5
         6
 7
delete 1
True
         2
     3
             4
         5
             6
 7
delete 2
True
 3
             4
         5
             6
     7
delete 3
True
         4
     5
         6
 7
delete 4
True
 5
         6
     7
delete 5
True
     6
 7
delete 6
True
 7
delete 7
True

データの削除でも Splay 操作を行っているので、データを削除するたびにスプレー木の状態は変化します。正常に動作していますね。

次は、Top-Down Splay について説明します。


●プログラムリスト1

# coding: utf-8
#
# snode0.py : スプレー木 操作関数 (Bottom-Up)
#
#             Copyright (C) 2007 Makoto Hiroi
#

# 定数
LEFT  = 0
RIGHT = 1

# 節
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# 右回転
def rotate_right(node):
    lnode = node.left
    node.left = lnode.right
    lnode.right = node
    return lnode

# 左回転
def rotate_left(node):
    rnode = node.right
    node.right = rnode.left
    rnode.left = node
    return rnode

# Splay 操作 (Bottom-Up)
def splay(node, path):
    while len(path) > 1:
        node, dir = path.pop()
        pnode, pdir = path.pop()
        if dir == pdir:
            # zig-zig
            if dir == LEFT:
                pnode = rotate_right(pnode)
                node = rotate_right(pnode)
            else:
                pnode = rotate_left(pnode)
                node = rotate_left(pnode)
        else:
            # zig-zag
            if dir == LEFT:
                pnode.right = rotate_right(node)
                node = rotate_left(pnode)
            else:
                pnode.left = rotate_left(node)
                node = rotate_right(pnode)
        # 子の付け替え
        if len(path) == 0: return node
        gnode, gdir = path[len(path) - 1]
        if gdir == LEFT:
            gnode.left = node
        else:
            gnode.right = node
    # zig
    if len(path) == 0: return node
    node, dir = path.pop()
    if dir == LEFT:
        node = rotate_right(node)
    else:
        node = rotate_left(node)
    return node


# データの探索
def search(node, x):
    path = []
    if node is None: return node, False
    while node is not None:
        if node.data == x:
            return splay(node, path), True
        if x < node.data:
            path.append((node, LEFT))
            node = node.left
        else:
            path.append((node, RIGHT))
            node = node.right
    # 最後にアクセスした節を Splay 操作する
    node, dir = path.pop()
    if len(path) == 0: return node, False
    return splay(node, path), False


# データの挿入
def insert(node, x):
    if node is None: return Node(x)
    node, result = search(node, x)
    if result: return node
    new_node = Node(x)
    if x < node.data:
        new_node.right = node
        new_node.left = node.left
        node.left = None
    else:
        new_node.left = node
        new_node.right = node.right
        node.right = None
    return new_node


# データの削除
def delete(node, x):
    if node is None: return node, False
    node, result = search(node, x)
    if not result: return node, False
    # データあり
    if node.left is None:
        return node.right, True
    elif node.right is None:
        return node.left, True
    else:
        node1, result = search(node.left, x)
        node1.right = node.right
        return node1, True


# 巡回 (とりあえず再帰呼び出しで実装)
def traverse(node):
    if node is not None:
        for x in traverse(node.left):
            yield x
        yield node.data
        for x in traverse(node.right):
            yield x

●Top-Down Splay

ところで、今までは移動する節からルート方向へ木をたどって zig, zig - zig, zig - zag 操作を適用する、いわゆるボトムアップで Splay 操作を行っています。これに対し、ルートから木をたどっいくトップダウンでも Splay 操作を行うことができます。これを Top-Down Splay といいます。

Top-Down Splay の基本的な考え方は簡単です。トップダウンでルートから節 X までたどるとき、X よりも大きい節は X の右部分木になります。逆に、X よりも小さな節は左部分木になります。そこで、木をたどりながら左右の部分木を作成することにします。そして、節 X に到達したら X の子を部分木に挿入し、その部分木を節 X につなげればいいわけです。

それでは zig 操作から説明しましょう。次の図を見てください。

          Y                               W
        /  \              X           /  \  
      X      C ──→   /  \       Y 
    /  \              A      B   /  \
  A      B                               C


                図 : zig (1)

左右の部分木を格納する作業用の節 W を用意します。W の左の子には X よりも大きなデータを、右の子には X よりも小さなデータを追加します。このようにすると、部分木の作成が簡単になります。

たとえば、節 Y の左部分木をたどる場合、左部分木には Y より大きなデータはありません。したがって、次のデータを追加するとき、X よりも小さなデータは必ず Y の左の子になります。つまり、左部分木をたどる場合は節を W の左部分木に追加し、逆に右部分木をたどる場合は W の右部分木に節を追加すればいいわけです。

上図の場合、Y を W の左の子にセットして、節 X に到達します。次は、X の子を W の部分木に追加します。

                   W                  X
    X           /  \              /  \
  /  \       Y      A  ──→  A      Y
             /  \                      /  \
           B      C                  B      C  


                図 : zig (2)

X の左の子 A は X よりも小さいので W の右部分木に追加します。上図の場合、W の右の子に A をセットします。X よりも大きい右の子 B は、W の左部分木である Y の左の子にセットします。あとは、W の左部分木を X の右の子に、W の右部分木を X の左の子にセットすればいいわけです。

次は zig - zig 操作を説明します。下図を見てください。

              Z                     Y                    X           W
            /  \                 /  \                /  \       /  \
          Y      D  zig        /      \            A      B   Y
        /  \       ──→    X          Z   ──→            /  \
      X      C             /  \      /  \                         Z
    /  \                 A      B  C      D                     /  \    
  A      B                                                        C      D  


                            図 : zig - zig (1)

zig - zig 操作の場合、最初に節 Z を右回転するところは今までと同じです。それから、節 Y を W の左部分木にセットします。これで節 X に到達したので、X の子を W に追加します。これは zig 操作と同じです。次の図を見てください。

    X           W                X
  /  \       /  \            /  \
             Y      A ──→ A      Y
           /  \                    /  \
         B      Z                B      Z
               /  \                    /  \    
             C      D                C      D  


            図 : zig - zig (2)

X の左の子 A を W の右の子に、X の右の子 B を Y の左の子にセットします。最後に、W の左部分木を X の右の子に、W の右部分木を X の左の子にセットします。

次は zig - zag 操作を説明します。下図を見てください。

          Z                Y                W
        /  \            /  \            /  \  
      Y      D        A      X        Z
    /  \       ──→       /  \    /  \
  A      X                B      C        D
        /  \
      B      C


                図 : zig - zag (1)

zig - zag 操作の場合、回転操作が不要なので zig - zig 操作よりも簡単です。節 Y は節 Z の左部分木なので、Z を W の左部分木に追加します。

      Y                W              X             W
    /  \            /  \          /  \         /  \ 
  A      X        Z       ──→ B      C     /      \ 
        /  \    /  \                         Z          Y
      B      C        D                     /  \      /  \ 
                                                     D  A


                       図 : zig - zag (2)

次に、節 X は Y の右部分木なので、Y を W の右部分木に追加します。これで X に到達したので、X の子を W の部分木に追加します。

      X             W                          X
    /  \         /  \                      /  \ 
                 /      \      ──→      /      \ 
               Z          Y              Y          Z
             /  \      /  \          /  \      /  \ 
           C      D  A      B       A     B  C      D  


                       図 : zig - zag (3)

X の左の子 B は W の右部分木である Y の右の子に、X の右の子 C は W の左部分木である Z の左の子にセットします。あとは、W の左部分木を X の右の子に、W の右部分木を X の左の子にセットするだけです。

このように、トップダウンでも Splay 操作を実現することができます。それでは、Top-Down Splay の簡単な例を示しましょう。次の図を見てください。


                    E                    C          W
                  /  \                /  \      /  \
                D                    B          D
              /  \                /  \      /  \
            C         zig-zig    A                  E
          /  \       ───→ /  \              /  \  
        B
      /  \
    A
  /  \


                   図 : splay 操作の場合 (1)

節 A をルートに移動します。最初は部分木 E - D - C に zig - zig 操作を適用します。すると、節 W の左の子に節 D がセットされます。次に、部分木 C - B - A に zig - zig 操作を適用します。次の図を見てください。


           C        W                           W            A
         /  \    /  \ zig-zig    A         /  \        /  \
       B        D       ───→ /  \     D        ─→        D
     /  \    /  \                       /  \                /  \
   A                E                   /      \            /      \
 /  \            /  \               B          E        B          E
                                      /  \      /  \    /  \      /  \  
                                            C                    C
                                          /  \                /  \


                    図 : splay 操作の場合 (2) 

節 D の左の子に節 B がセットされ、節 A に到達しました。あとは、A の子を W の部分木に追加して、W の左部分木を A の右の子に、W の右部分木を A の左の子にセットするだけです。

●Top-Down Splay のプログラム

それでは Top-Down Splay のプログラムを作りましょう。次のリストを見てください。

リスト : Top-Down Splay

# Splay 作業用セル
wnode = Node(None)

# Top-Down Splay
def splay(node, x):
    rnode = wnode    # rnode は右部分木になる節を追加する
    lnode = wnode    # lnode は左部分木になる節を追加する
    while True:
        if node.data == x: break
        elif x < node.data:
            # node は右部分木になる
            if node.left is None: break
            if x < node.left.data:
                # 右回転 (zig - zig)
                node = rotate_right(node)
                if node.left is None: break
            rnode.left = node
            rnode = node
            node = node.left
        else:
            # node は左部分木になる
            if node.right is None: break
            if x > node.right.data:
                # 左回転 (zig - zig)
                node = rotate_left(node)
                if node.right is None: break
            lnode.right = node
            lnode = node
            node = node.right
    #
    rnode.left = node.right
    lnode.right = node.left
    node.left = wnode.right
    node.right = wnode.left
    return node

関数 splay は Top-Down Splay 操作を行います。引数 node にはスプレー木のルートを渡します。x はルートへ移動するデータです。wnode が部分木を格納する節、rnode が右部分木になる節、lnode が左部分木になる節を表します。rnode と lnode は wnode に初期化します。

x を見つけたら break で while ループを脱出します。x より大きな節 (node) は rnode の左の子にセットし、rnode を node に書き換えます。節 node の左の子がない場合は、スプレー木に x はありません。そこで while ループを脱出して最後にアクセスした node をルートへ移動します。左の子がある場合は zig - zig 操作を行うかチェックし、そうであれば木を右回転します。このとき、もう一度 node に左の子があるかチェックすることに注意してください。

x より小さな節は lnode の右の子にセットし、lnode を node に書き換えます。節 node の右の子がない場合は、そこで while ループを脱出して node をルートへ移動します。そして、zig - zig 操作を行うかチェックし、そうであれば木を左回転します。このとき、もう一度 node に右の子があるかチェックすることに注意してください。

while ループを脱出したら、node の左右の子を rnode と lnode にセットします。そして、wnode の右部分木を node の左の子に、wnode の左部分木を node の右の子にセットしてから node を返します。

関数 splay を使うと、データの探索、挿入、削除の各処理は簡単に作成できます。データの探索は、splay を呼び出したあと、ルートにあるデータと比較します。データの挿入と削除は、最初に作成したボトムアップのプログラムとほとんど同じです。詳細は プログラムリスト2 をお読みください。

●簡単なテスト

それでは、ここで簡単なテストを行ってみましょう。テストプログラムは次のようになります。

リスト : スプレー木の簡単なテスト

# coding: utf-8
import snode

# スプレー木の表示
def print_splay_tree(node, x):
    if node is not None:
        print_splay_tree(node.left, x + 1)
        print "    " * x, node.data
        print_splay_tree(node.right, x + 1)

# テスト
a = None
buff = [random.randint(0, 100) for _ in xrange(8)]
for x in buff:
    print 'insert', x
    a = insert(a, x)
    print_splay_tree(a, 0)
for x in buff:
    print 'search', x,
    a, r = search(a, x)
    print r
    print_splay_tree(a, 0)
for x in buff:
    print 'delete', x
    a, r = delete(a, x)
    print r
    print_splay_tree(a, 0)

実行結果は次のようになります。

insert 53
 53
insert 30
 30
     53
insert 0
 0
     30
         53
insert 16
     0
 16
     30
         53
insert 38
             0
         16
     30
 38
     53
insert 3
     0
 3
         16
     30
         38
             53
insert 57
                 0
             3
                 16
         30
             38
     53
 57
insert 94
                     0
                 3
                     16
             30
                 38
         53
     57
 94
search 53 True
             0
         3
             16
     30
         38
 53
     57
         94
search 30 True
         0
     3
         16
 30
         38
     53
         57
             94
search 0 True
 0
     3
             16
         30
                 38
             53
                 57
                     94
search 16 True
         0
     3
 16
     30
             38
         53
             57
                 94
search 38 True
                 0
             3
         16
     30
 38
     53
         57
             94
search 3 True
     0
 3
         16
     30
         38
             53
                 57
                     94
search 57 True
             0
         3
             16
     30
             38
         53
 57
     94
search 94 True
                 0
             3
                 16
         30
                 38
             53
     57
 94
delete 53
True
             0
         3
             16
     30
 38
     57
         94
delete 30
True
         0
     3
 16
     38
         57
             94
delete 0
True
 3
     16
         38
             57
                 94
delete 16
True
 3
     38
         57
             94
delete 38
True
 3
     57
         94
delete 3
True
 57
     94
delete 57
True
 94
delete 94
True

正常に動作していますね。

●Splaytree クラスの作成

最後にスプレー木を表すクラスを作成します。次のリストを見てください。

# coding: utf-8
#
# splay.py : スプレイ木
#
#            Copyright (C) 2007 Makoto Hiroi
#
import snode

class Splaytree:
    def __init__(self):
        self.root = None

    # 探索
    def search(self, x):
        self.root, result = snode.search(self.root, x)
        return result

    # 挿入
    def insert(self, x):
        self.root = snode.insert(self.root, x)

    # 削除
    def delete(self, x):
        self.root, result = snode.delete(self.root, x)
        return result

    # 巡回
    def traverse(self):
        for x in snode.traverse(self.root):
            yield x

    # 表示
    def __str__(self):
        if self.root is None: return 'Splaytree()'
        buff = 'Splaytree('
        for x in snode.traverse(self.root):
            buff += '%s, ' % x
        buff = buff.rstrip(',  ')
        buff += ')'
        return buff

# テスト
if __name__ == '__main__':
    import random
    tree = Splaytree()
    data = [random.randint(0, 100) for x in range(10)]
    print data
    print tree
    for x in data: tree.insert(x)
    print tree
    for x in data:
        print 'search', x, tree.search(x)
        print 'delete', x
        tree.delete(x)
        print 'search', x, tree.search(x)
        print tree

クラス名は Splaytree としました。Splaytree のメソッドはモジュール snode の操作関数を呼び出すだけです。とくに難しいところはないでしょう。ただし、木の表示と巡回は再帰呼び出しを使っているので注意してください。

それでは、テストの実行結果を示します。

[46, 34, 38, 75, 40, 19, 57, 60, 53, 70]
Splaytree()
Splaytree(19, 34, 38, 40, 46, 53, 57, 60, 70, 75)
search 46 True
delete 46
search 46 False
Splaytree(19, 34, 38, 40, 53, 57, 60, 70, 75)
search 34 True
delete 34
search 34 False
Splaytree(19, 38, 40, 53, 57, 60, 70, 75)
search 38 True
delete 38
search 38 False
Splaytree(19, 40, 53, 57, 60, 70, 75)
search 75 True
delete 75
search 75 False
Splaytree(19, 40, 53, 57, 60, 70)
search 40 True
delete 40
search 40 False
Splaytree(19, 53, 57, 60, 70)
search 19 True
delete 19
search 19 False
Splaytree(53, 57, 60, 70)
search 57 True
delete 57
search 57 False
Splaytree(53, 60, 70)
search 60 True
delete 60
search 60 False
Splaytree(53, 70)
search 53 True
delete 53
search 53 False
Splaytree(70)
search 70 True
delete 70
search 70 False
Splaytree()

●スプレー木の評価

それでは、ボトムアップ版とトップダウン版の性能を比較してみましょう。次のリストを見てください。

リスト : スプレー木のテスト

import splay0    # Bottom-Up
import splay     # Top-Down
import time, random

def insert_test(tree, buff):
    s = time.clock()
    for x in buff:
        tree.insert(x)
    e = time.clock()
    return e - s

def search_test(tree, buff):
    s = time.clock()
    for x in buff:
        tree.search(x)
    e = time.clock()
    return e - s

def delete_test(tree, buff):
    s = time.clock()
    for x in buff:
        tree.delete(x)
    e = time.clock()
    return e - s

for x in [1000, 2000, 4000, 8000, 16000]:
    buff = [random.randint(0, 100000) for _ in xrange(x)]
#    buff.sort()
    print x,
    for tree in [splay0.Spalytree, splay.Splaytree]:
        a = tree()
        print '%.3f' % insert_test(a, buff),
        print '%.3f' % search_test(a, buff),
        print '%.3f' % delete_test(a, buff),
    print

データは乱数で生成します。そして、木にデータを挿入する (insert_test)、データを探索する (search_test)、データを削除する (delete_test) 時間を計測します。実行結果は次のようになります。

        表 : 実行結果 (単位 : 秒)

      :      Bottom-Up      :      Top-Down
 個数 : 挿入   探索   削除  : 挿入   探索   削除
-------------------------------------------------
 1000 : 0.051  0.044  0.052 : 0.023  0.020  0.024
 2000 : 0.112  0.097  0.117 : 0.050  0.044  0.054
 4000 : 0.243  0.214  0.261 : 0.112  0.096  0.118
 8000 : 0.543  0.470  0.579 : 0.251  0.213  0.260
16000 : 1.204  1.029  1.289 : 0.562  0.476  0.586

実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2

Bottom-Up 版のプログラムはとても遅くなりました。スプレー木の場合、Top-Down Splay で実装したほうがよいでしょう。その Top-Down 版にしても、実行時間は他の平衡木よりも遅くなりました。スプレー木の場合、頻繁にアクセスするデータほど木の浅いところに集まります。今回のテストのように、データを一回ずつしか探索しない場合、スプレー木はその効果を十分に発揮できないと思われます。スプレー木には不利なテストだったようです。

次はソート済みデータで試してみましょう。実行結果は次のようになりました。

        表 : 実行結果 (単位 : 秒)
             (ソート済みデータ)

      :      Bottom-Up      :      Top-Down
 個数 : 挿入   探索   削除  : 挿入   探索   削除
-------------------------------------------------
 1000 : 0.008  0.017  0.015 : 0.007  0.009  0.009
 2000 : 0.018  0.034  0.030 : 0.014  0.019  0.017
 4000 : 0.033  0.069  0.063 : 0.030  0.038  0.035
 8000 : 0.068  0.146  0.127 : 0.061  0.078  0.072
16000 : 0.152  0.292  0.262 : 0.124  0.159  0.148

実行環境 : Windows XP, celeron 1.40 GHz, Python 2.4.2

どちらのプログラムも高速になりました。Top-Down 版の場合、他の平衡木と比べてもデータの挿入と削除は高速です。前回取り上げた Treap よりも速くなるとは驚きました。

なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。


●プログラムリスト2

# coding: utf-8
#
# snode.py : スプレー木 操作関数 (Top-Down Splay)
#
#            Copyright (C) 2007 Makoto Hiroi
#

# 節
class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

# 右回転
def rotate_right(node):
    lnode = node.left
    node.left = lnode.right
    lnode.right = node
    return lnode

# 左回転
def rotate_left(node):
    rnode = node.right
    node.right = rnode.left
    rnode.left = node
    return rnode

# Splay 作業用セル
wnode = Node(None)

# Top-Down Splay
def splay(node, x):
    rnode = wnode    # rnode は右部分木になる節を追加する
    lnode = wnode    # lnode は左部分木になる節を追加する
    while True:
        if node.data == x: break
        elif x < node.data:
            # node は右部分木になる
            if node.left is None: break
            if x < node.left.data:
                # 右回転 (zig - zig)
                node = rotate_right(node)
                if node.left is None: break
            rnode.left = node
            rnode = node
            node = node.left
        else:
            # node は左部分木になる
            if node.right is None: break
            if x > node.right.data:
                # 左回転 (zig - zig)
                node = rotate_left(node)
                if node.right is None: break
            lnode.right = node
            lnode = node
            node = node.right
    #
    rnode.left = node.right
    lnode.right = node.left
    node.left = wnode.right
    node.right = wnode.left
    return node


# データの挿入
def insert(node, x):
    if node is None: return Node(x)
    node = splay(node, x)
    if x == node.data: return node
    new_node = Node(x)
    if x < node.data:
        new_node.right = node
        new_node.left = node.left
        node.left = None
    else:
        new_node.left = node
        new_node.right = node.right
        node.right = None
    return new_node


# データの探索
def search(node, x):
    if node is None: return node, False
    node = splay(node, x)
    return node, node.data == x


# データの削除
def delete(node, x):
    if node is None: return node, False
    node = splay(node, x)
    if node.data != x: return node, False
    # データあり
    if node.left is None:
        return node.right, True
    elif node.right is None:
        return node.left, True
    else:
        node1 = splay(node.left, x)
        node1.right = node.right
        return node1, True


# 巡回 (とりあえず再帰呼び出しで実装)
def traverse(node):
    if node is not None:
        for x in traverse(node.left):
            yield x
        yield node.data
        for x in traverse(node.right):
            yield x

Copyright (C) 2007 Makoto Hiroi
All rights reserved.

[ PrevPage | Python | NextPage ]