はじめに
2-3 木の続きです。前回はデータの探索と挿入について説明しました。今回はデータの削除について詳しく説明します。
●データの削除
2-3 木からデータを削除する場合、その処理はデータを挿入するよりも複雑です。2-3 木の途中にある節からデータ (data1 or data2) を削除する場合、そのデータをそのまま削除することはできません。2-3 木の条件である 左部分木(left) < data1 < 中央の部分木 (mid) < data2 < 右部分木 (right) を満たすようにデータを削除する必要があります。
この場合は、二分木と同様に「葉」からデータを削除するようにします。たとえば、data1 を削除する場合は、中央の部分木から最小値 min_data を探して data1 と置き換えます。そして、中央の部分木から min_data を削除します。
min_data を削除する場合、葉にデータが 2 つある場合は簡単です。問題は葉にあるデータが一つしかない場合です。葉は空になるので、2-3 木の条件を満たすように木を修正する処理が必要になります。
簡単な例を示しましょう。次の図を見てください。
上図 (a) の 2-3 木から 4 を削除します。4 は節 A に格納されていて、4 を削除すると空になるので、(b) のように葉を削除します。これで親節 P の左部分木の高さが一つ低くなった状態になります。そこで、データが 2 つある節から子を移動します。(b) の場合、A の隣の節 B にデータが 2 つあるので、小さいほうのデータを P を経由して移動します。つまり、B の data1 を P に動かして、P の data1 を左部分木 (A*) へ動かすのです。この状態が (c) で、2-3 木の条件を満たしています。
次は 10 を削除してみましょう。下図を見てください。
上図 (a) は 10 を削除した状態です。P の子 A*, C にはデータが一つしかありませんが、P にはデータが 2 つあります。この場合は、P の data2 と C を合わせて、節 B* を作ります。B* の data1 に 12 をセットし、data2 に 14 をセットします。そして、B* を P の中央の部分木にセットします。P の data2 は None にクリアします。つまり、P を経由して C のデータを B* へ動かすわけです。
次は、B* のデータ 14 を削除したあと、12 を削除する場合を考えて見ましょう。次の図を見てください。
上図 (a) の状態で、12 を削除すると (b) のようになります。この場合は節 A のデータを親節 P に動かして、A を削除します。すると、(c) の状態になり P は葉になります。つまり、部分木 P の高さは一つ低くなるわけです。今度は P の親節で木を修正する必要があります。もしも、P がルートであれば、2-3 木の高さが一つ低くなります。
●木の修正処理
それでは木の修正処理を詳しくみていきましょう。最初に左部分木の高さが一つ低くなる場合から説明します。次の図を見てください。
上図の左側は、左部分木 A で高さが一つ低くなった状態です。(a) は中央の節にデータが 2 つある場合です。左部分木に新しい節を作り、そこに A と X を挿入します。そして、データ c を親節へ、データ a を新しい節へ移動します。中央の部分木の Y, d, Z は一つずつ左へ移動します。親節のデータが一つの場合でも同じように修正できます。
(b) は親節にデータが 2 つある場合です。左部分木に新しい節を作り、そこに A, X, Y を挿入します。そして、データ a, c を新しい節へ移動します。中央の部分木は空になるので、右部分木 B を挿入して、右部分木を空にします。このとき、親節のデータ b を data1 に動かすことをお忘れなく。
(c) は親節と中央の節にはデータが一つしかない場合です。これは親節に X, Y を挿入し、データ b を data2 にセットします。親節の高さは一つ低くなるので、さらに木の修正が必要になります。
次は中央の部分木で削除が行われた場合です。
上図の左側は、中央の部分木 B で高さが一つ低くなった状態です。(a) は右部分木の節にデータが 2 つある場合です。中央の部分木に新しい節を作り、そこに B と X を挿入します。そして、データ c を親節へ、データ b を新しい節へ動かします。左部分木の Y, d, Z は一つずつ左へ移動します。親節のデータが一つの場合でも同じように修正できます。
(b) は親節にデータが 2 つある場合です。中央の部分木に新しい節を作り、そこに B, X, Y を挿入します。そして、データ b, c を新しい節へ移動します。右部分木は空になるので削除します。このとき、親節の data2 を None でクリアすることをお忘れなく。
中央の部分木で削除が行われるとき、右部分木がない場合もあります。次の図を見てください。
右部分木がないので、親節のデータは一つしかないことに注意してください。上図の左側は、中央の節 A の高さが一つ低くなった状態です。(a) は左部分木の節にデータが 2 つある場合です。中央の部分木に新しい節を作り、そこに Z と A を挿入します。そして、データ c を親節へ、データ a を新しい節へ移動します。左部分木の right と data2 は None でクリアすることをお忘れなく。
(b) は親節と左の節にはデータが一つしかない場合です。これは親節に X, Y, A を挿入し、データ b を data1 に、データ a を data2 にセットします。親節の高さは一つ低くなるので、さらに木の修正が必要になります。
最後は右部分木で削除が行われた場合です。
上図の左側は、右部分木 B で高さが一つ低くなった状態です。親節のデータは必ず 2 つあることに注意してください。(a) は中央の節にデータが 2 つある場合です。右部分木に新しい節を作り、そこに Z と B を挿入します。そして、データ d を親節へ、データ b を新しい節へ移動します。中央の節の right と data2 は None でクリアします。
(b) は中央の節のデータが 1 つしかない場合です。この場合は、節 B とデータ b を中央の節へ移動します。そして、親節の right と data2 を None でクリアします。
このように、データの削除は子の有無や個数で場合分けを行うため、プログラムはかなり複雑になります。
●プログラムの作成
それではプログラムを作りましょう。最初は木を再帰的にたどってデータを削除する関数 delete_node() を作ります。
リスト : データの削除
def delete_node(node, x):
if node is None: return False
if node.data1 == x or node.data2 == x:
# データを発見
if node.left is None:
# 葉
if node.data1 == x:
node.data1 = node.data2
node.data2 = None
return node.data1 is None
else:
# 節
if node.data1 == x:
node.data1 = _search_min(node.mid)
if delete_node(node.mid, node.data1):
return delete_mid(node)
else:
node.data2 = _search_min(node.right)
if delete_node(node.right, node.data2):
return delete_right(node)
elif x < node.data1:
if delete_node(node.left, x):
return delete_left(node)
elif node.data2 is None or x < node.data2:
if delete_node(node.mid, x):
return delete_mid(node)
else:
if delete_node(node.right, x):
return delete_right(node)
return False
delete_node() は引数 node の部分木からデータ x を削除します。データを削除して木の高さが一つ低くなった場合、delete_node() は True を返します。この場合は木の修正を行います。木の高さが変わらない場合は False を返します。
最初に、node が None の場合は False を返します。削除するデータが見つからない場合は、ここで再帰呼び出しが停止します。次に、x と node のデータ (data1, data2) と比較します。データを見つけた場合は削除処理を行います。node.left が None の場合、node は葉です。x と data1 が等しい場合は、data2 の値を data1 に上書きします。それ以外の場合は data2 を None に書き換えます。data1 が None の場合、データがなくなったので True を返します。そうでなければ False を返します。
node が節の場合は、削除するデータを右側の部分木の最小値に書き換えて、その部分木から最小値を削除します。x が data1 と等しい場合は、関数 _search_min() で node.mid から最小値を求めて data1 にセットします。そして、delete_node() で node.mid から最小値を削除します。最小値は葉に格納されているので、必ず削除することができます。返り値が Ture の場合は、関数 delete_mid() を呼び出して、中央の部分木の修正を行います。
data2 を削除する場合も同様です。_search_min() で node.right の最小値を求めて、node.data2 にセットします。そして、delete_node() で node.right から最小値を削除します。返り値が Ture の場合は delete_right() を呼び出して、右部分木の修正を行います。
x と節のデータが等しくない場合は木をたどります。x が data1 よりも小さい場合は node.left をたどります。返り値が Ture の場合は関数 delete_left() を呼び出して、左部分木の修正を行います。x が data2 よりも小さい場合、または data2 が None の場合は、 node.mid をたどります。部分木の修正は delete_mid() で行います。そして、x が data2 よりも大きい場合は node.right をたどります。部分木の修正は delete_right() で行います。
最小値を求める関数 _search_min() は簡単です。
リスト : 最小値を求める
def _search_min(node):
while node.left is not None: node = node.left
return node.data1
最小値は一番左側の葉に格納されています。左部分木をたどって葉に到達したら node.data1 を返すだけです。
●左部分木の修正
次は左部分木の修正を行う関数 delete_left() を作ります。次のリストを見てください。
リスト : 左部分木の修正
def delete_left(node):
# 空の葉ならばリンクを切る
if node.left.data1 is None: node.left = None
if node.mid.data2 is not None:
# 隣の節は子が３つ
node.left = Node(node.data1, node.left, node.mid.left)
node.data1 = node.mid.data1
move_left(node.mid)
return False
elif node.data2 is not None:
# node は子が３つ
move_right(node.mid, node.left, node.data1)
move_left(node)
return False
else:
# node の子が２つ
node1 = node.mid
node.data2 = node1.data1
node.mid = node1.left
node.right = node1.mid
return True
最初に、左部分木がデータのない葉かチェックします。そうであれば、node.left に None セットして葉を削除します。これで左部分木の高さが一つ低くなった状態になります。あとは、節の修正と同じ処理で大丈夫です。
node.mid にデータが 2 つ (子が 3 つ) ある場合、node.mid から節とデータを移動します。左部分木に新しい節を作り、そこに node.data1, node.left, node.mid.left をセットします。node.data1 は node.mid.data1 に書き換えます。そして、move_left() で node.mid に残っているデータを左へ移動します。
node にデータが 2 つある場合は、node.left と node.mid を併合します。関数 move_right で node.mid のデータを右へ移動し、空いたところに node.left と node.data1 を挿入します。これで、node.left のデータを node.mid に併合することができます。あとは、move_left() で node のデータを左へ一つ移動します。これで、併合された節が node.left にセットされます。
最後に、node の子が 2 つしかない場合は、node.mid の子を node にまとめます。node.mid を node1 にセットし、node1.left と node2.mid を node.mid と node.right に挿入します。そして、node.data2 に node1.data1 をセットします。この場合は木の高さが一つ低くなるので return で True を返します。
ここで、move_left() と move_right() を説明します。次のリストを見てください。
リスト : 子の移動
# 子を左へ移動する
def move_left(node):
node.left = node.mid
node.mid = node.right
node.right = None
node.data1 = node.data2
node.data2 = None
# 子を右へ移動する
def move_right(node, left, data1):
node.right = node.mid
node.mid = node.left
node.left = left
node.data2 = node.data1
node.data1 = data1
どちらの関数も簡単です。子を左へ移動する場合は node.right と node.data2 を None でクリアします。子を右へ移動する場合は、引数で与えられた節 left とデータ data1 を node.left と node.data1 にセットします。
●中央の部分木の修正
次は中央の部分木を修正する関数 delete_mid() を作ります。
リスト : 中央の部分木の修正
def delete_mid(node):
# 空の葉ならばリンクを切る
if node.mid.data1 is None: node.mid = None
if node.data2 is not None:
# 右の子と調整する
if node.right.data2 is not None:
# 子が３つある
node.mid = Node(node.data2, node.mid, node.right.left)
node.data2 = node.right.data1
move_left(node.right)
else:
# 子が２つ
move_right(node.right, node.mid, node.data2)
node.mid = node.right
node.right = None
node.data2 = None
return False
else:
# 左の子と調整する
if node.left.data2 is not None:
# 子が３つある
node.mid = Node(node.data1, node.left.right, node.mid)
node.data1 = node.left.data2
node.left.right = None
node.left.data2 = None
return False
else:
# 子が二つ
node1 = node.left
node.data2 = node.data1
node.data1 = node1.data1
node.right = node.mid
node.mid = node1.mid
node.left = node1.left
return True
node.mid にデータがない場合は削除します。次に、node.right がある場合は node.mid と node.right で調整します。node.rigth に子が 3 つある場合は、節とデータを node.mid に移動します。中央の部分木に新しい節を作り、そこに node.data2, node.mid, node.right.left を挿入します。node.data2 は node.right.data1 に書き換えます。そして、move_left() で node.right に残っているデータを左へ移動します。
子が 2 つしかない場合は、node.mid と node.right を併合します。move_right で node.mid と node.data2 を node.right に挿入します。そして、node.mid の値を node.right に書き換えます。あとは、node.rigth と node.data2 を None でクリアします。
node.right がない場合は、node.left と node.mid で調整します。node.left に子が 3 つある場合は、節とデータを node.mid に移動します。node.mid に新しい節を挿入します。ここに node.data1, node.left.right, node.mid を挿入し、node.data1 の値を node.left.data2 に書き換えます。あとは、node.left.right と node.left.data2 を None でクリアします。
子が 2 つしかない場合は、node.mid と node.left の子を node に格納します。node.left を node1 にセットし、node.data1 を node.data2 へ移動してから node.data1 に node1.data1 をセットします。そして、node.mid を node.rigth へ移動してから、node1 の子を node に挿入します。木の高さは一つ低くなるので True を返します。
●右部分木の修正
次は右部分木を修正する関数 delete_right() を作ります。
リスト : 右部分木の修正
def delete_right(node):
# 空の葉ならばリンクを切る
if node.right.data1 is None: node.right = None
# 中央の子と調整する
if node.mid.data2 is not None:
# 子が３つある
node.right = Node(node.data2, node.mid.right, node.right)
node.data2 = node.mid.data2
node.mid.right = None
node.mid.data2 = None
else:
node1 = node.mid
node1.right = node.right
node1.data2 = node.data2
node.right = None
node.data2 = None
return False
node.right にデータがない場合は削除します。node.mid に子が 3 つある場合は、節とデータを node.right へ移動します。新しい節を生成して node.right い挿入します。ここに node.data2, node.mid.right, node.right を挿入します。そして、node.data2 は node.mid.data2 に書き換えます。あとは、node.mid.right と node.mid.data2 を None でクリアします。
子が 2 つしかない場合は、node.mid と node.right を併合します。node.right と node.right.data2 を node.mid へ挿入します。そして、node.right と node.data2 を None でクリアするだけです。
●関数 delete() の作成
これでようやく 2-3 木からデータを削除する関数 delete() を作ることができます。次のリストを見てください。
リスト : データの削除
def delete(root, x):
if root is None: return None
if delete_node(root, x):
if root.data1 is None: return None
return root
引数 root は 2-3 木のルートで、x が削除するデータです。root が None の場合は空の木なので、削除するデータはありません。return で None を返します。次に、delete_node で x を削除します。返り値が True の場合、木の高さが一つ低くなります。このとき、root.data1 が None の場合は、2-3 木は空になったので None を返します。それ以外は root をそのまま返します。
●データ削除のテスト
それでは、ここでデータ削除のテストを行ってみましょう。テストプログラムは次のようになります。
リスト : データ削除の簡単なテスト
import node23
# 2-3 木の表示
def print_node(node, n):
if node is not None:
print_node(node.left, n + 1)
print(' ' * n, '{}-'.format(node.data1))
print_node(node.mid, n + 1)
if node.data2 is not None:
print(' ' * n, '{}='.format(node.data2))
print_node(node.right, n + 1)
root = None
for x in range(7):
root = node23.insert(root, x)
print_node(root, 0)
for x in range(7):
print('delete', x)
root = node23.delete(root, x)
print_node(root, 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
-----
このように、データを削除しても 2-3 木では全ての葉が同じレベルになります。
●2-3 木の巡回
今度は、2-3 木を巡回する関数 traverse() を作ります。次のリストを見てください。
リスト : 2-3 木の巡回
def traverse(node):
if node is not None:
for x in traverse(node.left):
yield x
yield node.data1
for x in traverse(node.mid):
yield x
if node.data2 is not None:
yield node.data2
for x in traverse(node.right):
yield x
traverse() はジェネレータとして実装しました。2-3 木の巡回は簡単です。最初に左部分木 (node.left) をたどります。次に、yield で node.data1 を返します。それから中央の部分木 (node.mid) をたどります。node.data2 がある場合は yield で node.data2 を返します。最後に、右部分木 (node.right) をたどります。とても簡単ですね。
●Tree23 クラスの作成
最後に 2-3 木を表すクラスを作成します。次のリストを見てください。
#
# tree23.py : 2-3 木
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import node23
# 2-3 木
class Tree23:
def __init__(self):
self.root = None
# 探索
def search(self, x):
return node23.search(self.root, x)
# 挿入
def insert(self, x):
self.root = node23.insert(self.root, x)
# 削除
def delete(self, x):
self.root = node23.delete(self.root, x)
# 巡回
def traverse(self):
for x in node23.traverse(self.root):
yield x
# 表示
def __str__(self):
if self.root is None: return 'Tree23()'
buff = 'Tree23('
for x in node23.traverse(self.root):
buff += '{}, '.format(x)
buff = buff.rstrip(', ')
buff += ')'
return buff
# テスト
if __name__ == '__main__':
import random
tree = Tree23()
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)
クラス名は Tree23 としました。Tree23 のメソッドはモジュール node23 の操作関数を呼び出すだけです。とくに難しいところはないでしょう。
それでは、テストの実行結果を示します。
$ python3 tree23.py [55, 14, 45, 15, 100, 73, 43, 74, 90, 40] Tree23() Tree23(14, 15, 40, 43, 45, 55, 73, 74, 90, 100) search 55 True delete 55 search 55 False Tree23(14, 15, 40, 43, 45, 73, 74, 90, 100) search 14 True delete 14 search 14 False Tree23(15, 40, 43, 45, 73, 74, 90, 100) search 45 True delete 45 search 45 False Tree23(15, 40, 43, 73, 74, 90, 100) search 15 True delete 15 search 15 False Tree23(40, 43, 73, 74, 90, 100) search 100 True delete 100 search 100 False Tree23(40, 43, 73, 74, 90) search 73 True delete 73 search 73 False Tree23(40, 43, 74, 90) search 43 True delete 43 search 43 False Tree23(40, 74, 90) search 74 True delete 74 search 74 False Tree23(40, 90) search 90 True delete 90 search 90 False Tree23(40) search 40 True delete 40 search 40 False Tree23()
●2-3 木の評価
それでは、二分木、AVL 木、2-3 木の性能を比較してみましょう。次のリストを見てください。
リスト : 二分木、AVL 木、2-3 木のテスト
from bintree import *
from avltree import *
from tree23 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, Tree23]:
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 : 2-3 tree
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------+---------------------+---------------------+---------------------
10000: 0.034 0.022 0.025 : 0.046 0.018 0.039 : 0.038 0.019 0.038
20000: 0.079 0.052 0.065 : 0.106 0.039 0.083 : 0.085 0.041 0.082
40000: 0.172 0.119 0.137 : 0.243 0.096 0.195 : 0.185 0.100 0.176
80000: 0.360 0.264 0.285 : 0.499 0.214 0.405 : 0.397 0.221 0.394
160000: 0.720 0.560 0.566 : 0.970 0.473 0.770 : 0.867 0.479 0.771
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
データの探索は AVL 木が最も速く、データの挿入と削除は二分木が最も速くなりました。2-3 木の場合、データの探索は二分木よりも高速ですが、AVL 木よりも少しだけ遅くなりました。データの挿入と削除は AVL 木よりも少しだけ速くなります。データの挿入と削除を頻繁に行う場合は、AVL 木よりも 2-3 木のほうが適しているようです。
次はソート済みのデータで試してみましょう。データの個数は 1 / 10 にしてあります。実行結果は次のようになりました。
表 : ソート済みデータの実行結果 (単位 : 秒)
: Binary tree : AVL tree : 2-3 tree
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------+---------------------+---------------------+---------------------
1000 : 0.066 0.061 0.001 : 0.004 0.001 0.003 : 0.003 0.002 0.003
2000 : 0.268 0.228 0.001 : 0.008 0.002 0.006 : 0.007 0.003 0.006
4000 : 1.059 0.915 0.003 : 0.017 0.006 0.014 : 0.016 0.006 0.012
8000 : 4.279 3.695 0.005 : 0.037 0.012 0.027 : 0.034 0.013 0.026
16000 :16.644 14.591 0.009 : 0.076 0.026 0.051 : 0.083 0.029 0.058
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
ソート済みデータの場合、二分木は線形探索と同じになるため、その性能は著しく劣化します。AVL 木と 2-3 木は平衡木なので、ソート済みデータの場合でも性能は大きく劣化しません。
なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
改訂 2022 年 9 月 3 日