今回は平衡木 (balanced tree) の一つである「AVL 木 (AVL tree)」を取り上げます。拙作のページ「二分木とヒープ」で説明したように、二分木は左右の部分木のバランスが崩れると性能が劣化します。二分木の場合、最下層にあるデータを探す場合が最悪で、木の高さ分だけ比較が行われます。したがって、木の高さを低く抑えた方が探索効率も良くなります。
二分木の高さはデータ数を N とすると、データがランダムに挿入されれば log2 N 程度に収まります。しかし、昇順にソートされたデータを挿入していくと、右側の部分木にだけデータが追加されていくことになり、けっきょく連結リストを線形探索することと同じになってしまいます。二分木の性能を十分に発揮させるには、左右の部分木のバランスが重要なのです。
そこで、木のバランスを一定の範囲に収める平衡木が考案されています。有名なところでは AVL 木、赤黒木 (2 色木)、AA 木、2-3 木、B 木、B* 木などがあります。この中で 2-3 木、B 木、B* 木は多分木、AVL 木、赤黒木、AA 木は二分木を使用します。
今回取り上げる AVL 木は、1962 年に Adel'son-Vel'skii と Landis が考案したものです。考案者の頭文字をとって AVL 木と呼ばれています。この方法は、左右の部分木の高さを計算し、その差が 1 より大きくなったならば、それを 1 以下になるように修正することで、全体の木の高さを抑えようとするものです。
N 個の節を持つ二分木の高さは、節が左右に均等に分配されれば log2 N 程度に収まります。参考文献『X68000 マシン語プログラミング 木探索』によれば、『AVL 平衡木では、この 1.5 倍程度の高さに収まる。』 とのことです。したがって、100 万個のデータに対して木の高さは 30 程度に収まることになります。
AVL 木は最初に実現された平衡木なのですが、性能的には B 木や B* 木の方が優れているといわれています。B 木や B* 木はハードディスクなど外部記憶上での探索に適した木構造 (外部探索木) で、データベースなどで利用されています。多分木を使う場合、原理的に難しいところはないのですが、実際のプログラムは相当に複雑になります。
このため、主記憶上での探索には二分木をベースにした AVL 木、赤黒木、AA 木などを用いることが多いようです。たとえば、赤黒木は C++ の Standard Template Library (STL) で使用されています。AVL 木は GTK+ / GNOME のライブラリ GLib で使用されています。
AVL 木は二分木の一種なので、データの探索は二分木と同様に簡単にプログラムできます。ところが、AVL 木にデータを挿入する場合、二分木のように簡単ではありません。AVL 木の条件を満たすように、木の修正が必要になる場合があるからです。このときに用いられる操作が「回転 (rotate)」です。回転は二分木の条件を満たしたまま木構造を修正する基本的な操作です。
ここで回転について詳しく説明しましょう。次の図を見てください。
Ａ 右回転 Ｂ
／ ＼ ────→ ／ ＼
／ ＼ ／ ＼
Ｂ Ｃ 左回転 Ｄ Ａ
／ ＼ ←──── ／ ＼
Ｄ Ｅ Ｅ Ｃ
(１) (２)
どちらの木も Ｄ＜Ｂ＜Ｅ＜Ａ＜Ｃ を満たしている
図 1 : 二分木の回転
| 右回転 | 左回転 | |
|---|---|---|
| Ｃ | ||
| Ｄ | ||
| Ｅ |
回転は節 A と B の親子関係を反転する操作です。(1) -> (2) の操作を「右回転 (right rotate)」といい、逆に (2) -> (1) の操作を「左回転 (left rotate)」といいます。このような操作を行っても、(1) と (2) は二分木の条件である「左の子 < 節のデータ < 右の子」 を満たしています。
また、木を回転すると、部分木 (C, D, E) に含まれる節のレベル (ルートからの節までの経路長) は上表のように変化します。このような回転操作を行うことで、木のバランスを修正することができます。
それでは、実際に二分木の回転を Python でプログラムしてみましょう。次のリストを見てください。
リスト : 二分木の回転操作
# 右回転
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
拙作のページ「二分木とヒープ」で作成したプログラム (node.py) に関数 rotate_right() と rotate_left() を追加します。どちらの関数も引数 node 以下の部分木に対して回転操作を行います。右回転は node と「左の子」の親子関係を反転します。左の子を変数 lnode にセットし、node と lnode の子を書き換えます。そして、新しく親になる lnode を返します。
左回転は node と「右の子」の親子関係を反転します。右の子を変数 rnode にセットし、node と rnode の子を書き換えます。そして、新しく親になる rnode を返します。回転操作の図を見ながらプログラムを読んでみると、よくわかると思います。
それでは、簡単な実行例を示しましょう。
リスト : 簡単な回転操作のテスト
from node import *
# 表示
def print_node(node, n):
if node:
print_node(node.left, n + 1)
print(' ' * n, node.data)
print_node(node.right, n + 1)
# テスト
if __name__ == '__main__':
root = None
for x in [40, 20, 50, 10, 30]:
root = insert(root, x)
print_node(root, 0)
print('rotate right')
root = rotate_right(root)
print_node(root, 0)
print('rotate right')
root = rotate_right(root)
print_node(root, 0)
print('rotate left')
root = rotate_left(root)
print_node(root, 0)
print('rotate left')
root = rotate_left(root)
print_node(root, 0)
print_node は二分木を表示する関数です。データを出力する前に、レベル * 4 個の空白を出力します。これで木の形を表すことができます。テストでは、関数 insert() で二分木にデータを挿入して回転操作を行います。なお、今回のプログラムは再帰呼び出しを繰り返しに変換しています。詳細はプログラムリストをお読みください。
実行結果は次のようになります。
10
20
30
40
50
rotate right
10
20
30
40
50
print_node() の表示は、上が左部分木で下が右部分木になり、左側が根の方向で右側が葉の方向になります。root に右回転を行うとルートの節は 20 になり、右部分木の高さが一つ増えて、左部分木の高さが一つ減ります。右回転を続けて行うと次のようになります。
rotate right
10
20
30
40
50
ルートの節は 10 になり、左部分木は空になります。この状態で左回転を 2 回行うと元の状態に戻ります。
rotate left
10
20
30
40
50
rotate left
10
20
30
40
50
このように、回転操作を行うことで木の高さを修正することができます。
それでは AVL 木にデータを挿入するとき、どのように木の構成を修正するのか見ていくことにしましょう。
左右の部分木の高さの差を「平衡度」という数値を使って表すことにします。新しい節を追加した場合、その親の節で平衡度が崩れます。新しい節は子を持っていないので、平衡度は 0 とします。そして、左部分木に新しい子を追加した場合は、平衡度を一つ増やすことにし、右部分木に新しい子を追加した場合は一つ減らすことにします。このようにすると、平衡度が 1 ならば左部分木が一つ高く、-1 ならば右部分木が一つ高いということになります。
このあと根の方向に向かって平衡度が崩れていないかチェックしていきます。そして、平衡度が -2 または 2 になったら、左右の部分木の高さを修正します。
それでは、修正が必要な場合を考えていきましょう。次の図を見てください。
平衡度 平衡度
Ａ Ａ：1 Ａ Ａ：2
／ ＼ ／ ＼
Ｂ Ｃ Ｂ：0 Ｂ Ｃ Ｂ：1
／ ＼ ／ ＼
Ｄ Ｅ Ｄ：0 Ｄ Ｅ Ｄ：1
／
Ｆ Ｆ：0
図 2 : ＬＬ１重回転 (修正前)
節 A の平衡度は 1 で、そのほかの節の平衡度は 0 です。この状態で、節 D の左側に節 F を追加します。すると、D の平衡度は +1 されて 1 になります。その親の B は、左部分木で節が追加されたので、この平衡度も 1 になります。
そして、その親の A も左部分木で追加が行われたので、平衡度が +1 されて 2 になり、修正が必要になります。この場合は A を右回転します。この操作を「ＬＬ１重回転」といいます。修正後は次のようになります。
平衡度
Ｂ Ａ：0
／ ＼
Ｄ Ａ Ｂ：0
／ ／ ＼
Ｆ Ｅ Ｃ Ｄ：1
Ｆ < Ｄ < Ｂ < Ｅ < Ａ < Ｃ
図 3 : ＬＬ１重回転 (修正後)
次も、左部分木が高くなる場合です。
平衡度 平衡度
Ａ Ａ：1 Ａ Ａ：2
／ ＼ ／ ＼
Ｂ Ｃ Ｂ：0 Ｂ Ｃ Ｂ：-1
／ ＼ ／ ＼
Ｄ Ｅ Ｄ：0 Ｄ Ｅ Ｅ：1
／
Ｆ Ｆ：0
図 4 : ＬＲ２重回転 (修正前)
今度は、節 E の左側に節 F を追加します。E の平衡度は 1 になりますが、B から見ると右部分木に節が追加されているので、平衡度を一つ減らして -1 となります。その親の A は、左部分木に節が追加されているので、平衡度を +1 して 2 になります。
この場合は B を左回転してから、さらに A を右回転します。この操作を「ＬＲ２重回転」といいます。A の平衡度はＬＬ１重回転と同じく 2 になりますが、B の平衡度が -1 になるので区別することができます。修正後は図 5 のようになります。
節 F を節 E の右側に追加しても、ＬＲ２重回転となります。ただし、修正後の平衡度が異なります。これはあとで説明します。
平衡度
Ｅ Ａ：-1
／ ＼
Ｂ Ａ Ｂ：0
／ ＼ ＼
Ｄ Ｆ Ｃ Ｅ：0
Ｄ < Ｂ < Ｆ < Ｅ < Ａ < Ｃ
図 5 : ＬＲ２重回転 (修正後)
今度は、右部分木が高くなる場合を考えましょう。
平衡度 平衡度
Ａ Ａ：-1 Ａ Ａ：-2
／ ＼ ／ ＼
Ｂ Ｃ Ｃ：0 Ｂ Ｃ Ｃ：-1
／ ＼ ／ ＼
Ｄ Ｅ Ｅ：0 Ｄ Ｅ Ｅ：-1
＼
Ｆ Ｆ：0
図 6 : ＲＲ１重回転 (修正前)
最初の状態は、節 A からみて右部分木が高いので、平衡度は -1 になっています。そのほかの節の平衡度は 0 です。この状態から節 E の右側に節 F を追加することを考えます。E の平衡度は -1 になります。C の平衡度は右部分木に節が追加されたので、一つ減らして -1 になります。その親の A は、これも右部分木に追加されているので、平衡度を 1 つ減らして -2 になり、修正が必要になります。この場合は A を左回転します。この操作を「ＲＲ１重回転」といいます。修正後は次のようになります。
平衡度
Ｃ Ａ：0
／ ＼
Ａ Ｅ Ｃ：0
／ ＼ ＼
Ｂ Ｄ Ｆ Ｅ：-1
Ｂ < Ａ < Ｄ < Ｃ < Ｅ < Ｆ
図 7 : ＲＲ１重回転 (修正後)
１重回転の次は２重回転です。
平衡度 平衡度
Ａ Ａ：-1 Ａ Ａ：-2
／ ＼ ／ ＼
Ｂ Ｃ Ｃ：0 Ｂ Ｃ Ｃ：1
／ ＼ ／ ＼
Ｄ Ｅ Ｄ：0 Ｄ Ｅ Ｄ：1
／
Ｆ Ｆ：0
図 8 : ＲＬ２重回転 (修正前)
節 D の左側に節 F を追加します。D の平衡度は 1 になります。C は左部分木に追加されたので、平衡度を一つ増やして 1 になります。その親の A は右部分木に追加されたので、平衡度を一つ減らして -2 となります。
この場合は C を右回転してから、さらに A を左回転します。この操作を「ＲＬ２重回転」といいます。ＲＲ１重回転と同様に A の平衡度は -2 ですが、C の平衡度が 1 なので区別することができます。修正後は次のようになります。
平衡度
Ｄ Ａ：0
／ ＼
Ａ Ｃ Ｃ：-1
／ ＼ ＼
Ｂ Ｆ Ｅ Ｄ：0
Ｂ < Ａ < Ｆ < Ｄ < Ｃ < Ｅ
図 9 : ＲＬ２重回転 (修正後)
D の右側に F を追加してもＲＬ２重回転になりますが、修正後の平衡度が異なります。これはあとで説明します。
このように、データの挿入で木を修正する場合は、大きく分けるとＬＬ１重回転、ＲＲ１重回転、ＬＲ２重回転、ＲＬ２重回転の 4 通りになります。
それではプログラムを作りましょう。最初に節を表すクラスを定義します。
リスト : 節の定義
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
self.balance = 0 # 平衡度
クラス名は Node としました。基本的には二分木の節 Node と同じですが、平衡度を表すため、新しいインスタンス変数 balance を追加します。 balance は 0 に初期化します。
次は、データを挿入する関数 insert() を作成します。新しい節を挿入した場合、根の方に向かって平衡度をチェックしていく処理が必要になります。拙作のページ「二分木とヒープ」では、データの挿入を再帰呼び出しでプログラムしましたが、平衡度のチェックを組み込むには少々面倒なので、ループに展開することにします。単純なループでは、たどってきた経路がわからなくなるので、経路を表す配列 (Python のリスト) を用意して通過した節を記憶します。プログラムは次のようになります。
リスト : データの挿入 (AVL 木)
# 挿入または削除が行われた部分木の種別
LEFT = 0
RIGHT = 1
# 挿入
def insert(root, x):
if root is None: return Node(x)
path = []
node = root
while True:
if node.data == x: return root
elif x < node.data:
path.append((node, LEFT))
if node.left is None:
node.left = Node(x)
break
node = node.left
else:
path.append((node, RIGHT))
if node.right is None:
node.right = Node(x)
break
node = node.right
return balance(root, path)
関数 insert() は AVL 木のルートと挿入するデータを受け取り、挿入したあとの木を返します。これは二分木の場合と同じです。経路を記憶するために配列 path を用意します。path には節と左右どちらの部分木をたどったかを示すデータ (LEFT or RIGTH) をタプルにまとめてセットします。
最初に、root が空の木 (None) ならば新しい節を Node(x) で生成して返します。次に、while ループで木をたどり、データを挿入する場所を探します。もしも、x と等しいデータがあれば、データを挿入せずに root を返します。そして、x が node.data よりも小さい場合は左部分木をたどり、大きい場合は右部分木をたどります。このとき、path に (node, LEFT) または (node, RIGHT) をセットします。
部分木が None の場合は、Node(x) で新しい節を生成して、そこに節を挿入します。そして、break で while ループを脱出します。最後に、関数 balance() を呼び出して、木の平衡度をチェックします。このとき、ルートを書き換える場合があるので、balance() でルートを返すようにします。
次は平衡度をチェックする関数 balance() を作ります。
リスト : 平衡度のチェックと修正
def balance(root, path):
new_node = None
while len(path) > 0:
pnode, dir = path.pop() # pnode 節, dir 部分木の種別
if dir == LEFT:
pnode.balance += 1
else:
pnode.balance -= 1
b = pnode.balance
if b == 0: return root # 修正不要 root を返す
if b > 1:
if pnode.left.balance < 0:
# LR ２重回転
pnode.left = rotate_left(pnode.left)
new_node = rotate_right(pnode)
update_balance(new_node)
else:
# LL １重回転
new_node = rotate_right(pnode)
new_node.balance = 0
pnode.balance = 0
break
elif b < -1:
if pnode.right.balance > 0:
# RL ２重回転
pnode.right = rotate_right(pnode.right)
new_node = rotate_left(pnode)
update_balance(new_node)
else:
# RR １重回転
new_node = rotate_left(pnode)
new_node.balance = 0
pnode.balance = 0
break
# 子の付け替え
if len(path) > 0:
# pnode の親節を求める
gnode, gdir = path.pop()
if gdir == LEFT:
gnode.left = new_node
else:
gnode.right = new_node
elif new_node is not None:
return new_node
return root
経路 path に格納された節を取りだして、平衡度をチェックしていきます。pnode は平衡度をチェックする節で、dir はデータが挿入された部分木 (LEFT or RIGTH) を表します。
最初の while ループで、path にデータがある間、平衡度をチェックします。dir が LEFT であれば pnode.balance を +1 し、RIGHT であれば -1 します。そして、その値を変数 b にセットします。平衡度 b が 0 ならば木のバランスは保たれているので、それ以上チェックする必要はありません。ルートは変更する必要がないので、root をそのまま返します。
次に、b が 1 より大きい場合は、木を修正する必要があります。この場合は左部分木が大きいので、ＬＬ１重回転かＬＲ２重回転を行います。左の子の平衡度 (pnode.left.balance) が 0 よりも小さい場合はＬＲ２重回転、そうでなければＬＬ１重回転です。
ＬＲ２重回転の場合、pnode.left を左回転してから pnode を右回転します。そして、回転した木を変数 new_node にセットします。平衡度の修正は関数 update_balance() で行います。ＬＬ１重回転の場合は pnode を右回転して、その結果を new_node にセットします。そして、new_node と pnode の平衡度を 0 に修正します。
平衡度 b が -1 より小さい場合は、右部分木が大きくなったので、ＲＲ１重回転かＲＬ２重回転の処理が必要になります。右の子の平衡度 (pnode.right.balance) が 0 よりも大きい場合はＲＬ二重回転、そうでなければＲＲ１重回転です。
ＲＬ２重回転の場合、pnode.right を右回転してから、pnode を左回転します。そして、回転した木を変数 new_node にセットします。平衡度の修正は update_balance() で行います。ＲＲ１重回転の場合は pnode を左回転して、その結果を new_node にセットします。そして、new_node と pnode の平衡度を 0 に修正します。
修正が終わったら break でループを脱出します。これ以外は、修正が必要なほどバランスが崩れていない場合です。path から pnode の親を取り出して平衡度のチェックを続行します。
ループを抜けたあと、バランスが崩れた部分木は修正されていますが、その部分木を持つ親節の書き換えが済んでいません。次の図を見てください。
Ｐ 平衡度 Ｐ 平衡度
＼ ＼
Ａ Ａ：-2 Ｄ Ａ：1
／ ＼ ／ ＼
Ｂ Ｃ Ｃ：1 Ａ Ｃ Ｃ：0
／ ＼ ／ ／ ＼
Ｄ Ｅ Ｄ：-1 Ｂ Ｆ Ｅ Ｄ：0
＼
Ｆ Ｆ：0
(1) 修正前 (2) 修正後
図 10 : 子の付け替えが必要 (例 : ＲＬ２重回転)
上図において、節 A で木の修正が行われた場合、節 P の右側の子を A から D に付け替えなければいけません。D は変数 new_node に格納されているので、子の付け替え処理を行います。
もし path にデータがあれば、そこから親節を取り出して変数 gnode と gdir にセットします。gdir が LEFT であれば gnode.left に、そうでなければ gnode.right に new_node をセットします。path にデータがなく new_node が None でなければ、ルートを書き換えるため new_node を返します。ただし、new_node が None の場合は、木の修正が行われていないので root をそのまま返します。
平衡度 平衡度
Ａ Ａ：2 Ｅ ｘ： 1, 0, -1
／ ＼ ／ ＼ --------------
Ｂ Ｃ Ｂ：-1 ／ ＼ Ｂ： 0, 0, 1
／ ＼ Ｂ Ａ Ａ：-1, 0, 0
Ｄ Ｅ Ｅ：ｘ ／ ＼ ／ ＼ Ｅ： 0, 0, 0
／ ＼ Ｄ Ｆ Ｇ Ｅ
Ｆ Ｇ
(1) 修正前 (2) 修正後
(a) ＬＲ２重回転の場合
平衡度 平衡度
Ａ Ａ：2 Ｄ ｘ： 1, 0, -1
／ ＼ ／ ＼ --------------
Ｂ Ｃ Ｂ：-1 ／ ＼ Ａ： 0, 0, 1
／ ＼ Ａ Ｃ Ｃ：-1, 0, 0
Ｄ Ｅ Ｄ：ｘ ／ ＼ ／ ＼ Ｄ： 0, 0, 0
／ ＼ Ｂ Ｆ Ｇ Ｅ
Ｆ Ｇ
(1) 修正前 (2) 修正後
(b) ＲＬ２重回転の場合
図 11 : ２重回転の平衡度の更新
次は２重回転のあとで平衡度を修正する関数 update_balance() を作ります。２重回転の場合、図 11 のように場合分けすることができます。
新しく親になる節を node としましょう。修正前の node の子は、どちらの２重回転の場合でも F と G です。node の平衡度は 0 になるので、node の修正前の平衡度、つまり F と G の高さの違いにより node の子の平衡度が決まります。そして、その値はどちらの２重回転でも同じになります。
node の平衡度が 1 のときは、G の高さが 1 つ少ない場合です。たとえば、G が空の木の場合を考えてみてください。この場合、node の左の子は平衡度 0 になり、右の子は平衡度が -1 になります。
node の平衡度が -1 のときは、F の高さが 1 つ少ない場合です。たとえば、F が空の木の場合を考えてみてください。この場合、node の左の子は平衡度が 1 になり、右の子の平衡度は 0 になります。
node の平衡度が 0 の場合は、F と G は同じ高さなので、node の左右の子は平衡度が 0 になります。
これをプログラムすると、次のようになります。
リスト : 平衡度の更新 (２重回転だけ)
def update_balance(node):
if node.balance == 1:
node.right.balance = -1
node.left.balance = 0
elif node.balance == -1:
node.right.balance = 0
node.left.balance = 1
else:
node.right.balance = 0
node.left.balance = 0
node.balance = 0
引数 node には修正した部分木 (節 E または D) が渡されます。node.balance が 1 の場合、右部分木の平衡度が -1 で、左部分木の平衡度が 0 になります。node.balance が -1 の場合、右部分木の平衡度が 0 で、左部分木の平衡度が 1 になります。node.balance が 0 の場合、左右どちらの部分木も平衡度は 0 になります。最後に、node の平衡度を 0 にします。
それでは、ここでデータ挿入のテストを行ってみましょう。単純な「二分木」と比較してみます。テストプログラムは次のようになります。
リスト : データ挿入の簡単なテスト
import node
import avlnode
# 表示
def print_node(node, n):
if node:
print_node(node.left, n + 1)
print(' ' * n, node.data)
print_node(node.right, n + 1)
a = None # AVL tree
b = None # Binary tree
print('Binary tree')
for x in range(1, 8):
b = node.insert(b, x)
print_node(b, 0)
print('AVL tree')
for x in range(1, 8):
a = avlnode.insert(a, x)
print_node(a, 0)
1 から 7 までの整数値を順番に二分木と AVL 木に挿入します。最初に、二分木の実行結果を示します。
Binary tree
1
2
3
4
5
6
7
実行結果を見ればおわかりのように、右部分木にしかデータが挿入されません。これが二分木での最悪の状態です。では、AVL 木の実行結果を示します。
AVL tree
1
2
3
4
5
6
7
このように、AVL 木の場合はバランスが完全に保たれています。
次は二分木と AVL 木の高さを比較してみましょう。次のリストを見てください。
リスト : データ挿入の簡単なテスト (2)
import node
import avlnode
import random
# 木の高さを求める
def get_height(node):
if node:
a = get_height(node.left)
b = get_height(node.right)
return max(a, b) + 1
return 0
# 平衡度のチェック
def check_avl(node):
if node:
a = check_avl(node.left)
b = check_avl(node.right)
if a - b != node.balance: raise 'avl tree error'
return max(a, b) + 1
return 0
for x in [1000, 2000, 4000, 8000]:
buff = [random.randint(0, 100000) for _ in range(x)]
a = None # AVL tree
b = None # Binary tree
for n in buff:
a = avlnode.insert(a, n)
check_avl(a)
b = node.insert(b, n)
print(x, get_height(a), get_height(b))
関数 get_height() は木の高さを求めます。木の高さは再帰呼び出しを使うと簡単に求めることができます。node が None の場合は 0 を返します。これが再帰呼び出しの停止条件です。そうでなければ、左右の部分木の高さを get_height() で求めます。そうすると、node の木の高さは max(a, b) + 1 になります。関数 check_avl() は部分木の高さを求めて平衡度が間違っていないかチェックします。
それでは、実行結果を示します。
| N | AVL | BIN | logN |
|---|---|---|---|
| 1000 | 12 | 23 | 10 |
| 2000 | 13 | 23 | 11 |
| 4000 | 14 | 28 | 12 |
| 8000 | 16 | 26 | 13 |
AVL 木の高さは二分木よりも低くなりました。log2 N の 1.5 倍以内に収まっています。それに対し、二分木の高さは log2 N の 2 倍より大きくなる場合もあります。まあ、コンピュータで扱う乱数は「擬似乱数」なので、二分木のバランスが多少崩れるのはしょうがないでしょう。木の高さは AVL 木のほうが低いので、二分木よりも高速に探索できることが期待できます。これはプログラムを完成したあとで、実際に試してみましょう。
次回はデータの削除について説明します。
#
# avlnode.py : AVL tree 操作関数
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
# 節の定義
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
self.balance = 0 # 平衡度
# 右回転
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 search(node, x):
while node is not None:
if node.data == x: return True
if x < node.data:
node = node.left
else:
node = node.right
return False
#
# 平衡度の更新 (２重回転だけ)
#
def update_balance(node):
if node.balance == 1:
node.right.balance = -1
node.left.balance = 0
elif node.balance == -1:
node.right.balance = 0
node.left.balance = 1
else:
node.right.balance = 0
node.left.balance = 0
node.balance = 0
#
# データの挿入
#
# 挿入または削除が行われた部分木の種別
LEFT = 0
RIGHT = 1
# バランスが崩れていたら修正する
def balance(root, path):
new_node = None
while len(path) > 0:
pnode, dir = path.pop() # pnode 節, dir 部分木の種別
if dir == LEFT:
pnode.balance += 1
else:
pnode.balance -= 1
b = pnode.balance
if b == 0: return root # 修正不要 root を返す
if b > 1:
if pnode.left.balance < 0:
# LR ２重回転
pnode.left = rotate_left(pnode.left)
new_node = rotate_right(pnode)
update_balance(new_node)
else:
# LL １重回転
new_node = rotate_right(pnode)
new_node.balance = 0
pnode.balance = 0
break
elif b < -1:
if pnode.right.balance > 0:
# RL ２重回転
pnode.right = rotate_right(pnode.right)
new_node = rotate_left(pnode)
update_balance(new_node)
else:
# RR １重回転
new_node = rotate_left(pnode)
new_node.balance = 0
pnode.balance = 0
break
# 子の付け替え
if len(path) > 0:
# pnode の親節を求める
gnode, gdir = path.pop()
if gdir == LEFT:
gnode.left = new_node
else:
gnode.right = new_node
elif new_node is not None:
return new_node
return root
# 挿入
def insert(root, x):
if root is None: return Node(x)
path = []
node = root
while True:
if node.data == x: return root
elif x < node.data:
path.append((node, LEFT))
if node.left is None:
node.left = Node(x)
break
node = node.left
else:
path.append((node, RIGHT))
if node.right is None:
node.right = Node(x)
break
node = node.right
return balance(root, path)
#
# データの削除
#
# バランスが崩れていたら修正する
def balance_delete(root, path):
while len(path) > 0:
new_node = None
pnode, dir = path.pop() # pnode = 節, dir = 削除した部分木
if dir == LEFT:
pnode.balance -= 1 # 挿入と逆で left が -1, right が +1
else:
pnode.balance += 1
b = pnode.balance
if b > 1:
if pnode.left.balance < 0:
# ２重回転
pnode.left = rotate_left(pnode.left)
new_node = rotate_right(pnode)
update_balance(new_node)
else:
# １重回転
new_node = rotate_right(pnode)
if new_node.balance == 0:
new_node.balance = -1
pnode.balance = 1
else:
new_node.balance = 0
pnode.balance = 0
elif b < -1:
if pnode.right.balance > 0:
# ２重回転
pnode.right = rotate_right(pnode.right)
new_node = rotate_left(pnode)
update_balance(new_node)
else:
# １重回転
new_node = rotate_left(pnode)
if new_node.balance == 0:
new_node.balance = 1
pnode.balance = -1
else:
new_node.balance = 0
pnode.balance = 0
elif b != 0:
break # b == 1 or b == -1 は修正終了
# 子の付け替え
if new_node is not None:
if len(path) == 0: return new_node # root になる
gnode, gdir = path[len(path) - 1] # pnode の親
if gdir == LEFT:
gnode.left = new_node
else:
gnode.right = new_node
if new_node.balance != 0: break # 修正終了
return root
# データを探す
def _search(node, x, path):
while node is not None:
if node.data == x: return node
if x < node.data:
path.append((node, LEFT))
node = node.left
else:
path.append((node, RIGHT))
node = node.right
return None
# 最小値を探す
def _search_min(node, path):
while node.left is not None:
path.append((node, LEFT))
node = node.left
return node
# 削除
def delete(root, x):
if root is None: return None # 空の木
path = [] # 経路
node = _search(root, x, path) # 探索
if node is None: return root # 削除データなし
if node.left is not None and node.right is not None:
# 子が二つある場合
# 右部分木の最小値を探して置き換える
path.append((node, RIGHT))
min_node = _search_min(node.right, path)
node.data = min_node.data
node = min_node
if len(path) > 0:
pnode, dir = path[len(path) - 1]
else:
pnode = None
# 節を削除する
if node.left is None:
cnode = node.right
else:
cnode = node.left
if pnode is None:
return cnode # root の削除
elif dir == LEFT:
pnode.left = cnode
else:
pnode.right = cnode
return balance_delete(root, path)
# 巡回
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
#
# node.py : 二分木の操作関数 (非再帰版)
#
# Copyright (C) 2007-2022 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
# データの探索
def search(node, x):
while node is not None:
if node.data == x: return True
if x < node.data:
node = node.left
else:
node = node.right
return False
# データの挿入
def insert(node, x):
if node is None: return Node(x)
p = node
while True:
if p.data == x: return node
elif x < p.data:
if p.left is None:
p.left = Node(x)
break
p = p.left
else:
if p.right is None:
p.right = Node(x)
break
p = p.right
return node
#
# データの削除
#
# データを探す
def _search(node, x):
pnode = None
while node is not None:
if node.data == x: return node, pnode
pnode = node
if x < node.data:
node = node.left
else:
node = node.right
return None, None
# 最小値を探す
def _search_min(node):
pnode = None
while node.left is not None:
pnode = node
node = node.left
return node, pnode
# 削除
def delete(root, x):
if root is None: return None # 空の木
node, pnode = _search(root, x) # 探索
if node is None: return root # 削除データなし
if node.left is not None and node.right is not None:
# 子が二つある場合
# 右部分木の最小値を探して置き換える
min_node, min_pnode = _search_min(node.right)
node.data = min_node.data
if min_pnode is not None:
pnode = min_pnode
node = min_node
else:
pnode = node
node = min_node
# 節を削除する
if node.left is None:
cnode = node.right
else:
cnode = node.left
if pnode is None:
return cnode # root の削除
elif pnode.left == node:
pnode.left = cnode
else:
pnode.right = cnode
return root
# 巡回
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