はじめに
赤黒木の続きです。前回はデータの挿入について説明しました。今回はデータの削除について詳しく説明します。
●データの削除
赤黒木の場合、二分木と同様にデータを削除して、そのあと赤黒木の条件を満たすように木のバランスを修正します。実際に削除される節は葉の場合か、子を一つだけ持っている場合です。もしも、削除する節が「赤」ならば簡単です。赤黒木の条件により、子を一つだけ持つ赤節は存在しないので、その赤節は葉であることがわかります。したがって、その節を削除するだけで OK です。黒高さに変化はないので、木のバランスを修正する必要もありません。
問題は黒節を削除する場合です。その黒節が子をひとつ持っている場合は簡単です。赤黒木は黒高さが一定になるので、黒節がひとつだけ子を持つ場合、その子は赤節しかありえません。次の図を見てください。
図 (A) でデータ 17 を削除します。図 (B) のように、削除する節 (17) とその子 (18) を置き換えたあと、節 (18) の色を黒に塗り替えるだけで赤黒木の条件を満たすことができます。
簡単なのはここまでです。たとえば、図 (A) で節 (15) を削除する場合を考えてみましょう。削除する黒節は「葉」なので、節 (16) の左部分木の黒高さがひとつ低くなりますね。この場合、木のバランスを修正するため回転操作が必要になります。図 (A) では、節 (16) 以下の部分木を左回転すれば、赤黒木の条件を満たすことができます。
この例では簡単に木のバランスを修正できますが、実際には削除する節の親、兄弟、兄弟の子の「色」によって場合分けが必要になります。これをそのままプログラムすると大変なのですが、木を回転するときに色の付け替えを行うと、場合分けを簡略化することができます。これにより、プログラムは少しですが簡単になります。
●バランスの修正
赤黒木の場合、データを挿入するときは回転操作により黒節と黒節の間に赤節を挿入することで、木のバランスを修正しました。データを削除する場合、黒高さが一つ低くなった部分木に回転操作で節を挿入して、黒高さが同じになるように節の色を塗り替える、というのが基本的な考え方です。
具体的には、削除する節の親、兄弟、兄弟の子から赤節を探して、回転操作と色の塗り替えにより木のバランスを修正します。たとえば、黒節を一つ削除して、左部分木の黒高さが一つ低くなった場合を考えてみます。この場合、次に示す 9 通りのパターンがあります。
上図は、部分木 X の黒高さが -1 になる場合です。この場合、節 X の色は黒になります。たとえば、黒節 (葉) を削除した場合、終端を表す節 null が節 X に相当しますが、null の色を黒とすれば上図で表すことができます。そして、X 以外の節 Y, Z, A, B の中でひとつでも赤節があれば、回転操作と色の塗り替えにより木のバランスを修正することができます。
逆にいえば、上図 (1) のように節 Y, Z, A, B がすべて黒節の場合、木のバランスは修正できません。この場合、節 Z 以下の右部分木の黒高さを左部分木と同じに揃えて、節 Y の親節で木のバランスを修正します。次の図を見てください。
節 Z の色を赤に塗り替えれば、右部分木の黒高さはひとつ低くなります。これで、左右の部分木の黒高さを同じに揃えることができます。つまり、部分木 Y の黒高さが一つ低くなるわけです。あとは、節 Y の親節で木のバランスを修正します。もしも、節 Y がルートであれば、これで木の修正は終わりです。この操作で、赤黒木の黒高さは一つ低くなります。
次はパターン (2) の修正を説明します。次の図を見てください。
パターン (2) は節 Y だけが赤節で、節 Z, A, B が黒節の場合です。この場合は、節 Y と Z の色を塗り替えるだけで、木のバランスを修正できます。節 Y を黒に塗り替えると左右の部分木の黒高さは +1 されますが、節 Z を赤に塗り替えることで右部分木の黒高さが -1 されるので、左部分木だけ黒高さを +1 することができます。
節 Y は赤節なので、その親節は赤黒木の条件により必ず黒節になります。したがって、節 Y の色を黒に塗り替えても、赤黒木の条件を満たしているので大丈夫です。
次はパターン (3) の修正を説明します。次の図を見てください。
パターン (3) は節 Z だけが赤節で、節 Y, A, B が黒節の場合です。この場合、部分木 Y を左回転します。このとき、節 Y, Z の色が塗り替えられることに注意してください。すると、節 A と B の黒高さは同じままなので、赤節 Y の左部分木 X の黒高さが -1 になった場合に変換することができます。あとは、節 Y が「赤」のパターン (2), (7), (8), (9) を適用して、木のバランスを修正します。
次は節 B が「赤」のパターン (5), (6), (8), (9) の修正を説明します。次の図を見てください。
パターン (5), (6) は節 Y, Z が黒節で、節 B が赤節の場合です。この場合、部分木 Y を左回転すると、節 Y の色は赤になります。その後、節 Y, B の色を「黒」に塗り替えます。経路 Y - Z - B は Y - B になりますが、節 B が「黒」になったので節 B の黒高さは同じままです。経路 Y - Z - A は Z - Y - A と順番が変わるだけなので、節 A の黒高さは同じままです。経路 Y - X は Z - Y - X になり、黒節 Z が挿入されるので、節 X の黒高さは +1 されます。
パターン (8), (9) も同様に、部分木 Y を左回転します。すると、節 Z, Y の色は赤になります。その後、節 B, Y を「黒」に塗り替えます。経路 Y - X は Z - Y - X になり、黒節 Y が挿入されるので、節 X の黒高さは +1 されます。ほかの節の黒高さは同じままです。これで木のバランスは修正されます。けっきょく、(5), (6), (8), (9) は部分木を左回転して節 B, Y の色を黒に塗り替えることで木のバランスを修正することができます。
最後に、節 B が「黒」で節 A が「赤」のパターン (4), (7) の修正を説明します。次の図を見てください。
パターン (4) は節 A が赤節で、節 Y, Z, B が黒節の場合です。パターン (7) は節 A, Y が赤節で、節 Z, B が黒節の場合です。どちらの場合も、部分木 Z を右回転すると節 A, Z の色が塗り替えられるので、(4) ならばパターン (5), (6) に、(7) ならばパターン (8), (9) に変換することができます。つまり、(4) - (9) のパターンは、A が赤ならば Z を右回転しておいて、あとは Y を左回転して Y, B を黒に塗り替えればいいわけです。
このように、9 通りのパターンを 3 通りの修正パターンに場合分けすることができます。実際には、左部分木だけではなく右部分木の黒高さが -1 になる場合もあるので、全部で 6 通りのパターンになります。
●プログラムの作成
それでは、データを削除する関数 delete() を作成します。プログラムは次のようになります。
リスト : データの削除
# 最小値を探す
def search_min(node):
while node.left is not null: node = node.left
return node.data
# 削除
def delete(node, x):
if node is null: return node, True
if x == node.data:
if node.left is null and node.right is null:
return null, node.color == RED
elif node.right is null:
node.left.color = BLACK
return node.left, True
elif node.left is null:
node.right.color = BLACK
return node.right, True
else:
node.data = search_min(node.right)
node.right, flag = delete(node.right, node.data)
return balance_right(node, flag)
elif x < node.data:
node.left, flag = delete(node.left, x)
return balance_left(node, flag)
else:
node.right, flag = delete(node.right, x)
return balance_right(node, flag)
delete() は木 node から x と等しいデータを削除します。delete() は x を削除した部分木とフラグを返します。フラグが True の場合、バランスを修正する必要はありません。False の場合は木のバランスを修正します。
x と等しいデータが見つかった場合は左右の子の有無をチェックします。node が葉の場合は null を返します。このとき、node が赤節ならば木のバランスを修正する必要はありませんが、黒節の場合は修正する必要があります。
子が一つしかない場合は、node が黒節で子が赤節になります。子の色を黒に塗り替えてから返します。この場合、木のバランスを修正する必要はありません。子が二つある場合は、右部分木の最小値と置き換えてから、右部分木の最小値を削除します。右部分木からデータを削除したあと、関数 balance_right() で木のバランスを修正します。
あとは、左部分木をたどったら関数 balance_left() で木のバランスを修正し、右部分木をたどったら balance_right() で木のバランスを修正します。
●バランスの修正処理
次は、黒節を削除したとき、木のバランスを修正する処理を説明します。次のリストを見てください。
リスト : 黒節を削除したときの修正
# 左部分木の修正
def balance_left(node, flag):
if flag: return node, flag
if node.right.left.color == BLACK and node.right.right.color == BLACK:
# (1), (2)
if node.right.color == BLACK:
node.right.color = RED
if node.color == BLACK: return node, False
node.color = BLACK
else:
# (3)
node = rotate_left(node)
node.left, _ = balance_left(node.left, False)
else:
# (4), (7)
if node.right.left.color == RED:
node.right = rotate_right(node.right)
# (5), (6), (8), (9)
node = rotate_left(node)
node.left.color = BLACK
node.right.color = BLACK
return node, True
引数の flag が False の場合、木のバランスを修正します。node の右部分木 (node.right) の孫節が 2 つとも黒ならばパターン (1), (2), (3) の場合です。そして、node.right が黒節ならば (1), (2) の場合です。node.right の色を赤に塗り替えて、(1) ならば node, False を返し、(2) ならば node を赤に塗り替えます。そうでなければ (3) の場合です。node を左回転してから、node.left に対して木のバランスを修正します。これは balance_left() を再帰呼び出しするだけです。
パターン (4) - (9) の場合は、まず (4) と (7) のパターンかチェックします。そうであれば、右部分木 node.right を右回転します。あとは node を左回転して、node.left と node.right を黒に塗り替えるだけです。最後に node, True を返します。
右部分木のバランスを修正する関数 balance_right() は、子のチェックと木の回転操作が左右対称になるだけなので、説明は割愛いたします。詳細は プログラムリスト をお読みください。
●データ削除のテスト
それでは、ここでデータ削除のテストを行ってみましょう。テストプログラムは次のようになります。
リスト : データ削除の簡単なテスト
# 木の表示
def print_node(node, n):
color = ('B', 'R')
if node is not null:
print_node(node.left, n + 1)
print(' ' * n, color[node.color], node.data)
print_node(node.right, n + 1)
# 赤黒木の条件を満たしているか
def check_rbtree(node):
if node is not null:
if node.color == RED:
if node.left.color == RED or node.right.color == RED:
raise 'rbtree error1'
a = check_rbtree(node.left)
b = check_rbtree(node.right)
if a != b: raise 'rbtree error2'
if node.color == BLACK: a += 1
return a
return 0
# test
if __name__ == '__main__':
import random
root = make_null()
buff = range(8)
print('insert test')
for x in buff:
print('----- insert', x)
root, _ = insert(root, x)
root.color = BLACK
print_node(root, 0)
check_rbtree(root)
print('search test')
for x in buff:
if not search(root, x):
raise 'search error'
print('delete test')
for x in buff:
print('----- delete', x)
root, _ = delete(root, x)
print_node(root, 0)
check_rbtree(root)
実行結果を示します。
B 0
R 1
B 2
B 3
B 4
R 5
B 6
R 7
-----
delete 0
B 1
R 2
B 3
B 4
R 5
B 6
R 7
-----
delete 1
B 2
B 3
B 4
R 5
B 6
R 7
-----
delete 2
B 3
R 4
B 5
B 6
R 7
-----
delete 3
B 4
B 5
B 6
R 7
-----
delete 4
B 5
B 6
B 7
-----
delete 5
B 6
R 7
-----
delete 6
B 7
-----
delete 7
このように、データを削除しても赤黒木のバランスが大きく崩れることはありません。
●RBtree クラスの作成
最後に赤黒木を表すクラスを作成します。次のリストを見てください。
#
# rbtree.py : Red-Black tree (赤黒木)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import rbnode
# 赤黒木
class RBtree:
def __init__(self):
self.root = rbnode.make_null()
# 探索
def search(self, x):
return rbnode.search(self.root, x)
# 挿入
def insert(self, x):
self.root, _ = rbnode.insert(self.root, x)
self.root.color = rbnode.BLACK
# 削除
def delete(self, x):
self.root, _ = rbnode.delete(self.root, x)
self.root.color = rbnode.BLACK
# 巡回
def traverse(self):
for x in rbnode.traverse(self.root):
yield x
# 表示
def __str__(self):
if self.root is rbnode.null: return 'RBtree()'
buff = 'RBtree('
for x in rbnode.traverse(self.root):
buff += '%s, ' % x
buff = buff.rstrip(', ')
buff += ')'
return buff
# テスト
if __name__ == '__main__':
import random
tree = RBtree()
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)
クラス名は RBtree としました。RBtree のメソッドはモジュール rbnode の操作関数を呼び出すだけです。メソッド __init__() で root を初期化するとき、モジュール rbnode の関数 make_null() を呼び出して、終端オブジェクトを設定することに注意してください。あとは、とくに難しいところはないでしょう。
それでは、テストの実行結果を示します。
$ python3 rbtree.py [95, 40, 0, 85, 77, 53, 89, 96, 38, 76] RBtree() RBtree(0, 38, 40, 53, 76, 77, 85, 89, 95, 96) search 95 True delete 95 search 95 False RBtree(0, 38, 40, 53, 76, 77, 85, 89, 96) search 40 True delete 40 search 40 False RBtree(0, 38, 53, 76, 77, 85, 89, 96) search 0 True delete 0 search 0 False RBtree(38, 53, 76, 77, 85, 89, 96) search 85 True delete 85 search 85 False RBtree(38, 53, 76, 77, 89, 96) search 77 True delete 77 search 77 False RBtree(38, 53, 76, 89, 96) search 53 True delete 53 search 53 False RBtree(38, 76, 89, 96) search 89 True delete 89 search 89 False RBtree(38, 76, 96) search 96 True delete 96 search 96 False RBtree(38, 76) search 38 True delete 38 search 38 False RBtree(76) search 76 True delete 76 search 76 False RBtree()
●赤黒木の評価
それでは、AVL 木、2-3 木、赤黒木の性能を比較してみましょう。次のリストを見てください。
リスト : AVL 木、2-3 木、赤黒木のテスト
from avltree import *
from tree23 import *
from rbtree 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, Tree23, RBtree]:
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 : 2-3 tree : red-black tree
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------------------------------------------------------------------------
10000: 0.051 0.018 0.045 : 0.043 0.018 0.041 : 0.052 0.019 0.047
20000: 0.117 0.046 0.085 : 0.092 0.043 0.082 : 0.111 0.041 0.111
40000: 0.228 0.090 0.194 : 0.189 0.094 0.182 : 0.249 0.098 0.246
80000: 0.466 0.212 0.410 : 0.408 0.224 0.393 : 0.530 0.228 0.520
160000: 0.959 0.472 0.788 : 0.868 0.504 0.813 : 1.123 0.497 1.036
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
赤黒木の場合、データの探索は AVL 木や2-3 木と同じくらい高速ですが、データの挿入と削除には少しだけ時間がかかるようです。平衡木を構築する場合、回転操作が不要な分だけ 2-3 木の方が速くなるようです。
次はソート済みのデータで試してみましょう。実行結果は次のようになりました。
表 : ソート済みデータの実行結果 (単位 : 秒)
: AVL tree : 2-3 tree : red-black tree
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------+---------------------+---------------------+---------------------
10000: 0.049 0.016 0.033 : 0.045 0.017 0.033 : 0.079 0.020 0.041
20000: 0.115 0.035 0.077 : 0.101 0.037 0.071 : 0.168 0.038 0.087
40000: 0.208 0.075 0.142 : 0.224 0.081 0.149 : 0.354 0.079 0.193
80000: 0.424 0.166 0.273 : 0.444 0.168 0.318 : 0.739 0.176 0.394
160000: 0.801 0.334 0.523 : 0.872 0.358 0.612 : 1.478 0.344 0.781
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
ソート済みデータの場合、赤黒木はデータの挿入に時間がかかります。2-3 木はデータの挿入に少しだけ時間がかかるようになりますが、赤黒木ほど遅くなりません。AVL 木は乱数データよりも速くなりました。AVL 木はソート済みデータでも苦にしないようです。データの探索は、どの平衡木でも少し速くなりました。赤黒木の場合、データの探索も遅くなると思っていたので、この結果にはちょっと驚きました。データの削除は AVL 木が最も速くなりました。
この結果を見ると、AVL 木は赤黒木よりも性能が大きく劣るものではなく、十分実用になる平衡木だと思います。歴史的な価値だけではなく、実用的な平衡木としてもっと評価されてもよいのではないかと思いました。なお、拙作のページ AVL 木 [2] の Appendix で説明したように、AVL 木の性能はプログラムの実装方法で大きく変わります。木の高さを使った実装では、実行速度がとても遅くなります。ご注意くださいませ。
また、2-3 木の性能も AVL 木や赤黒木に劣るものではなく、実用的に使える優れた平衡木だと思います。ただし、今回作成した 2-3 木のように、多分木は二分木よりも記憶領域を多く使用する (記憶領域がムダになる) という欠点があります。多分木をベースにした平衡木、たとえば B 木は外部記憶にむいた優れた平衡木で、その改良版である B* 木や B+ 木はファイルシステムやデータベースなどで利用されています。
なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●参考文献, URL
改訂 2022 年 9 月 3 日