はじめに
AVL 木の続きです。前回はデータを挿入したあとで木のバランスを修正する処理を説明しました。今回はデータを削除したあとで木のバランスを修正する処理を詳しく説明します。
●データの削除
それでは AVL 木からデータを削除するとき、どのように木の構成を修正するのか見ていくことにしましょう。
二分木からデータを削除する場合、削除する節が葉の場合や子が一つしかない場合は簡単ですが、子が二つある場合はちょっと面倒です。この場合、削除するデータの右部分木から最小値のデータを探して、その値と交換します。そのようにしても、二分木の条件は崩れません。そして、最小値を格納していた節を削除します。この節は葉か右の子があるだけなので、削除するのは簡単です。詳しい説明は拙作のページ 二分木とヒープ をお読みください。
AVL 木でデータを削除する場合、データを削除する方法は二分木と同じですが、節を削除したあとで木のバランスをチェックします。節を挿入するときとは逆に、左部分木の節を削除したときは平衡度を一つ減らし、右部分木の節を削除するときは平衡度を一つ増やします。木のバランスをチェックする処理も、データ挿入時のバランスチェックとは異なります。
たとえば、平衡度が 0 の節から子を削除してみましょう。次の図を見てください。
節 E を削除します。E は親節 B の右の子なので、B の平衡度は一つ増えて 1 になります。この場合、B の木の高さは変化しないので、ここで木の修正は終了です。逆に、節 D を削除する場合も、B の平衡度は一つ減って -1 になりますが、木の高さは変化しないので、木の修正は終了です。挿入のときは、平衡度が 0 になったときに木の修正を終了しましたが、削除のときは平衡度が 0 から 1 または -1 になったときに木の修正を終了します。
次に、続けて節 D を削除します。次の図を見てください。
D は B の左の子なので、B の平衡度を一つ減らして 0 になります。このとき、B の木の高さが一つ減っていることに注目してください。つまり、平衡度が 0 になる場合は、その節の木の高さが一つ減るときなのです。この場合は、B の親節 A の平衡度をチェックします。B は A の左の子なので、A の平衡度は一つ減って 0 になります。この場合も A の高さが一つ減っているので、次は A の親節 P の平衡度をチェックします。
このように、平衡度が 0 になった場合は、親節の平衡度をチェックするのです。挿入処理とは異なり、平衡度が 0 になっても木の修正処理は終了しません。ご注意ください。
このあと根の方向に向かって平衡度が崩れていないかチェックしていきます。そして、平衡度が -2 または 2 になったら、左右の部分木の高さを修正します。
●木の修正
それでは、木の修正が必要な場合を考えていきましょう。次の図を見てください。
上図は節 A の左部分木 B の高さが一つ減って A の平衡度が -2 になった状態です。節 C の高さを h とすると、B の高さは h - 2 になります。この場合は C の平衡度によって処理を場合わけします。C の平衡度が 0 の場合は A を左回転します。節 D と E の高さは h - 1 なので、A の平衡度は右部分木 D の方が高くなり -1 となります。そして、C の平衡度は A の方が高くなるので 1 になります。これで木の修正は終わりになります。
C の平衡度が -1 の場合も A を左回転します。次の図を見てください。
この場合、B と D の高さは同じ (h - 2) になるので、A の平衡度は 0 で高さは h - 1 になります。A の高さは E と同じなので、C の平衡度は 0 で高さは h になります。この場合、さらに親節の平衡度をチェックする必要があります。
C の平衡度が 1 の場合は２重回転になります。次の図を見てください。
この場合は節 C を右回転してから節 A を左回転します。そして、平衡度の修正は節 D の平衡度により 3 通りに場合分けされます。これは挿入処理で２重回転を行ったとき、平衡度の修正処理と同じになります。
(a) は D の平衡度が 0 の場合です。F と G の高さが同じ (h - 2) なので、A, C, D の平衡度は 0 になります。(b) は D の平衡度が 1 の場合です。G の高さが一つ低いので、C の平衡度が -1 で、A と D の平衡度は 0 になります。(c) は D の平衡度が -1 の場合です。今度は F の高さが一つ低いので、A の平衡度が 1 になり、C と D の平衡度が 0 になります。どの場合も節 D の平衡度は 0 になるので、さらに親節の平衡度をチェックする必要があります。
右部分木が一つ低くなる場合も同様の処理になります。１重回転と２重回転の様子を下図に示します。
●プログラムの作成
それでは、データを削除する関数 delete を作成します。節を削除した場合、根の方に向かって平衡度をチェックしていく処理が必要になります。二分木では、データの削除を再帰呼び出しでプログラムしましたが、平衡度のチェックを組み込むには少々面倒なので、ループに展開することにします。単純なループでは、たどってきた経路がわからなくなるので、配列 path を用意して通過した節を記憶します。プログラムは次のようになります。
リスト : データの削除
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)
引数 root が None の場合は空の木なので削除するデータはありません。None を返します。経路は配列 path に格納します。次に、関数 _search() でデータ x を格納している節を探します。このとき、たどった節を path に格納します。path の要素は節と部分木の種別 (LEFT or Right) をタプルにまとめたものです。返り値が None の場合は x が見つからないので、root をそのまま返します。
削除する節 node に子が二つある場合は、右部分木 node.right から最小値を探して、node.data と置き換えます。最小値を格納している節は関数 _serach_min() で求めます。このときも、たどった節を path に格納します。_serach_min() を呼び出す前に、(node, RIGHT) を path に追加することをお忘れなく。そして、node.data の値を min_node.data に書き換えて、削除する節 node に min_node をセットします。
次は node を削除します。まず、node の親節と削除した部分木の種別を pnode と dir にセットします。そして、node の子を cnode にセットします。ここでは、node の子は多くても一つしかないことに注意してください。
もしも pnode が None であれば、ルートの節を削除するので cnode を返します。この場合、AVL 木は cnode だけしかありません。cnode が None であれば、最後のデータを削除したので空の木になります。どちらの場合でも、木のバランスを修正する必要はありません。そうでなければ、pnode の子を cnode に書き換えます。dir が LEFT であれば pnode.left に cnode をセットし、そうでなければ pnode.right に cnode をセットします。最後に、木のバランスをチェックする関数 balance_delete() を呼び出します。
次は、データを探索する関数 _search() と最小値を探す関数 _search_min() を作ります。次のリストを見てください。
リスト : データと最小値の探索
# データを探す
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
どちらの関数も繰り返しでプログラムしています。たどった経路を path に格納する処理を追加しただけなので、難しいところはないでしょう。
次は、木のバランスを修正する関数 balance_delete() を作ります。次のリストを見てください。
リスト : バランスの修正
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
path にデータがある間はバランスのチェックを行います。変数 new_node は回転操作した節 (部分木) をセットします。変数 pnode は平衡度をチェックする節、変数 dir は節を削除した部分木の種別を表します。path からデータを取り出して pnode と dir にセットします。dir が LEFT ならば pnode.balance を一つ減らし、RIGHT ならば一つ増やします。そして、平衡度を変数 b にセットします。
b が 1 よりも大きい場合は右部分木の高さが 2 つ低くなったので、木の修正を行います。pnode.left の平衡度が -1 の場合は２重回転を行います。pnode.left を左回転して、pnode を右回転します。回転した木は new_node にセットします。そして、平衡度を update_balance() で修正します。
pnode.left の平衡度が 0 か 1 の場合は１重回転を行います。pnode を右回転して new_node にセットします。new_node の平衡度が 0 の場合は、new_node.balance を -1 に、pnode.balance を 1 に書き換えます。そうでなければ、new_node と pnode の平衡度を 0 に書き換えます。
b が -1 よりも小さい場合は左部分木の高さが 2 つ低くなったので、木の修正を行います。pnode.right の平衡度が -1 の場合は２重回転を行います。pnode.right を右回転して、pnode を左回転します。回転した木は new_node にセットします。そして、平衡度を update_balance() で修正します。
pnode.right の平衡度が 0 か 1 の場合は１重回転を行います。pnode を左回転して new_node にセットします。new_node の平衡度が 0 の場合は、new_node.balance を 1 に、pnode.balance を -1 に書き換えます。そうでなければ、new_node と pnode の平衡度を 0 に書き換えます。
次に、b が 0 でない場合 (b == 1 または b == -1 の場合) は、修正は必要ないので break で while ループを脱出します。最後に root を返します。b が 0 の場合はバランスのチェックを続行することに注意してください。
次に、回転操作を行った場合は子の付け替え処理を行います。もしも、path にデータがなければ、new_node がルートになります。return で new_node を返します。次に、path より親節を取り出して gnode と gdir にセットします。gdir が LEFT の場合は gnode.left に、RIGTH の場合は gnode.right に new_node をセットします。そして、new_node の平衡度をチェックし、0 であればバランスのチェックを続行し、そうでなければ break で while ループを脱出して修正処理を終了します。
●データ削除のテスト
それでは、ここでデータ削除のテストを行ってみましょう。テストプログラムは次のようになります。
リスト : データ削除の簡単なテスト
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
for x in range(7):
a = avlnode.insert(a, x)
print_node(a, 0)
for x in range(7):
print('delete', x)
a = avlnode.delete(a, x)
print_node(a, 0)
print('-----')
実行結果を示します。
0
1
2
3
4
5
6
-----
delete 0
1
2
3
4
5
6
-----
delete 1
2
3
4
5
6
-----
delete 2
3
4
5
6
-----
delete 3
4
5
6
-----
delete 4
5
6
-----
delete 5
6
-----
delete 6
-----
このように、データを削除しても木のバランスは崩れません。
●AVLtree クラスの作成
最後に AVL 木を表すクラスを作成します。次のリストを見てください。
#
# avltree.py : AVL tree (平衡木)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import avlnode
# AVL 木
class AVLtree:
def __init__(self):
self.root = None
# 探索
def search(self, x):
return avlnode.search(self.root, x)
# 挿入
def insert(self, x):
self.root = avlnode.insert(self.root, x)
# 削除
def delete(self, x):
self.root = avlnode.delete(self.root, x)
# 巡回
def traverse(self):
for x in avlnode.traverse(self.root):
yield x
# 表示
def __str__(self):
if self.root is None: return 'AVLtree()'
buff = 'AVLtree('
for x in avlnode.traverse(self.root):
buff += '%s, ' % x
buff = buff.rstrip(', ')
buff += ')'
return buff
# テスト
if __name__ == '__main__':
import random
tree = AVLtree()
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)
クラス名は AVLtree としました。AVLtree のメソッドは avlnode の操作関数を呼び出すだけです。とくに難しいところはないでしょう。
それでは、テストの実行結果を示します。
$ python3 avltree.py [60, 20, 22, 31, 77, 59, 6, 66, 66, 2] AVLtree() AVLtree(2, 6, 20, 22, 31, 59, 60, 66, 77) search 60 True delete 60 search 60 False AVLtree(2, 6, 20, 22, 31, 59, 66, 77) search 20 True delete 20 search 20 False AVLtree(2, 6, 22, 31, 59, 66, 77) search 22 True delete 22 search 22 False AVLtree(2, 6, 31, 59, 66, 77) search 31 True delete 31 search 31 False AVLtree(2, 6, 59, 66, 77) search 77 True delete 77 search 77 False AVLtree(2, 6, 59, 66) search 59 True delete 59 search 59 False AVLtree(2, 6, 66) search 6 True delete 6 search 6 False AVLtree(2, 66) search 66 True delete 66 search 66 False AVLtree(2) search 66 False delete 66 search 66 False AVLtree(2) search 2 True delete 2 search 2 False AVLtree()
●AVL 木の評価
それでは、二分木と AVL 木の性能を比較してみましょう。次のリストを見てください。
リスト : 二分木と AVL 木のテスト
from bintree import *
from avltree 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 [BinaryTree, AVLtree]:
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() でデータを削除する時間を計測します。二分木のプログラム (node.py) は再帰呼び出しをループに展開したものを使いました。実行結果を示します。
表 : 実行結果 (単位 : 秒)
: Binary tree : AVL tree
個数 : 挿入 探索 削除 : 挿入 探索 削除
------+---------------------+--------------------
10000: 0.035 0.031 0.029 : 0.046 0.018 0.042
20000: 0.079 0.052 0.058 : 0.103 0.039 0.091
40000: 0.171 0.112 0.137 : 0.218 0.095 0.186
80000: 0.364 0.269 0.283 : 0.495 0.215 0.391
160000: 0.761 0.584 0.590 : 0.956 0.483 0.781
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
データの挿入と削除は二分木の方が速いですが、データの探索は AVL 木の方が速くなりました。AVL 木の効果は十分に出ていると思います。AVL 木はバランスを修正する分だけデータの挿入や削除には時間がかかりますが、そのかわりにデータの探索は高速になります。データの挿入や削除を行う回数が少なく、データの探索回数が多い場合は、AVL 木を使ってみるとよいかもしれません。
次はソート済みのデータで試してみましょう。データの個数は 1 / 10 にしてあります。実行結果は次のようになりました。
表 : ソート済みデータの実行結果 (単位 : 秒)
: Binary tree : AVL tree
個数 : 挿入 探索 削除 : 挿入 探索 削除
------+---------------------+---------------------
1000 : 0.066 0.068 0.001 : 0.004 0.001 0.003
2000 : 0.269 0.238 0.001 : 0.010 0.003 0.006
4000 : 1.074 0.911 0.002 : 0.017 0.006 0.011
8000 : 4.236 3.729 0.005 : 0.036 0.012 0.024
16000 :16.673 15.578 0.009 : 0.083 0.033 0.051
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
ソート済みデータの場合、二分木は線形探索と同じになるため、その性能は著しく劣化します。AVL 木は平衡木なので、ソート済みデータの場合でも性能は劣化しません。
なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●Appendix
ところで、今回のプログラムは節に平衡度を持たせました。この方法は GLib と同じですが、プログラムはけっこう複雑になります。もう少し簡単な実装方法はないか調べてみたところ、節に木の高さを持たせる方法がありました。木の高さから平衡度を求めるようにすると、プログラムはもう少し簡単になります。ただし、実行時間は遅くなってしまいました。
ご参考までに、プログラムリストと実行結果を示します。
表 : 実行結果 (単位 : 秒)
: BinaryTree : avlnode.py : avlnode1.py : avlnode2.py
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------+-------------------+-------------------+-------------------+-------------------
10000: 0.034 0.022 0.025 : 0.047 0.019 0.045 : 0.129 0.019 0.117 : 0.079 0.018 0.044
20000: 0.080 0.054 0.061 : 0.101 0.041 0.084 : 0.294 0.041 0.259 : 0.143 0.042 0.096
40000: 0.170 0.128 0.134 : 0.216 0.098 0.196 : 0.623 0.095 0.574 : 0.307 0.095 0.208
80000: 0.378 0.288 0.328 : 0.478 0.225 0.394 : 1.331 0.222 1.231 : 0.592 0.232 0.433
160000: 0.763 0.591 0.610 : 0.973 0.500 0.787 : 2.809 0.488 2.501 : 1.132 0.494 0.855
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
avlnode1.py は再帰版で、avlnode2.py は再帰を繰り返しに変換したものです。avlnode1.py は木の高さのチェックと修正をルートまで無条件に行っています。プログラムは簡単になるのですが、挿入と削除の実行時間は平衡度を使った方法 (avlnode.py) の 2 倍以上遅くなりました。
avlnode2.py は木の高さに変化がない場合は処理を終了するように工夫したものです。実行時間は avlnode1.py よりも速くなりましたが、それでも avlnode.py よりは遅くなります。AVL 木を実装する場合、実行速度の点では平衡度を使った方法が優れているようです。
なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●Appendix : プログラムリスト１
#
# avlnode1.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.height = 1 # 木の高さ
# 木の高さを求める
def get_height(node):
if node.left is not None:
a = node.left.height
else:
a = 0
if node.right is not None:
b = node.right.height
else:
b = 0
return max(a, b) + 1
# バランスを求める
def get_balance(node):
if node.left is not None:
a = node.left.height
else:
a = 0
if node.right is not None:
b = node.right.height
else:
b = 0
return a - b
# 右回転
def rotate_right(node):
lnode = node.left
node.left = lnode.right
lnode.right = node
node.height = get_height(node)
lnode.height = get_height(lnode)
return lnode
# 左回転
def rotate_left(node):
rnode = node.right
node.right = rnode.left
rnode.left = node
node.height = get_height(node)
rnode.height = get_height(rnode)
return rnode
# バランスが崩れていたら修正する
def balance(node):
if node is not None:
b = get_balance(node)
if b > 1:
if get_balance(node.left) < 0:
# LR 2 重回転
node.left = rotate_left(node.left)
return rotate_right(node)
elif b < -1:
if get_balance(node.right) > 0:
# RL 2 重回転
node.right = rotate_right(node.right)
return rotate_left(node)
# 修正不要
node.height = get_height(node)
return node
# 探索
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)
elif x == node.data: return node
elif x < node.data:
node.left = insert(node.left, x)
else:
node.right = insert(node.right, x)
return balance(node)
# 最小値を探す
def search_min(node):
if node.left is None: return node.data
return search_min(node.left)
# 最小値を削除する
def delete_min(node):
if node.left is None: return node.right
node.left = delete_min(node.left)
return balance(node)
# 削除
def delete(node, x):
if node is not None:
if x == node.data:
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
node.data = search_min(node.right)
node.right = delete_min(node.right)
elif x < node.data:
node.left = delete(node.left, x)
else:
node.right = delete(node.right, x)
return balance(node)
# 巡回
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
●Appendix : プログラムリスト２
#
# avlnode2.py : AVL 木の操作関数 (非再帰版)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
# 節の定義
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
self.height = 1 # 木の高さ
# 木の高さを求める
def get_height(node):
if node.left is not None:
a = node.left.height
else:
a = 0
if node.right is not None:
b = node.right.height
else:
b = 0
return max(a, b) + 1
# 平衡度を求める
def get_balance(node):
if node.left is not None:
a = node.left.height
else:
a = 0
if node.right is not None:
b = node.right.height
else:
b = 0
return a - b
# 右回転
def rotate_right(node):
lnode = node.left
node.left = lnode.right
lnode.right = node
node.height = get_height(node)
lnode.height = get_height(lnode)
return lnode
# 左回転
def rotate_left(node):
rnode = node.right
node.right = rnode.left
rnode.left = node
node.height = get_height(node)
rnode.height = get_height(rnode)
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
#
# データの挿入
#
LEFT = 0
RIGHT = 1
# バランスのチェック
def balance(root, path):
while len(path) > 0:
new_node = None
node, dir = path.pop()
h = get_height(node)
if h == node.height: return root # 高さに変化なし
b = get_balance(node)
if b > 1:
if get_balance(node.left) < 0:
# ２重回転
node.left = rotate_left(node.left)
new_node = rotate_right(node)
elif b < -1:
if get_balance(node.right) > 0:
# ２重回転
node.right = rotate_right(node.right)
new_node = rotate_left(node)
else:
node.height = h
if new_node is not None:
# 子の付け替え
if len(path) > 0:
# node の親節を求める
pnode, pdir = path[len(path) - 1]
if pdir == LEFT:
pnode.left = new_node
else:
pnode.right = new_node
else:
return new_node
return root
# 挿入
def insert(root, x):
if root is None: return Node(x)
path = []
p = root
while True:
if p.data == x: return root
elif x < p.data:
path.append((p, LEFT))
if p.left is None:
p.left = Node(x)
break
p = p.left
else:
path.append((p, RIGHT))
if p.right is None:
p.right = Node(x)
break
p = p.right
return balance(root, path)
# データを探す
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(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
改訂 2022 年 9 月 3 日