前回は 2-3 木をベースにした Left-Leaning Red Black Tree (LLRB 木) を作成しました。LLRB 木の場合、赤節は黒節の左の子にしかなれません。今回は黒節の右の子にも赤節を許す赤黒木を作ってみましょう。
データ挿入の基本的な考え方は簡単です。通常の赤黒木のようにデータを挿入しますが、左右の子がともに赤節になったならば、その節を分割して親節で木のバランスを修正します。プログラムの作成は簡単で、赤黒木 [1] のプログラムを少し修正するだけです。左部分木のバランスを修正する関数 balance_insert_left() は次のようになります。
リスト : データの挿入
# 4node の分割
def split(node):
node.color = RED
node.left.color = BLACK
node.right.color = BLACK
# 左部分木の修正
def balance_insert_left(node, flag):
if flag: return node, flag
if node.color == BLACK:
if node.right.color == RED:
# 4 node なので分割
split(node)
else:
if node.left.right.color == RED:
node.left = rotate_left(node.left)
if node.left.left.color == RED:
# 赤が 2 つ続く
node = rotate_right(node)
# 4 node になるので分割
split(node)
else:
# 赤一つならば終了
flag = True
return node, flag
# データの挿入
def insert(node, x):
if node is null: return Node(x), False
if x < node.data:
node.left, flag = insert(node.left, x)
return balance_insert_left(node, flag)
elif x > node.data:
node.right, flag = insert(node.right, x)
return balance_insert_right(node, flag)
return node, True
balance_insert_left() でバランスを修正する場合、node.left は赤節になります。最初に、右の子 (node.right) が赤節かチェックします。そうであれば、左右の子が赤になるので、split() で節を分割して node の親節でバランスを修正します。
右の子が黒節ならば、node.left の子に赤節がないかチェックします。この処理は赤黒木 [1] のプログラムと同じですが、左右の子が赤節になった場合は split() で node を分割する処理を追加します。赤節が node.left の一つだけならば、木のバランスを修正する必要はありません。
右部分木のバランスを修正する関数 balance_lnsert_right() は、子のチェックと回転操作が左右対称になるだけなので説明は割愛いたします。詳細はプログラムリストをお読みください。
ところで、データの挿入処理は次のようにプログラムすることもできます。
リスト : データの挿入 (2-3 木版)
# 簡単な実装方法
def insert1(node, x):
if node is null: return Node(x)
# 木をたどる
if x < node.data:
node.left = insert1(node.left, x)
elif x > node.data:
node.right = insert1(node.right, x)
# バランスの修正
# 左の子をチェック
if node.left.color == RED:
if node.left.right.color == RED:
node.left = rotate_left(node.left)
if node.left.left.color == RED:
node = rotate_right(node)
# 右の子をチェック
if node.right.color == RED:
if node.right.left.color == RED:
node.right = rotate_right(node.right)
if node.right.right.color == RED:
node = rotate_left(node)
# 4 node の分割
if node.left.color == RED and node.right.color == RED:
split(node)
return node
左右の子で赤節が 2 つ続いているかチェックし、そうであれば木を回転してバランスを修正します。そのあとで左右の子がともに赤節ならば split() で分割します。また、参考文献 "Left-Leaning Red Black Trees" によると、木をたどるときに 4 node の分割処理を行うと、通常の赤黒木の挿入処理になります。
リスト : データの挿入 (2-3-4 木版)
# 簡単な実装方法
def insert1(node, x):
if node is null: return Node(x)
# 4 node の分割
if node.left.color == RED and node.right.color == RED:
split(node)
# 木をたどる
if x < node.data:
node.left = insert1(node.left, x)
elif x > node.data:
node.right = insert1(node.right, x)
# バランスの修正
# 左の子をチェック
if node.left.color == RED:
if node.left.right.color == RED:
node.left = rotate_left(node.left)
if node.left.left.color == RED:
node = rotate_right(node)
# 右の子をチェック
if node.right.color == RED:
if node.right.left.color == RED:
node.right = rotate_right(node.right)
if node.right.right.color == RED:
node = rotate_left(node)
return node
このように、とても簡単にプログラムできるのですが、実行速度はどちらのプログラムも LLRB 木より少し遅くなるようです。興味のある方は試してみてください。
それでは、ここでデータ挿入のテストを行ってみましょう。テストプログラムは次のようになります。
リスト : データ挿入の簡単なテスト
# 木の表示
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_rb23tree(node):
if node is not null:
if node.color == RED:
if node.left.color == RED or node.right.color == RED:
raise 'rb23 error1'
else:
if node.left.color == RED and node.right.color == RED:
raise 'rb23 error2'
a = check_rb23tree(node.left)
b = check_rb23tree(node.right)
if a != b: raise 'rb23 error3'
if node.color == BLACK: a += 1
return a
return 0
# test
if __name__ == '__main__':
import random, time
root = make_null()
buff = range(8)
print('insert test')
for x in buff:
print('----- insert', x)
root = insert1(root, x)
root.color = BLACK
print_node(root, 0)
check_rb23tree(root)
print_node() は赤黒木を表示する関数です。黒節は B を、赤節は R をつけて表しています。終端は None ではなく null なので、node と null を比較していることに注意してください。
関数 check_rb23tree() は赤黒木の条件をチェックする関数です。node が赤節の場合、その子が赤節であればエラーを送出します。node が黒節の場合、左右の子がともに赤節の場合もエラーを送出します。check_rb23tree() の返り値は黒高さです。左右の部分木の黒高さを求め、それが等しくない場合はエラーを送出します。
insert test
----- insert 0
B 0
----- insert 1
B 0
R 1
----- insert 2
B 0
B 1
B 2
----- insert 3
B 0
B 1
B 2
R 3
----- insert 4
B 0
B 1
B 2
R 3
B 4
|
----- insert 5
B 0
B 1
B 2
R 3
B 4
R 5
----- insert 6
B 0
B 1
B 2
B 3
B 4
B 5
B 6
----- insert 7
B 0
B 1
B 2
B 3
B 4
B 5
B 6
R 7
|
テストは 0 から 7 までの整数値を順番に赤黒木に挿入します。実行結果は上図のようになります。どの経路でも黒高さが同じになっていることがすぐにわかると思います。また、赤節は黒節の左右のどちらかにしか存在しません。これが 2-3 木をベースにした赤黒木の特徴です。
今度は木の高さを比較してみましょう。テストプログラムは次のようになります。
リスト : データ挿入の簡単なテスト (2)
import node
import avlnode
import rbnode
import rb23node
import llrb23node
import random
# 木の高さを求める
def get_height(node, term = None):
if node is not term:
a = get_height(node.left)
b = get_height(node.right)
return max(a, b) + 1
return 0
for n in [1000, 2000, 4000, 8000, 16000, 32000]:
a = None
b = rbnode.make_null()
c = rb23node.make_null()
d = llrb23node.make_null()
buff = list(range(n))
random.shuffle(buff)
for x in buff:
a = avlnode.insert(a, x)
b, _ = rbnode.insert(b, x)
b.color = rbnode.BLACK
c, _ = rb23node.insert(c, x)
c.color = rb23node.BLACK
d, _ = llrb23node.insert1(d, x)
d.color = llrb23node.BLACK
print(n, get_height(a), get_height(b, rbnode.null), \
get_height(c, rb23node.null), get_height(d, llrb23node.null))
それでは、実行結果を示します。
表 : 木の高さ
N : AVL RB RB23 LLRB
---------------------------
1000 : 12 12 12 13
2000 : 13 14 14 16
4000 : 14 15 15 16
8000 : 16 16 16 18
16000 : 16 17 17 19
32000 : 18 18 19 21
RB は赤黒木 (2-3-4 木) で、RB23 は今回作成した赤黒木 (2-3 木) です。木の高さは AVL 木 < RB 木 < RB23 木 < LLRB 木になりました。
次はソート済みデータで試してみましょう。結果は次のようになりました。
表 : 木の高さ
(a) 昇順
N : AVL RB RB23 LLRB
---------------------------
1000 : 10 17 15 10
2000 : 11 19 16 11
4000 : 12 21 17 12
8000 : 13 23 18 13
16000 : 14 25 19 14
32000 : 15 27 20 15
(b) 逆順 N : AVL RB RB23 LLRB --------------------------- 1000 : 10 17 15 15 2000 : 11 19 16 16 4000 : 12 21 17 17 8000 : 13 23 18 18 16000 : 14 25 19 19 32000 : 15 27 20 20
ソート済みデータの場合、木の高さは RB 木よりも RB23 木の方が低くなりました。これらの結果を見ると、2-3 木をベースにした赤黒木でも十分な性能が得られるように思います。
データの削除は赤黒木 [2] のプログラムをそのまま使用することができます。それでは、ここでデータ削除のテストを行ってみましょう。テストプログラムは次のようになります。
リスト : データ削除の簡単なテスト
# test
if __name__ == '__main__':
import random, time
root = make_null()
buff = range(8)
print('insert test')
for x in buff:
root = insert(root, x)
root.color = BLACK
check_rb23tree(root)
print('delete test')
print_node(root, 0)
for x in buff:
print('----- delete ', x)
root, _ = delete(root, x)
root.color = BLACK
print_node(root, 0)
check_rb23tree(root)
実行結果を示します。
B 0
B 1
B 2
B 3
B 4
B 5
B 6
R 7
delete test
----- 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
このように、データを削除しても赤黒木のバランスが大きく崩れることはありません。
最後に赤黒木を表すクラスを作成します。次のリストを見てください。
#
# rb23tree.py : 赤黒木 (2-3 木をベース)
#
# Copyright (C) 2009-2022 Makoto Hiroi
#
import rb23node
# 赤黒木
class RB23tree:
def __init__(self):
self.root = rb23node.make_null()
# 探索
def search(self, x):
return rb23node.search(self.root, x)
# 挿入
def insert(self, x):
self.root, _ = rb23node.insert(self.root, x)
self.root.color = rb23node.BLACK
# 削除
def delete(self, x):
self.root, _ = rb23node.delete(self.root, x)
self.root.color = rb23node.BLACK
# 巡回
def traverse(self):
for x in rb23node.traverse(self.root):
yield x
# 表示
def __str__(self):
if self.root is rb23node.null: return 'RB23tree()'
buff = 'RB23tree('
for x in rb23node.traverse(self.root):
buff += '%s, ' % x
buff = buff.rstrip(', ')
buff += ')'
return buff
# テスト
if __name__ == '__main__':
import random
tree = RB23tree()
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)
クラス名は RB23tree としました。RB23tree のメソッドはモジュール rb23node の操作関数を呼び出すだけです。メソッド __init__() で root を初期化するとき、モジュール rb23node の関数 make_null() を呼び出して、終端オブジェクトを設定することに注意してください。あとは、とくに難しいところはないでしょう。
それでは、テストの実行結果を示します。
[21, 64, 51, 35, 94, 17, 89, 35, 99, 98] RB23tree() RB23tree(17, 21, 35, 51, 64, 89, 94, 98, 99) search 21 True delete 21 search 21 False RB23tree(17, 35, 51, 64, 89, 94, 98, 99) search 64 True delete 64 search 64 False RB23tree(17, 35, 51, 89, 94, 98, 99) search 51 True delete 51 search 51 False RB23tree(17, 35, 89, 94, 98, 99) search 35 True delete 35 search 35 False RB23tree(17, 89, 94, 98, 99) search 94 True delete 94 search 94 False RB23tree(17, 89, 98, 99) search 17 True delete 17 search 17 False RB23tree(89, 98, 99) search 89 True delete 89 search 89 False RB23tree(98, 99) search 35 False delete 35 search 35 False RB23tree(98, 99) search 99 True delete 99 search 99 False RB23tree(98) search 98 True delete 98 search 98 False RB23tree()
最後に、赤黒木 (2-3-4木)、LLRB 木、赤黒木 (2-3 木) の性能を比較してみましょう。次のリストを見てください。
リスト : 赤黒木 (2-3-4 木)、LLRB 木、赤黒木 (2-3 木) のテスト
from llrb23tree import *
from rbtree import *
from rb23tree 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 [RBtree, LLRB23tree, RB23tree]:
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() でデータを削除する時間を計測します。結果は次のようになりました。
表 : 実行結果 (単位 : 秒)
: RB tree : LLRB tree : RB23 tree
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------------------------------------------------------------------------
10000: 0.054 0.018 0.048 : 0.063 0.020 0.056 : 0.054 0.019 0.047
20000: 0.134 0.042 0.100 : 0.129 0.041 0.109 : 0.110 0.042 0.102
40000: 0.259 0.097 0.235 : 0.299 0.101 0.251 : 0.239 0.098 0.233
80000: 0.568 0.223 0.504 : 0.653 0.228 0.515 : 0.526 0.224 0.500
160000: 1.131 0.486 0.997 : 1.384 0.502 1.052 : 1.068 0.498 0.999
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
通常の赤黒木と同様に、2-3 木をベースにした赤黒木も高速ですね。
次はソート済みのデータで試してみましょう。実行結果は次のようになりました。
表 : ソート済みデータの実行結果 (単位 : 秒)
(a) 昇順
: RB tree : LLRB tree : RB23 tree
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------------------------------------------------------------------------
10000: 0.091 0.017 0.045 : 0.062 0.016 0.056 : 0.066 0.017 0.040
20000: 0.193 0.044 0.085 : 0.129 0.035 0.121 : 0.148 0.039 0.086
40000: 0.365 0.079 0.184 : 0.287 0.074 0.256 : 0.301 0.084 0.319
80000: 0.797 0.177 0.406 : 0.670 0.228 0.648 : 0.803 0.189 0.399
160000: 1.539 0.342 0.783 : 1.117 0.333 1.143 : 1.259 0.360 0.807
(b) 逆順
: RB tree : LLRB tree : RB23 tree
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------------------------------------------------------------------------
10000: 0.078 0.017 0.044 : 0.073 0.020 0.043 : 0.064 0.017 0.047
20000: 0.171 0.036 0.098 : 0.157 0.038 0.092 : 0.132 0.036 0.087
40000: 0.333 0.082 0.186 : 0.345 0.080 0.191 : 0.278 0.086 0.188
80000: 0.708 0.165 0.419 : 0.718 0.170 0.401 : 0.565 0.165 0.396
160000: 1.383 0.351 0.774 : 1.413 0.362 0.813 : 1.116 0.349 0.802
ソート済みデータの場合、データの挿入は RB 木よりも RB23 木の方が速くなりました。これらの結果を見ると、2-3 木をベースにした赤黒木でも十分な性能が得られることがわかります。
なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
#
# rb23node.py : 赤黒木用操作関数 (2-3 木をベース)
#
# Copyright (C) 2009-2022 Makoto Hiroi
#
# 終端
null = None
# 色
BLACK = 0
RED = 1
# 節
class Node:
def __init__(self, x, color = RED):
self.data = x
self.color = color
self.left = null
self.right = null
# 終端の設定
def make_null():
global null
if null is None:
null = Node(None, BLACK)
null.left = None
null.right = None
return null
# 右回転
def rotate_right(node):
lnode = node.left
node.left = lnode.right
lnode.right = node
lnode.color = node.color
node.color = RED
return lnode
# 左回転
def rotate_left(node):
rnode = node.right
node.right = rnode.left
rnode.left = node
rnode.color = node.color
node.color = RED
return rnode
#
# データの探索
#
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
#
# データの挿入
#
# 4node の分割
def split(node):
node.color = RED
node.left.color = BLACK
node.right.color = BLACK
# 左部分木の修正
def balance_insert_left(node, flag):
if flag: return node, flag
if node.color == BLACK:
if node.right.color == RED:
# 4 node なので分割
split(node)
else:
if node.left.right.color == RED:
node.left = rotate_left(node.left)
if node.left.left.color == RED:
# 赤が 2 つ続く
node = rotate_right(node)
# 4 node になるので分割
split(node)
else:
# 赤一つならば終了
flag = True
return node, flag
# 右部分木の修正
def balance_insert_right(node, flag):
if flag: return node, flag
if node.color == BLACK:
if node.left.color == RED:
# 4 node なので分割
split(node)
else:
if node.right.left.color == RED:
node.right = rotate_right(node.right)
if node.right.right.color == RED:
# 赤が 2 つ続く
node = rotate_left(node)
# 4node になるので分割
split(node)
else:
# 赤一つならば終了
flag = True
return node, flag
# データの挿入
def insert(node, x):
if node is null: return Node(x), False
if x < node.data:
node.left, flag = insert(node.left, x)
return balance_insert_left(node, flag)
elif x > node.data:
node.right, flag = insert(node.right, x)
return balance_insert_right(node, flag)
return node, True
# 簡易バージョン (遅い)
def insert1(node, x):
if node is null: return Node(x)
if x < node.data:
node.left = insert1(node.left, x)
elif x > node.data:
node.right = insert1(node.right, x)
# バランスの修正
if node.left.color == RED:
if node.left.right.color == RED:
node.left = rotate_left(node.left)
if node.left.left.color == RED:
node = rotate_right(node)
if node.right.color == RED:
if node.right.left.color == RED:
node.right = rotate_right(node.right)
if node.right.right.color == RED:
node = rotate_left(node)
if node.left.color == RED and node.right.color == RED:
split(node)
return node
#
# データの削除
#
# 右部分木の修正
def balance_right(node, flag):
if flag: return node, flag
if node.left.left.color == BLACK and node.left.right.color == BLACK:
if node.left.color == BLACK:
node.left.color = RED
if node.color == BLACK: return node, False
node.color = BLACK
else:
node = rotate_right(node)
node.right, _ = balance_right(node.right, False)
else:
if node.left.right.color == RED:
node.left = rotate_left(node.left)
node = rotate_right(node)
node.right.color = BLACK
node.left.color = BLACK
return node, True
# 左部分木の修正
def balance_left(node, flag):
if flag: return node, flag
if node.right.left.color == BLACK and node.right.right.color == BLACK:
if node.right.color == BLACK:
node.right.color = RED
if node.color == BLACK: return node, False
node.color = BLACK
else:
node = rotate_left(node)
node.left, _ = balance_left(node.left, False)
else:
if node.right.left.color == RED:
node.right = rotate_right(node.right)
node = rotate_left(node)
node.left.color = BLACK
node.right.color = BLACK
return node, True
# 最小値を探す
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)
#
# 巡回
#
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
# 木の表示
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_rb23tree(node):
if node is not null:
if node.color == RED:
if node.left.color == RED or node.right.color == RED:
raise 'rb23 error1'
else:
if node.left.color == RED and node.right.color == RED:
raise 'rb23 error2'
a = check_rb23tree(node.left)
b = check_rb23tree(node.right)
if a != b: raise 'rb23 error3'
if node.color == BLACK: a += 1
return a
return 0
# 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)
root.color = BLACK
check_rb23tree(root)
print('search test')
random.shuffle(buff)
for x in buff:
if not search(root, x):
raise 'search error'
print('delete test')
for x in buff:
root, _ = delete(root, x)
root.color = BLACK
check_rb23tree(root)