今回は 2-3 木 (two-three tree) という平衡木 (balanced tree) を取り上げます。二分木は拙作のページ「二分木とヒープ」で説明したように、左右の部分木のバランスが崩れると性能が劣化する欠点があります。極端な例ですが、ソートされたデータを二分木に挿入していくと、データは右側の部分木にしか挿入されず、連結リストと同じ線形探索になってしまいます。
これを補うために、木のバランスを一定の範囲に収める平衡木が考案されています。有名なところでは、二分木をベースにした AVL 木、赤黒木、AA 木や、多分木をベースにした 2-3 木、B 木、B* 木などがあります。二分木をベースにした AVL 木は前々回と前回で詳しく説明しました。今回は多分木をベースにした平衡木の中で、比較的簡単にプログラムを実装できる 2-3 木を紹介します。
多分木を使う場合、原理的に難しいことはないのですが、実際のプログラムは相当に複雑になります。2-3 木は B 木や B* 木に比べれば簡単なほうですが、それでもプログラムを作るのはけっこう大変です。
2-3 木は最大で 3 つの子を持つ多分木です。多分木で平衡木を実装する場合、葉にデータを格納する方法と、節と葉の両方にデータを格納する方法があります。たとえば、キーとデータを組にして木に格納する場合、第ーの方法は節にキーのみを格納し、葉にキーとデータの両方を格納します。第二の方法は節と葉どちらにもキーとデータを格納します。
B 木や B* 木を外部記憶上で利用する場合、最初の方法が一般的です。主記憶上で多分木を利用する場合、どちらの方法で実装してもかまわないのですが、第二の方法が一般的なようです。そこで、今回は第二の方法でプログラムを作りましょう。
簡単な例を示します。次の図を見てください。
┌─┬─┐
│６│12│
└─┴─┘
／│＼
／ │ ＼
／ │ ＼
／ │ ＼
／ │ ＼
／ │ ＼
／ │ ＼
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│４│─│ │８│10│ │14│─│
└─┴─┘ └─┴─┘ └─┴─┘
／ │ ＼ ／ │ ＼ ／ │ ＼
× × × × × × × × ×
図 1 : 2-3 木の例
上図の場合、箱で節を表しています。本稿では、左側の箱を data1、右側の箱を data2 と呼ぶことにします。2-3 木の場合、節には 1 個または 2 個のデータを格納することができます。データが 1 個の場合は data1 に格納します。データが 2 個の場合は data1 と data2 に格納しますが、data1 < data2 の条件を満たすようにします。
子は最大で 3 つまで持つことができます。左部分木を left、中央の部分木を mid、右部分木を right とします。データが 1 つの場合、2-3 木は 2 つの子 left と mid だけしかなく、right は必ず空の木 (終端) になります。データの順序関係は left < data1 < mid < data2 < right となります。
そして、ルートから葉 (子のない節) までの経路を全部同じ長さに揃えるところがポイントです。たとえば、すべての節でデータが 2 つ格納されている場合、データの総数は 2 * (30 + 31 + 32 + ... + 3n) = 3n+1 - 1 になります。すべての節でデータが 1 つしか格納されていない場合は二分木と同じなので、データの総数は 2n+1 - 1 になります。したがって、データが N 個の 2-3 木の高さは、log3 N から log2 N 程度に収まることになります。二分木のようにバランスが崩れることはありませんが、その分だけプログラムは二分木よりも複雑になります。
データの探索は簡単です。探索するデータを x とすると、x が data1 または data2 と等しい場合は探索成功です。そうでなければ 2-3 木をたどります。x < data1 であれば左部分木をたどり、x < data2 であれば中央の部分木をたどります。data2 がない場合は無条件に中央の部分木をたどります。それ以外の場合は右部分木をたどります。
たとえば、上図の 2-3 木で 9 を探してみましょう。ルートを見ると data1 は 6 で data2 は 12 なので、中央の部分木をたどります。次の節では、data1 は 8 で data2 は 10 なので、今度も中央の部分木をたどります。ところが、たどるべき木がないので、探索は失敗します。データ 9 は 2-3 木の中には無いことがわかります。
このように、データの探索は 2-3 木でも簡単ですが、データを挿入する操作はけっこう複雑です。
2-3 木にデータを挿入する場合は「葉」にデータを追加します。もし、その葉に格納されているデータが 1 つしかない場合は簡単です。その葉にデータを追加するだけです。次の図を見てください。
P
┌─┬─┐
│６│12│
└─┴─┘
／│＼
／ │ ＼
／ │ ＼
／ │ ＼
／ │ ＼
／ │ ＼
A ／ B │ C＼
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│４│─│ │８│10│ │14│─│
└─┴─┘ └─┴─┘ └─┴─┘
(a) 元の状態
P
┌─┬─┐
│６│12│
└─┴─┘
／│＼
／ │ ＼
／ │ ＼
／ │ ＼
／ │ ＼
／ │ ＼
A ／ B │ C＼
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│４│─│ │８│10│ │13│14│
└─┴─┘ └─┴─┘ └─┴─┘
(b) データ 13 を挿入する
図 2 : データの挿入
上図 (a) の 2-3 木に 13 を挿入します。木をたどっていくとデータを挿入する節は C になります。節 C にはデータが 1 つしかないので、ここに 13 を挿入します。このとき、data1 < data2 の順序が崩れないように、データの位置関係を調整します。データの順序は 13 < 14 なので、14 を data2 に移動して data1 に 13 をセットします。これは簡単ですね。
それでは、続いてデータ 9 を挿入してみましょう。今度は節 B にデータを追加します。ところが、節 B にはデータが 2 つ格納されています。この場合は下図のように節 B を分割します。
P
┌─┬─┐
│６│12│
└─┴─┘
／│└──────────────┐
／ │ │
／ │ │
／ │ │
／ │ │
／ │ │
A ／ B │ B* C │
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│４│─│ │８│─│ ９ │10│─│ │13│14│
└─┴─┘ └─┴─┘中央値└─┴─┘ └─┴─┘
図 3 : 葉の分割
3 つあるデータの中で、元の節 B には小さなデータを 1 つ格納し、新しい節に大きなデータを 1 つ格納します。そして、真ん中のデータは親節に挿入します。親節に格納されているデータが 1 つしかない場合は簡単です。そこに、データと新しい節を挿入するだけです。次の図を見てください。
P
┌─┬─┐
│６│─│
└─┴─┘
／│＼
／ │ ×
／ │
／ │
／ │
／ │
A ／ B │ B*
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│４│─│ │８│─│ ９ │10│─│
└─┴─┘ └─┴─┘中央値└─┴─┘
(a) 節 B を分割した状態
P
┌─┬─┐
│６│９│
└─┴─┘
／│＼
／ │ ＼
／ │ ＼
／ │ ＼
／ │ ＼
／ │ ＼
A ／ B │ B*＼
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│４│─│ │８│─│ │10│─│
└─┴─┘ └─┴─┘ └─┴─┘
(b) 節 P に新しい節を挿入
図 4 : 節の挿入
上図 (a) は中央の葉を分割した状態で、親節 P の右部分木がない場合です。この場合は、P の right に新しい節 B* を挿入し、data2 に中央値 9 をセットします。もしも、左の葉を分割した場合は、節 P の mid を right へ移動し、data1 を data2 へ移動します。そのあとで、新しい節を mid に挿入し、中央値を data1 にセットします。これで、2-3 木の条件を満たすことができます。
ところが、節 P に 2 つのデータが格納されている場合はちょっと面倒です。この場合も、次の図に示すように節 P を分割します。
P P*
┌─┬─┐ ┌─┬─┐
│６│─│ ９ │12│─│
└─┴─┘ 中央値 └─┴─┘
／│＼ ／│＼
／ │ × ／ │ ×
／ │ ／ │
／ │ ／ │
／ │ ／ │
／ │ ／ │
A ／ B │ B* ／ C │
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│４│─│ │８│─│ │10│─│ │13│14│
└─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘
図 5 : 節の分割 (1)
節 A, B, C と節 B* の順序は A < B < B* < C です。元の節 P には A と B をセットし、新しい節 P* には B* と C を格納します。そして、P の data1 には小さな値 6 を、P* の data1 には大きな値 12 をセットします。中央値 9 は親節へ挿入します。このとき、P の right と data2 は削除することをお忘れなく。
もしも、P がルートの場合は、新しい節 R を作って P と P* を格納し、それをルートに設定します。次の図を見てください。
R
┌─┬─┐
│９│─│
└─┴─┘
／ ＼ ＼
／ ＼ ×
／ ＼
／ ＼
P ／ ＼ P*
┌─┬─┐ ┌─┬─┐
│６│─│ │12│─│
└─┴─┘ └─┴─┘
／│＼ ／│＼
／ │ × ／ │ ×
／ │ ／ │
／ │ ／ │
／ │ ／ │
／ │ ／ │
A ／ B │ B* ／ C │
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│４│─│ │８│─│ │10│─│ │13│14│
└─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘
図 6 : 節の分割(2)
節 R の left に P を、mid に P* をセットします。そして、中央値 9 を R の data1 にセットします。これで 2-3 木の条件を満たすことができます。
このように、ルートの節が分割されると 2-3 木のレベルが 1 つ増えますが、葉までの経路は全て同じ長さになります。データを一つ (子を二つ) しか格納していない節が途中にあれば、そこに新しい節を追加するだけなので、ルートが分割されることはありません。2-3 木の高さは元のままです。
今まで説明したように、2-3 木の原理そのものは簡潔明瞭なので、すぐに理解できると思います。ところが、実際のプログラムはけっこう複雑になります。
それでは 2-3 木のプログラムを作りましょう。最初に、節を表すクラスを定義します。
リスト : 節の定義
class Node:
def __init__(self, data, left = None, mid = None):
self.data1 = data
self.data2 = None
self.left = left
self.mid = mid
self.right = None
クラス名は Node としました。インスタンス変数 data1 と data2 にデータを格納します。インスタンス変数 left が左部分木、mid が中央の部分木、right が右部分木を表します。Node() を呼び出すときは、引数として data1 と left と mid を渡します。left と mid は省略すると None になります。
それでは、データを探索する関数 search() を作りましょう。次のリストを見てください。
リスト : データの探索
def search(node, x):
while node is not None:
if node.data1 == x:
return True
elif x < node.data1:
node = node.left
elif node.data2 is None:
node = node.mid
elif node.data2 == x:
return True
elif x < node.data2:
node = node.mid
else:
node = node.right
return False
引数 node が 2-3 木の節、x が探索するデータです。x が data1 と等しい場合はデータが見つかったので True を返します。x が data1 よりも小さい場合は node.left をたどります。次に、data2 が None の場合は右部分木がないので、無条件で node.mid をたどります。x が data2 と等しい場合も True を返します。そして、x が data2 よりも小さい場合は node.mid をたどり、そうでなければ node.right をたどります。node が None になったら while ループを終了して False を返します。
リスト : データの探索 (修正前)
def search(node, x):
while node is not None:
if node.data1 == x or (node.data2 is not None and node.data2 == x):
return True
if x < node.data1:
node = node.left
elif node.data2 is None or x < node.data2:
node = node.mid
else:
node = node.right
return False
次は、データを挿入する関数 insert() を作りましょう。実際の処理は関数 insert_node() で行います。次のリストを見てください。
リスト : 節の挿入処理 (1)
def insert_node(node, x):
if node.data1 == x or node.data2 == x:
return None, None # 同じデータがある
if node.left is None:
# 葉の処理
return insert_leaf(node, x)
# 節の処理
if x < node.data1:
new_node, mid_data = insert_node(node.left, x)
if new_node is None: return None, None
if node.right is not None:
# 分割
new_node1 = Node(node.data2, node.mid, node.right)
node.mid = new_node
node.right = None
mid_data1 = node.data1
node.data1 = mid_data
node.data2 = None
return new_node1, mid_data1
else:
# 挿入
node.right = node.mid
node.data2 = node.data1
node.data1 = mid_data
node.mid = new_node
return None, None
# 続く
insert_node() は部分木 node にデータ x を挿入します。そして、節を分割した場合は、新しい節と中央値を返します。そうでなければ、None, None を返します。リストが少々長いので三分割しました。
最初に、x と同じデータが data1 と data2 にあるかチェックします。同じデータがある場合は、何もしないで None, None を返します。次に、node.left が None の場合、node は葉なので、そこに x を挿入します。この処理を関数 insert_leaf() で行います。insert_leaf() の返り値は insert_node() と同じです。
node が葉でない場合は節の挿入処理を行います。x が data1 よりも小さい場合は、insert_node() を再帰呼び出しして node.left に x を挿入します。そして、返り値を変数 new_node, mid_data にセットします。new_node が None の場合、node に挿入する節はないので None, None を返します。
新しい節 new_node がある場合は、節の挿入処理を行います。node.right がなければ new_node を挿入できますが、node.right がある場合は node を分割します。新しい節を Node() で生成して、変数 new_node1 にセットします。データの順序は left, mid_data, new_node, data1, mid, data2, right になります。したがって、new_node1 には mid, data2, right をセットし、node には left, mid_data, new_node をセットします。そして、新しい節 new_node1 と中央値 data1 を返します。
new_node を node に挿入する場合は簡単です。node.mid を node.right へ、data1 を data2 へ移動します。それから、node.mid に new_node を挿入して、data1 に mid_data をセットします。最後に None, None を返します。
次は中央の部分木の処理です。
リスト : 節の挿入処理 (2)
elif node.data2 is None or x < node.data2:
new_node, mid_data = insert_node(node.mid, x)
if new_node is None: return None, None
if node.right is not None:
# 分割
new_node1 = Node(node.data2, new_node, node.right)
node.right = None
node.data2 = None
return new_node1, mid_data
else:
# 挿入
node.right = new_node
node.data2 = mid_data
return None, None
# 続く
data2 が None の場合、または x が data2 よりも小さい場合は node.mid をたどります。insert_node() を再帰呼び出しして返り値を new_node と mid_data にセットします。new_node が None の場合は None, None を返します。そうでなければ、節の挿入処理を行います。
node.right がある場合は node を分割します。Node() で新しい節を生成して new_node1 にセットします。データの順序は left, data1, mid, mid_data, new_node, data2, right になるので、new_node1 には new_node, data2, right をセットし、node には left, data1, mid をセットします。この場合、node は right と data2 を None でクリアするだけです。そして、new_node1 と mid_data を返します。
new_node を挿入する場合は簡単です。node.right に new_node を挿入し、node.data2 に mid_data をセットするだけです。そして、None, None を返します。
最後は右部分木の処理です。
リスト : 節の挿入処理 (3)
else:
new_node, mid_data = insert_node(node.right, x)
if new_node is None: return None, None
# 分割
new_node1 = Node(mid_data, node.right, new_node)
mid_data1 = node.data2
node.data2 = None
node.right = None
return new_node1, mid_data1
insert_node() を再帰呼び出しして node.right に x を挿入します。返り値は new_node と mid_data にセットします。new_node が None であれば None, None を返します。
そうでなければ node を分割します。Node() で新しい節を生成して変数 new_node1 にセットします。データの順序は left, data1, mid, data2, right, mid_data, new_node になるので、new_node1 には right, mid_data, new_node をセットします。そして、node には left, data1, mid をセットします。この場合、node.right と node.data2 を None でクリアするだけです。ただし、node.data2 は中央値として返す必要があるので、mid_data1 にセットしておきます。そして、最後に new_node1 と mid_data1 を返します。
次は葉にデータを挿入する関数 insert_leaf() を作ります。
リスト : 葉にデータを挿入する
def insert_leaf(node, x):
new_node = None
mid_data = None
if node.data2 is not None:
# 分割
if x < node.data1:
new_node = Node(node.data2)
mid_data = node.data1
node.data1 = x
elif x < node.data2:
new_node = Node(node.data2)
mid_data = x
else:
new_node = Node(x)
mid_data = node.data2
node.data2 = None
else:
# 挿入
if x < node.data1:
node.data2 = node.data1
node.data1 = x
else:
node.data2 = x
return new_node, mid_data
データが 2 つがある場合は葉 (node) を分割します。x が data1 よりも小さい場合、データの順序は x, data1, data2 になるので、Node(node.data2) で新しい節 new_node を生成して、min_data に node.data1 をセットします。そして、node.data1 を x に書き換えます。
x が data2 よりも小さい場合、データの順序は data1, x, data2 になります。この場合は Node(node.data2) で新しい節 new_node を生成して、min_data に x をセットします。node.data1 はそのままです。x が data2 よりも大きい場合は Node(x) で新しい節 new_node を生成して、mid_data に data2 をセットします。最後に、node.data2 を None でクリアします。
データが一つしかない場合は、x と data1 を比較して、小さいほうを data1 にセットし、大きいほうを data2 にセットします。最後に、new_node, mid_data を返します。new_node と mid_data は None で初期化されているので、葉が分割されていない場合は None, None が返されます。
最後に 2-3 木にデータを挿入する関数 insert() を作ります。次のリストを見てください。
リスト : データの挿入
def insert(root, x):
if root is not None:
new_node, mid_data = insert_node(root, x)
if new_node is not None:
return Node(mid_data, root, new_node)
return root
return Node(x)
insert() の引数 root は 2-3 木のルートで、x が挿入するデータです。root が None の場合は空の木なので、Node() で新しい節を生成して return で返します。root にデータがある場合は、insert_node() を呼び出して root に x を挿入します。返り値は new_node と mid_data にセットします。new_node が None でない場合は、Node() で新しい節を生成して返します。 このとき、mid_data が data1 に、root が左部分木に、new_node が中央の部分木になります。new_node が 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):
print('insert', x)
root = node23.insert(root, x)
print_node(root, 0)
print('-----')
関数 print_node は 2-3 木を表示します。data1 と data2 を区別するため、後ろに '-' と '=' を付け加えています。そして、データを出力する前に、レベル * 4 個の空白を出力します。これで木の形を表すことができます。
それでは、0 から 6 までの整数値を順番に 2-3 木に挿入してみましょう。実行結果は次のようになります。
insert 0
0-
-----
insert 1
0-
1=
-----
insert 2
0-
1-
2-
-----
insert 3
0-
1-
2-
3=
-----
insert 4
0-
1-
2-
3=
4-
-----
insert 5
0-
1-
2-
3=
4-
5=
-----
insert 6
0-
1-
2-
3-
4-
5-
6-
-----
このように、2-3 木では全ての葉が同じレベルになります。データを 7 個挿入しましたが、全ての節で data2 がなく、二分木と同じようになってしまいました。実は、ソートされたデータを挿入すると、2-3 木は二分木と同じ形状になる場合があります。この場合、メモリが無駄になってしまいますね。けっきょく、2-3 木でもソート済みのデータは苦手なのですが、二分木と違って性能が劣化することはありません。
次は木の高さを比較してみましょう。次のリストを見てください。
リスト : データ挿入の簡単なテスト (2)
import node
import avlnode
import node23
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 get_height23(root):
h = 1
node = root
while node.left is not None:
h += 1
node = node.left
return h
for x in [1000, 2000, 4000, 8000, 16000]:
buff = [random.randint(0, 100000) for _ in range(x)]
a = None # AVL tree
b = None # Binary tree
c = None # 2-3 tree
for n in buff:
a = avlnode.insert(a, n)
b = node.insert(b, n)
c = node23.insert(c, n)
print(x, get_height(a), get_height(b), get_height23(c))
関数 get_height23 は 2-3 木の高さを求めます。これはルートから葉までの節の個数を求めるだけなので簡単です。
それでは、実行結果を示します。
| N | AVL | BIN | 2-3 |
|---|---|---|---|
| 1000 | 12 | 21 | 8 |
| 2000 | 13 | 22 | 9 |
| 4000 | 14 | 28 | 10 |
| 8000 | 16 | 30 | 11 |
| 16000 | 16 | 35 | 12 |
2-3 木の高さは AVL 木や二分木よりも低くなりました。2-3 木は多分木なので、二分木をベースにした AVL 木よりも高さが低くなるのは当然の結果でしょう。ただし、木の高さが低くなるからといって、AVL 木よりも探索が速くなるとは限りません。2-3 木は節にデータを 2 つ格納している場合があるので、データの比較は AVL 木よりも時間がかかると思われます。データの探索は AVL 木よりも遅くなるかもしれません。これはプログラムを完成したあとで、実際に試してみましょう。
次回はデータの削除について説明します。
#
# node23.py : 2-3 木用操作関数
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
# 節にもデータを格納する
# left < data1 < mid < data2 < right
#
# 節の定義
class Node:
def __init__(self, data, left = None, mid = None):
self.data1 = data
self.data2 = None
self.left = left
self.mid = mid
self.right = None
#
# データの探索
#
def search(node, x):
while node is not None:
if node.data1 == x:
return True
elif x < node.data1:
node = node.left
elif node.data2 is None:
node = node.mid
elif node.data2 == x:
return True
elif x < node.data2:
node = node.mid
else:
node = node.right
return False
#
# データの挿入
#
# 葉にデータを挿入する
# 返り値 : (新しい葉, 中間の値) or (None, None)
def insert_leaf(node, x):
new_node = None
mid_data = None
if node.data2 is not None:
# 分割
if x < node.data1:
new_node = Node(node.data2)
mid_data = node.data1
node.data1 = x
elif x < node.data2:
new_node = Node(node.data2)
mid_data = x
else:
new_node = Node(x)
mid_data = node.data2
node.data2 = None
else:
# 挿入
if x < node.data1:
node.data2 = node.data1
node.data1 = x
else:
node.data2 = x
return new_node, mid_data
# 節の挿入処理
# 返り値 : (新しい節, 中間の値) or (None, None)
def insert_node(node, x):
if node.data1 == x or node.data2 == x:
return None, None # 同じデータがある
if node.left is None:
# 葉の処理
return insert_leaf(node, x)
# 節の処理
if x < node.data1:
new_node, mid_data = insert_node(node.left, x)
if new_node is None: return None, None
if node.right is not None:
# 分割
new_node1 = Node(node.data2, node.mid, node.right)
node.mid = new_node
node.right = None
mid_data1 = node.data1
node.data1 = mid_data
node.data2 = None
return new_node1, mid_data1
else:
# 挿入
node.right = node.mid
node.data2 = node.data1
node.data1 = mid_data
node.mid = new_node
return None, None
elif node.data2 is None or x < node.data2:
new_node, mid_data = insert_node(node.mid, x)
if new_node is None: return None, None
if node.right is not None:
# 分割
new_node1 = Node(node.data2, new_node, node.right)
node.right = None
node.data2 = None
return new_node1, mid_data
else:
# 挿入
node.right = new_node
node.data2 = mid_data
return None, None
else:
new_node, mid_data = insert_node(node.right, x)
if new_node is None: return None, None
# 分割
new_node1 = Node(mid_data, node.right, new_node)
mid_data1 = node.data2
node.data2 = None
node.right = None
return new_node1, mid_data1
# データの挿入
def insert(root, x):
if root is not None:
new_node, mid_data = insert_node(root, x)
if new_node is not None:
return Node(mid_data, root, new_node)
return root
return Node(x)
#
# データの削除
#
# 最小値を求める
def _search_min(node):
while node.left is not None: node = node.left
return node.data1
# 子を左へ移動する
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
# 左部分木が削除された
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
# 中央の部分木が削除された
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
# 右部分木が削除された
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
# 節の削除
def delete_node(node, x):
if node is None: return False
if node.data1 == x or (node.data2 is not None and 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
# データの削除
def delete(root, x):
if root is None: return None
if delete_node(root, x):
if root.data1 is None: return None
return root
#
# 巡回
#
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