はじめに
AA 木 (Arne Andersson tree) は 1993 年に Arne Andersson 氏が発表した平衡木です。拙作のページ 二分木とヒープ で説明したように、二分木は左右の部分木のバランスが崩れると性能が劣化する欠点があります。極端な例ですが、ソートされたデータを二分木に挿入していくと、データは右側の部分木にしか挿入されず、連結リストと同じ線形探索になってしまいます。
これを補うために、木のバランスを一定の範囲に収める平衡木が考案されています。有名なところでは、二分木をベースにした AVL 木、赤黒木、AA 木などや、多分木をベースにした 2-3 木、B 木、B* 木などがあります。赤黒木は 2-3-4 木の動作を二分木で実現したものですが、そのプログラムはとても複雑になりす。
これに対して、AA 木は 2-3 木の動作を二分木で実現したものですが、とても簡単にプログラムを実装できる、という特徴があります。なお、赤黒木は 2008 年に Robert Sedgewick 氏が "Left-Leaning Red Black Trees" という改良版を発表しています。この方法を使うと、赤黒木も簡単にプログラムすることができるようです。
今回は AA 木について簡単に説明します。詳細は Arne Andersson 氏の論文 "Balanced Search Trees Made Simple" をお読みください。
●AA 木とは？
AA 木の基本を説明するため、赤黒木と同様に節を赤と黒で塗り分けてみましょう。すると、AA 木は次の条件を満たす「二分木」になります。
- 各節は赤または黒に区分される。
- ある節が赤ならばその子は必ず黒である。
- 黒節の左の子の色は赤にならない。右の子の色は赤でも黒でもよい。
- ルートから葉までの黒節の個数を「黒高さ」という。AA 木はどの経路でも黒高さが同じになる。
- ルートの節は黒である。
赤黒木との違いは 3 番目の「黒節の左の子の色は赤にならない」だけです。赤黒木は「2-3-4 木」という多分木の動作を二分木で実現したものです。2-3-4 木は最小で 2 つ、最大で 4 つの子を持ちます。2-3-4 木の節を赤節と黒節で表したものが赤黒木です。対応関係を図で表すと、次のようになります。
AA 木は 2-3 木の動作を二分木で実現したものなので、上図 (c) の状態は存在しません。そして、AA 木は子を 3 つ持つ (b) の状態を (b-1) だけに限定します。このことを 3 番目の条件「黒節の左の子の色は赤にならない」で表しています。このように条件を限定することで、プログラムの実装が簡単になるのです。
ちなみに、Robert Sedgewick 氏の "Left-Leaning Red Black Trees" では、(b) の状態を (b-2) だけに限定することにより、赤黒木を簡単にプログラムできるように改良しています。
●木のレベル
Arne Andersson の論文 "Balanced Search Trees Made Simple" では、節を赤と黒に塗り分けるのではなく、木のレベル (黒高さ) を使った実装方法が示されています。AA 木は葉のレベルを 1 とし、赤節のレベルは親の黒節と同じに値になります。次の図を見てください。
黒節の右隣に赤節を書くとわかりやすいと思います。黒節と赤節で 2-3 木の一つの節を表しているので、2 つの節のレベルは同じ値になるわけです。逆にいうと、黒節の子のレベルが親と同じ値であれば、その節の色は「赤」と判断できるわけです。したがって、左の子のレベルは親節よりも必ず一つ少なくなり、右の子は親節のレベルと同じか一つ少なくなります。
●データの挿入
次は、データの挿入について詳しく説明します。赤黒木と比較した方がわかりやすいと思うので、AA 木の節は赤と黒で塗り分けて示すことにします。新しいデータは赤節として AA 木に挿入します。これは赤黒木と同じです。親が黒節で左の子に挿入する場合は簡単です。AA 木の条件を満たしているので、そのまま挿入するだけです。
問題は黒節の左の子に挿入する場合と親が赤節の場合です。各々の場合について詳しく説明しましょう。最初は黒節 A に赤節 B を挿入する場合です。次の図を見てください。
数字はレベルを表します。AA 木の場合、節 A と B のレベルが同じことから、赤節が挿入されたことがわかります。この場合、部分木 A を右回転します。AA 木ではこの操作を skew といいます。A はレベルが同じまま B の右の子になるので赤節となり、AA 木の条件を満たします。
次は A に右の子 B がある場合です。
A の左に赤節 C を挿入します。すると、2-3-4 木で 4 つの子を持つ節と同じ状態になります。最初に部分木 A を skew するところは同じです。次に、節 C と節 B のレベルを比較します。レベルが同じなので、赤節が 2 つ続いていることがわかります。この状態も 2-3-4 木で 4 つの子を持つ節と考えることができます。そこで、部分木 C を左回転して、A のレベルを +1 します。AA 木ではこの操作を split といいます。
(a) の場合、A は親節 P の右の子になりレベルも同じ (赤節) なので AA 木の条件を満たします。(b) の場合、P の左の子が赤節になるので、P で木のバランスを修正します。なお、この処理は回転操作をせずに A のレベルを +1 するだけでいいのですが、オリジナルのプログラムでは skew と split を連続で適用することにより、場合分けを省いてプログラムを簡単にしています。
次は赤節の右にデータを挿入する場合です。
赤節 B の右に節 C を挿入します。B と C は同じレベルなので、ここでは修正処理を行いません。次に、B の親節 A を調べます。A と C は同じレベルなので、赤節が 2 つ続いているとがわかります。部分木 A を split で左回転します。(a) はこれで AA 木の条件を満たしますが、(b) は親節 P で修正処理を行います。
次は赤節 B の左に節 C を挿入する場合です。
まず赤節 C を挿入した節 B を skew で右回転します。次に、その親節 A を調べます。すると、A と B のレベルが同じなので、split で左回転します。(a) の場合、これで AA 木の条件を満たしますが、(b) の場合は親節 P で修正が必要になります。
データ挿入のパターンはこれで全部です。このように、AA 木はデータを挿入した部分木の親節に skew と split を連続で適用していくことで、木のバランスを修正することができます。
●AA 木のプログラム
それでは、AA 木にデータを挿入するプログラムを Python で作ってみましょう。最初に、節を表すクラスを定義します。
リスト : 節と終端の定義
# 終端
null = None
# 節
class Node:
def __init__(self, x):
self.data = x
self.height = 1
self.left = null
self.right = null
# 終端の設定
def make_null():
global null
if null is None:
null = Node(None)
null.height = 0
null.left = null
null.right = null
return null
クラス名は Node としました。インスタンス変数 height には木のレベルをセットします。関数 make_null() は終端オブジェクトを生成して返します。終端オブジェクトはグローバル変数 null に格納します。null が None の場合は終端オブジェクトがまだないので、Node() で終端オブジェクトを生成します。節のレベルは 0 で、left と right には null をセットしておきます。
●データの挿入処理
次はデータを挿入する関数 insert() を作成します。プログラムは次のようになります。
リスト : データの挿入
# 右回転による修正
def skew(node):
if node.left.height == node.height:
node = rotate_right(node)
return node
# 左回転による修正
def split(node):
if node.height == node.right.right.height:
node = rotate_left(node)
node.height += 1
return node
# データの挿入
def insert(node, x):
if node is null: return Node(x)
elif x == node.data: return node
elif x < node.data:
node.left = insert(node.left, x)
else:
node.right = insert(node.right, x)
return split(skew(node))
関数 skew() は節 node と node.left のレベルが同じ場合、node を rotate_right() で右回転してバランスを修正します。関数 split() は節 node と node.right.right のレベルが同じ場合、node を rotate_left() で左回転して、その返り値の node のレベルを +1 します。
insert() は AA 木のルートと挿入するデータを受け取り、データを挿入したあとの木を返します。これは二分木の場合と同じです。挿入処理も二分木と同じですが、node を返すときに skew() と split() を適用します。これでたどってきた節に skew() と split() が適用され、木のバランスを修正することができます。
データの挿入処理はこれだけです。驚くほど簡単ですね。
●データ挿入のテスト
それでは、ここでデータ挿入のテストを行ってみましょう。テストプログラムは次のようになります。
リスト : データ挿入の簡単なテスト
import aanode
# 表示
def print_node(node, x):
if node is not aanode.null:
print_node(node.left, x)
print(' ' * (x - node.height), node.data)
print_node(node.right, x)
root = aanode.make_null()
buff = range(8)
for x in buff:
root = aanode.insert(root, x)
print_node(root, root.height)
print('-----')
print_node は AA 木を表示する関数です。引数 x にはルートのレベルを渡します。終端は None ではなく null なので、node と aanode.null を比較していることに注意してください。0 から 7 までの整数値を順番に AA 木に挿入します。実行結果は次のようになります。
0
-----
0
1
-----
0
1
2
-----
0
1
2
3
-----
0
1
2
3
4
-----
0
1
2
3
4
5
-----
0
1
2
3
4
5
6
-----
0
1
2
3
4
5
6
7
-----
どの経路でも木のレベル (黒高さ) が同じになっていることはすぐにわかると思います。このように、AA 木ではどのようなデータでも木のバランスが大きく崩れることはありません。
今度は木の高さを比較してみましょう。次のリストを見てください。
リスト : データ挿入の簡単なテスト (2)
import node
import avlnode
import rbnode
import aanode
import random
# 木の高さを求める
def get_height(node, term = None):
if node is not term:
a = get_height(node.left, term)
b = get_height(node.right, term)
return max(a, b) + 1
return 0
for x in [1000, 2000, 4000, 8000, 16000]:
buff = [random.randint(0, 100000) for _ in range(x)]
a = None # AVL tree
b = None # Binary tree
c = rbnode.make_null() # 赤黒木
d = aanode.make_null() # AA 木
# buff.sort()
for n in buff:
a = avlnode.insert(a, n)
b = node.insert(b, n)
c, _ = rbnode.insert(c, n)
c.color = rbnode.BLACK
d = aanode.insert(d, n)
print(x, get_height(a), get_height(b), end=' ')
print(get_height(c, rbnode.null), get_height(d, aanode.null))
関数 get_height は木の高さを求めます。引数 term には木の終端を表すデータを渡します。赤黒木 (rbnode.py) の場合は rbnode.null を、AA 木 (aanode.py) の場合は aanode.null を指定します。
それでは、実行結果を示します。
表 : 木の高さ
N : AVL BIN R-B AA
--------------------------
1000 : 12 22 13 13
2000 : 13 22 13 14
4000 : 15 25 15 17
8000 : 16 29 16 18
16000 : 17 32 17 19
AA 木の高さは AVL 木や赤黒木よりも少しだけ高くなりましたが、単純な二分木に比べると木の高さは低く抑えられていて、平衡木として動作していることがわかります。AA 木の場合、データの探索は二分木と同じなので、AVL 木や赤黒木と同様にデータの探索は高速に処理できると思われます。
次はソート済みデータで試してみましょう。結果は次のようになりました。
表 : 木の高さ (a) 昇順 N : AVL R-B AA --------------------- 1000 : 10 17 15 2000 : 11 19 16 4000 : 12 21 17 8000 : 13 23 18 16000 : 14 25 19 (b) 逆順 N : AVL R-B AA --------------------- 1000 : 10 17 10 2000 : 11 19 11 4000 : 12 21 12 8000 : 13 23 13 16000 : 14 25 14
AA 木の場合、木の高さは赤黒木よりも低くなりました。AA 木の赤節は黒節の右の子にしかなれないので、昇順と逆順では木の高さが異なる結果になりました。逆順のデータで、木の高さが AVL 木と同じになるとは驚きました。ソート済みデータは赤黒木よりも AA 木の方が適しているのかもしれません。
●データの削除
次はデータの削除について説明します。AA 木の場合、二分木と同様にデータを削除して、そのあと AA 木の条件を満たすように木のバランスを修正します。実際に削除される節は「葉」の場合か、子を一つだけ持っている場合です。葉の場合は親節に終端 (null) が挿入され、子を一つだけ持っている場合は、その子が親節に挿入されます。このとき、親と子のレベルが 1 よりも大きくなったならば、バランスが崩れているので修正が必要になります。
AA 木のバランスは次の操作で修正することができます。
リスト : バランスの修正処理
if node.left.height < node.height - 1 or node.right.height < node.height - 1:
node.height -= 1
if node.right.height > node.height:
node.right.height = node.height
node = skew(node) # skew1
node.right = skew(node.right) # skew2
node.right.right = skew(node.right.right) # skew3
node = split(node) # split1
node.right = split(node.right) # split2
node とその右部分木に対して skew を 3 回、split を 2 回を適用して木のバランスをチェックします。これでバランスを修正できない場合は node の親節で修正を行います。M.Hiroi のような凡人には思いつかない方法ですね。これで本当に木のバランスを修正できるのか、削除パターンをすべて列挙して調べてみましょう。
●葉または子を一つ持つ節の場合
葉または子を一つ持つ節を削除する場合は簡単です。次の図を見てください。
もしも、削除する節が (a) のように「赤」ならば簡単です。AA 木の条件により、子を一つだけ持つ赤節は存在しないので、その赤節は「葉」であることがわかります。したがって、その節を削除するだけで OK です。黒高さに変化はないので、木のバランスを修正する必要もありません。
(b) は子を一つ持つ黒節 A を削除する場合です。子 B は赤節しかありえないので、A を B に置き換えるだけです。B は黒節となるので、木のバランスを修正する必要はありません。
(c), (d) は黒節の葉を削除する場合です。(c) は左の子 B を削除します。A の左の子は終端 null になるので、レベル差が 1 より大きくなり、バランスの修正が必要になります。まず、A のレベル (height) を -1 します。次に、skew と split を順番に適用しますが、部分木 A は AA 木の条件を満たしているので、ここでバランスを修正することはできません。A の親節でバランスを修正します。
(d) は右の子 C を削除します。A のレベルを -1 すると、左の子 B と同じレベルになります。そこで、skew を適用して木のバランスを修正します。これで部分木 B は AA 木の条件を満たしますが、部分木のレベルは -1 されているので、親節で木のバランスを修正します。
●子を 2 つ持つ節の場合
次は子を 2 つ持つ節で、部分木の高さが -1 された場合を説明します。次の図を見てください。
(a) は節 B のレベルが k1 から k0 (= k1 - 1) に下がり、節 C の子が黒節の場合です。この場合、節 A のレベルを -1 (k1 = k2 - 1) するだけで、部分木 A のバランスは保たれます。あとは A の親節で修正を行います。
(b) は節 C のレベルが k1 から k0 に下がり、節 B の子が黒節の場合です。まず、節 A のレベルを k1 に下げます。すると、節 B と同じレベルになるので skew を適用します。これで部分木 B は AA 木の条件を満たすので、B の親節で修正を行います。
次は節 A の孫が赤節の場合です。
(a) は孫節 E が赤節の場合です。まず、A のレベルを k1 に下げます。skew の操作は適用されませんが、A に split1 が適用されます。すると、C のレベルが k2 に上がるため、木のバランスは保たれます。
(b) は孫節 E が赤節の場合です。まず、A のレベルを k1 に下げます。次に、A に skew1 を適用します。すると、B の右の子が A になり、ここでも skew2 を適用します。次に、B に split1 を適用すると、木のバランスを保つことができます。
●子を 3 つ持つ節の場合
次は子を 3 つ持つ節、つまり、節 A の右の子が赤節の場合です。
(a), (b) は 3 つの子のうちの左の子 B のレベルが下がった場合です。(a) と (b) は節 G の色が異なります。まず、節 A と C のレベルを k1 に下げます。すると、C に skew2 が適用され、その後 A に split1 が適用されます。ここで、E の右の子 I が赤節であれば、さらに split2 が適用されます。これで木のバランスを保つことができます。
(b) は節 G の色が赤の場合です。節 C に skew2 を適用するのは (a) と同じです。節 G が赤なので、さらに skew3 を適用します。その後、A に split1 を、G に split2 を適用して、木のバランスを保つことができます。
次は中央の子のレベルが下がった場合です。
節 C が中央の子で、(a) と (b) では節 F の色が違います。(a) の場合、B のレベルを k1 に下げるだけで木のバランスを修正することができます。(b) の場合、B のレベルを下げて split を適用すると木のバランスを修正することができます。
最後に、右の子のレベルが下がった場合を説明します。
(a) と (b) は節 F の色が違います。(a) の場合、b のレベルを k1 に下げ、skew1 を適用します。これで木のバランスを修正することができます。(b) の場合、skew1 を適用したあと、節 F が赤なので再度 skew2 を適用します。それから、split1 を適用します。これで木のバランスを修正することができます。
このように skew と split を順番に適用することで、すべてのパターンに対して木のバランスを修正することができます。ただし、この方法が最適というわけではありません。もっと少ない回転操作で木のバランスを修正できる場合もあるからです。そのかわり、プログラムの実装はとても簡単になります。
●データ削除のプログラム
それでは、データを削除する関数 delete() を作成します。プログラムは次のようになります。
リスト : データの削除
# 最小値を探す
def search_min(node):
while node.left is not null: node = node.left
return node.data
# 削除
def delete(node, x):
if node is not null:
if x == node.data:
if node.left is null: return node.right
elif node.right is null: return node.left
else:
node.data = search_min(node.right)
node.right = delete(node.right, node.data)
elif x < node.data:
node.left = delete(node.left, x)
else:
node.right = delete(node.right, x)
# バランスのチェックと修正処理
if node.left.height < node.height - 1 or node.right.height < node.height - 1:
node.height -= 1
if node.right.height > node.height:
node.right.height = node.height
node = skew(node)
node.right = skew(node.right)
node.right.right = skew(node.right.right)
node = split(node)
node.right = split(node.right)
return node
二分木のデータ削除処理に、AA 木のバランスをチェックする処理を追加しただけなので、特に難しいところはないと思います。このように簡単にプログラムを実装できるところが AA 木の長所です。
●データ削除のテスト
それでは、ここでデータ削除のテストを行ってみましょう。テストプログラムは次のようになります。
リスト : データ削除の簡単なテスト
import aanode
# AA 木の表示
def print_node(node, x):
if node is not aanode.null:
print_node(node.left, x)
print(' ' * (x - node.height), node.data)
print_node(node.right, x)
root = aanode.make_null()
buff = range(8)
for x in buff:
root = aanode.insert(root, x)
print_node(root, root.height)
print('-----')
for x in buff:
root = aanode.delete(root, x)
print_node(root, root.height)
print('-----')
実行結果を示します。
0
1
2
3
4
5
6
7
-----
1
2
3
4
5
6
7
-----
2
3
4
5
6
7
-----
3
4
5
6
7
-----
4
5
6
7
-----
5
6
7
-----
6
7
-----
7
-----
-----
このように、データを削除しても AA 木のバランスが大きく崩れることはありません。
●AAtree クラスの作成
最後に、AA 木を表すクラスを作成します。次のリストを見てください。
#
# aatree.py : AA tree
#
# Copyright (C) 2009-2022 Makoto Hiroi
#
import aanode
# AA tree
class AAtree:
def __init__(self):
self.root = aanode.make_null()
# 探索
def search(self, x):
return aanode.search(self.root, x)
# 挿入
def insert(self, x):
self.root = aanode.insert(self.root, x)
# 削除
def delete(self, x):
self.root = aanode.delete(self.root, x)
# 巡回
def traverse(self):
for x in aanode.traverse(self.root):
yield x
# 表示
def __str__(self):
if self.root is aanode.null: return 'AAtree()'
buff = 'AAtree('
for x in aanode.traverse(self.root):
buff += '%s, ' % x
buff = buff.rstrip(', ')
buff += ')'
return buff
# テスト
if __name__ == '__main__':
import random
tree = AAtree()
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)
クラス名は AAtree としました。AAtree のメソッドはモジュール aanode の操作関数を呼び出すだけです。メソッド __init__() で root を初期化するとき、モジュール aanode の関数 make_null() を呼び出して、終端オブジェクトを設定することに注意してください。あとは、とくに難しいところはないでしょう。
それでは、テストの実行結果を示します。
[85, 67, 37, 40, 23, 64, 80, 68, 32, 51] AAtree() AAtree(23, 32, 37, 40, 51, 64, 67, 68, 80, 85) search 85 True delete 85 search 85 False AAtree(23, 32, 37, 40, 51, 64, 67, 68, 80) search 67 True delete 67 search 67 False AAtree(23, 32, 37, 40, 51, 64, 68, 80) search 37 True delete 37 search 37 False AAtree(23, 32, 40, 51, 64, 68, 80) search 40 True delete 40 search 40 False AAtree(23, 32, 51, 64, 68, 80) search 23 True delete 23 search 23 False AAtree(32, 51, 64, 68, 80) search 64 True delete 64 search 64 False AAtree(32, 51, 68, 80) search 80 True delete 80 search 80 False AAtree(32, 51, 68) search 68 True delete 68 search 68 False AAtree(32, 51) search 32 True delete 32 search 32 False AAtree(51) search 51 True delete 51 search 51 False AAtree()
●AA 木の評価
それでは、AVL 木、赤黒木、AA 木の性能を比較してみましょう。次のリストを見てください。
リスト : AVL 木、AA 木、赤黒木のテスト
from avltree import *
from rbtree import *
from aatree import *
import time, random
def insert_test(tree, buff):
s = time.time()
for x in buff:
tree.insert(x)
e = time.time()
return e - s
def search_test(tree, buff):
s = time.time()
for x in buff:
tree.search(x)
e = time.time()
return e - s
def delete_test(tree, buff):
s = time.time()
for x in buff:
tree.delete(x)
e = time.time()
return e - s
for x in [10000, 20000, 40000, 80000, 160000]:
buff = [random.randint(0, 100000) for _ in range(x)]
# buff.sort()
print('{:6d}'.format(x), end='')
for tree in [AVLtree, RBtree, AAtree]:
a = tree()
print(': {:.3f} {:.3f} {:.3f}'.format(insert_test(a, buff), search_test(a, buff), delete_test(a, buff)), end=' ')
print()
データは乱数で生成します。そして、insert_test() で木にデータを挿入する時間、search_test() でデータを探索する時間、delete_test() でデータを削除する時間を計測します。結果は次のようになりました。
表 : 実行結果 (単位 : 秒)
: AVL tree : red-black tree : AA tree
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------------------------------------------------------------------------
10000: 0.052 0.021 0.040 : 0.054 0.022 0.046 : 0.074 0.019 0.066
20000: 0.120 0.040 0.096 : 0.111 0.041 0.103 : 0.159 0.041 0.156
40000: 0.226 0.098 0.196 : 0.250 0.101 0.235 : 0.356 0.102 0.339
80000: 0.500 0.223 0.404 : 0.548 0.226 0.506 : 0.781 0.234 0.699
160000: 0.992 0.478 0.785 : 1.077 0.493 1.010 : 1.666 0.496 1.416
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
データの探索は AA 木でも高速に処理できますが、データの挿入と削除は AVL 木や赤黒木よりも遅くなりました。再帰を繰り返しに変換するともう少し速くなるかもしれません。
次はソート済みのデータで試してみましょう。実行結果は次のようになりました。
表 : ソート済みデータの実行結果 (単位 : 秒)
(a) 昇順
: AVL tree : red-black tree : AA tree
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------------------------------------------------------------------------
10000: 0.051 0.018 0.031 : 0.078 0.016 0.041 : 0.089 0.016 0.058
20000: 0.108 0.036 0.069 : 0.172 0.035 0.093 : 0.203 0.035 0.124
40000: 0.204 0.077 0.138 : 0.374 0.078 0.188 : 0.417 0.075 0.265
80000: 0.438 0.185 0.305 : 0.803 0.181 0.469 : 0.877 0.159 0.555
160000: 0.785 0.324 0.539 : 1.485 0.350 0.811 : 1.748 0.337 1.062
(b) 逆順
: AVL tree : red-black tree : AA tree
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------------------------------------------------------------------------
10000: 0.052 0.016 0.036 : 0.072 0.016 0.041 : 0.066 0.016 0.076
20000: 0.108 0.042 0.062 : 0.155 0.041 0.094 : 0.143 0.040 0.165
40000: 0.206 0.076 0.143 : 0.337 0.075 0.197 : 0.301 0.081 0.359
80000: 0.426 0.172 0.266 : 0.683 0.175 0.387 : 0.639 0.167 0.720
160000: 0.798 0.332 0.534 : 1.334 0.333 0.776 : 1.274 0.327 1.507
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
ソート済みデータの場合、AA 木は昇順でデータの挿入に時間がかかり、逆順ではデータの削除に時間がかかります。この結果を見ると、AA 木は赤黒木よりもソート済みデータに適しているとはいえないようです。データの探索は AA 木と赤黒木で大きな違いはないので、AA 木は平衡木として機能していることがわかります。
拙作のページ AVL 木 [2] の Appendix で説明しましたが、木の高さを使った AVL 木の実装では、実行速度がとても遅くなりました。木の高さを使った実装方法で、ここまで高い性能をたたきだす AA 木は優れたアルゴリズムだと思います。
なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●プログラムリスト
#
# aanode.py : AA tree 操作関数
#
# Copyright (C) 2009-2022 Makoto Hiroi
#
# 終端
null = None
# 節の定義
class Node:
def __init__(self, x):
self.data = x
self.height = 1
self.left = null
self.right = null
# 終端の生成
def make_null():
global null
if null is None:
null = Node(None)
null.height = 0
null.left = null
null.right = null
return null
# 右回転
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
# 左の子が赤の場合
def skew(node):
if node.left.height == node.height:
node = rotate_right(node)
return node
# 右の孫節が赤の場合
def split(node):
if node.height == node.right.right.height:
node = rotate_left(node)
node.height += 1
return node
# 探索
def search(node, x):
while node is not null:
if x == node.data: return True
elif x < node.data:
node = node.left
else:
node = node.right
return False
# 挿入
def insert(node, x):
if node is null: return Node(x)
elif x == node.data: return node
elif x < node.data:
node.left = insert(node.left, x)
else:
node.right = insert(node.right, x)
return split(skew(node))
# 最小値を探す
def search_min(node):
while node.left is not null: node = node.left
return node.data
# 削除
def delete(node, x):
if node is not null:
if x == node.data:
if node.left is null: return node.right
elif node.right is null: return node.left
else:
node.data = search_min(node.right)
node.right = delete(node.right, node.data)
elif x < node.data:
node.left = delete(node.left, x)
else:
node.right = delete(node.right, x)
# バランスのチェックと修正処理
if node.left.height < node.height - 1 or node.right.height < node.height - 1:
node.height -= 1
if node.right.height > node.height:
node.right.height = node.height
node = skew(node)
node.right = skew(node.right)
node.right.right = skew(node.right.right)
node = split(node)
node.right = split(node.right)
return node
# 巡回
def traverse(node):
if node is not null:
for x in traverse(node.left):
yield x
yield node.data
for x in traverse(node.right):
yield x
# AA 木のチェック
def check_tree(node):
if node is not null:
if node.height != node.left.height + 1:
raise 'aa tree error1'
if node.height != node.right.height and node.height != node.right.height + 1:
raise 'aa tree error2'
if node.height == node.right.right.height:
raise 'aa tree error3'
check_tree(node.left)
check_tree(node.right)
# test
if __name__ == '__main__':
import random, time
root = make_null()
buff = list(range(1000))
random.shuffle(buff)
print('insert test')
for x in buff:
root = insert(root, x)
check_tree(root)
print('search test')
random.shuffle(buff)
for x in buff:
if not search(root, x):
raise 'search test error'
print('delete test')
for x in buff:
root = delete(root, x)
check_tree(root)
改訂 2022 年 9 月 10 日