はじめに
今回は Treap という平衡木 (balanced tree) を取り上げます。二分木は拙作のページ 二分木とヒープ で説明したように、左右の部分木のバランスが崩れると性能が劣化するという欠点があります。極端な例ですが、ソートされたデータを二分木に挿入していくと、データは右側の部分木にしか挿入されず、連結リストと同じ線形探索になってしまいます。
これを補うために、木のバランスを一定の範囲に収める平衡木が考案されています。有名なところでは、二分木をベースにした AVL 木、赤黒木、AA 木などや、多分木をベースにした 2-3 木、B 木、B* 木などがあります。今まで AVL 木、2-3 木、赤黒木 を取り上げてきました。これらの平衡木は、性能は優れているのですが、プログラムはけっこう複雑になります。
Treap - Wikipedia によると、Treap は 1989 年に Cecilia R. Aragon 氏と Raimund G. Seidel 氏が考案した平衡木です。Treap は二分木 (Binary Tree) とヒープ (Heap) を合わせた木構造で、プライオリティという数値データを付け加え、データは二分木の条件 (左部分木 < データ < 右部分木) を満たすように、プライオリティはヒープの条件 (親のプライオリティ <= 左右の子のプライオリティ) を満たすように調整します。このプライオリティの設定に乱数を使うところが Treap の特徴です。
つまり、前回説明したスキップリスト (Skip List) と同様に、Treap は木のバランス調整を乱数にまかせているわけです。このため、AVL 木や赤黒木と違ってプログラムはとてもシンプルになります。これが Treap の長所です。ただし、木のバランスが崩れる確率は 0 ではないので、性能が劣化する場合もありえます。ご注意くださいませ。
今回は Treap について簡単に説明し、実際にプログラムを作ってみましょう。なお、Treap の詳しい説明は Cecilia R. Aragon 氏と Raimund G. Seidel 氏の論文 Randomized Search Trees (PDF) をお読みください。
●Treap とは？
Treap の基本は二分木 (binary tree) と同じです。データの順序関係も二分木と同様に 左部分木 < 節のデータ < 右部分木 となります。Treap の特徴は、データのほかにプライオリティ (priority) という数値データを乱数で設定するところです。そして、親節のプライオリティ <= 左右の子のプライオリティ を満たすように二分木を構成します。これはヒープ (heap) の条件と同じです。つまり、ヒープの条件を満たすように木を操作することで、木の高さを低く抑えようというわけです。このように二分木とヒープの特徴を持つことから Treap (tree + heap) と呼ばれているようです。
簡単な例を示しましょう。1 から 7 までのデータを Treap に挿入します。このとき、乱数でプライオリティの値を決めますが、次に示す値になったとしましょう。
data : 1 2 3 4 5 6 7 priority : 99 28 40 7 87 91 31
Treap にデータを挿入する場合、二分木と同様にデータを挿入し、そのあとでプライオリティの条件を満たすように回転操作で二分木を修正します。次の図を見てください。
1 はルートに、2 は 1 の右の子に挿入されます。プライオリティを比較すると、2 のプライオリティ (28) の方が小さいですね。右の子のプライオリティが小さい場合は左回転を行います。1 を左回転すると、2 がルートになり、1 が 2 の左の子になります。回転操作は二分木の条件を崩しません。ヒープの条件を満たすように回転操作を行えばいいわけです。
次に 3 を挿入します。3 のプライオリティは 40 なので、ヒープの条件を満たしています。木を修正する必要はありません。次に、4 を挿入します。4 のプライオリティは 7 なので、3 のプライオリティ 40 よりも小さいですね。左の子のプライオリティが大きい場合は右回転を行います。3 を右回転すると、4 が 2 の右の子になり、3 が 4 の右の子になります。
その次に、2 と 4 のプライオリティを比較します。4 のプライオリティのほうが小さいので、2 を左回転します。これで 4 がルートになり、木の修正が終了します。
さらにデータを追加しましょう。次の図を見てください。
5 と 6 の挿入はヒープの条件を満たしているので、木の修正は必要ありません。次に 7 を挿入します。7 は 6 の右の子になりますが、ヒープの条件を満たしていないので、6 を左回転します。さらに、5 と 7 のプライオリティを比較すると、7 の方が小さいので、5 を左回転します。その次に 4 と 7 のプライオリティを比較しますが、ヒープの条件を満たしているので、木の修正はここで終了します。
単純な二分木の場合、ソート済みのデータを挿入すると、右部分木にしかデータが挿入されないため、連結リストと同じになってしまいます。Treap の場合、乱数でプライオリティを設定することにより、ソート済みのデータでも木のバランスが大きく崩れることはありません。
このように、木のバランスチェックを乱数に任せるのが Treap なのです。そのかわり、AVL 木や赤黒木などの平衡木のように、木の高さが一定の範囲内に収まるという保障はありません。ご注意くださいませ。
●プログラムの作成
それではプログラムを作りましょう。最初に節を表すクラスを定義します。
リスト : 節の定義
class Node:
def __init__(self, x):
self.data = x
self.priority = random.random()
self.left = None
self.right = None
クラス名は Node としました。基本的には二分木の節と同じで、プライオリティを格納するインスタンス変数 priority を追加します。この変数には乱数をセットします。今回は実数 [0, 1.0) の一様乱数を生成する関数 random() を使いました。
●データの挿入
Treap の場合、データの探索は二分木とまったく同じなので簡単です。データの挿入は、プライオリティをチェックして木を修正する処理が必要になります。次のリストを見てください。
リスト : データの挿入
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)
if node.priority > node.left.priority:
node = rotate_right(node)
else:
node.right = insert(node.right, x)
if node.priority > node.right.priority:
node = rotate_left(node)
return node
プログラムはとても簡単です。新しい節を挿入したあと、節 node と子のプライオリティを比較します。左部分木にデータを挿入した場合は、node と node.left の priority を比較します。もし、node.left の priority が小さい場合は、関数 rotate_right() で node を右回転します。
右部分木にデータを挿入した場合は、node と node.right の priority を比較します。もし、node.right の priority が小さい場合は、関数 rotate_left() で node を左回転します。
どちらの場合も、回転したあとの返り値は新しく挿入された節になります。この値を返して、次の親節でプライオリティの値を比較します。ルートに到達した場合は、その値が返されるので、それが新しいルートになります。このように、データの挿入はとても簡単にプログラムできます。
●データ挿入のテスト
それでは、ここでデータ挿入の簡単なテストを行ってみましょう。テストプログラムは次のようになります。
リスト : データ挿入の簡単なテスト
import * from tnode
from tnode import *
# Treap の表示
def print_treap(node, x = 0):
if node is not None:
print_treap(node.left, x + 1)
print(' ' * x, node.data, '{:.3f}'.format(node.priority))
print_treap(node.right, x + 1)
# Treap の条件をチェック
def check_treap(node):
if node is not None:
if node.left is not None:
if node.priority > node.left.priority: raise 'Treap error'
if node.right is not None:
if node.priority > node.right.priority: raise 'Treap error'
check_treap(node.left)
check_treap(node.right)
# テスト
a = None
print_treap(a)
for x in range(8):
a = insert(a, x)
check_treap(a)
print_treap(a)
print('-----')
関数 print_treap は Treap を表示し、関数 check_treap は Treap の条件を満たしているかチェックします。実行結果は次のようになりました。
0 0.300
-----
0 0.300
1 0.844
-----
0 0.300
1 0.844
2 0.740
-----
0 0.300
1 0.844
2 0.740
3 0.230
-----
0 0.300
1 0.844
2 0.740
3 0.230
4 0.270
-----
0 0.300
1 0.844
2 0.740
3 0.230
4 0.270
5 0.561
-----
0 0.300
1 0.844
2 0.740
3 0.230
4 0.270
5 0.561
6 0.333
-----
0 0.300
1 0.844
2 0.740
3 0.230
4 0.270
5 0.561
6 0.333
7 0.900
二分木の条件とヒープの条件をきちんと満たしていることがわかります。正常に動作していますね。Treap は乱数を使っているので、結果はプログラムを実行するたびに変わります。興味のある方はいろいろ試してみてください。
次は二分木、AVL 木、Treap の木の高さを比較してみましょう。テストプログラムは次のようになります。
リスト : データ挿入の簡単なテスト (2)
import node # 二分木
import avlnode # AVL 木
import tnode # Treap
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
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 # Treap
for n in buff:
a = avlnode.insert(a, n)
b = node.insert(b, n)
c = tnode.insert(c, n)
print(x, get_height(a), get_height(b), get_height(c))
実行結果を示します。
| N | AVL | BIN | Treap |
|---|---|---|---|
| 1000 | 12 | 20 | 20 |
| 2000 | 13 | 26 | 25 |
| 4000 | 15 | 25 | 27 |
| 8000 | 16 | 30 | 30 |
| 16000 | 16 | 30 | 33 |
Treap の木の高さは二分木と同じくらいになりました。乱数データを挿入する場合、Treap の効果はないようです。それでは、ソート済みのデータで試してみましょう。結果は次のようになりました。
| N | AVL | Treap |
|---|---|---|
| 1000 | 10 | 22 |
| 2000 | 11 | 23 |
| 4000 | 12 | 27 |
| 8000 | 13 | 28 |
| 16000 | 14 | 31 |
- ソート済みデータ
ソート済みデータの場合、Treap の木の高さは乱数データと同程度になりました。Treap の効果は十分に出ていると思います。ソート済みデータの場合でも、Treap は高速に処理できるはずです。これはあとで試してみましょう
●データの削除
次はデータの削除について説明します。Treap の場合、ヒープの条件を満たすようにデータを削除する必要があります。削除する節が「葉」の場合、または子が一つしかない場合は簡単です。問題は子が二つある場合です。次の図を見てください。
上図で、データ 4 を削除します。通常の二分木の場合、右部分木から最小値を探し、それと削除するデータと置き換えて、最小値を格納していた節を削除します。上図の場合、4 を格納していた節に右部分木の最小値 5 をセットし、5 を格納していた節を削除します。このとき、上図のようにプライオリティをそのままにしておけば、ヒープの条件を満たすことができます。
ところが、この方法では木のバランスを崩すことがあるのです。上図の場合でも、右部分木が空の木になるので、木のバランスは崩れてしまいます。Cecilia R. Aragon 氏と Raimund G. Seidel 氏の論文では、削除する節を回転操作で葉の方向へ移動して、その節が葉になった時点で節を削除します。次の図を見てください。
4 を削除する場合、左右の子のプライオリティを比較して、小さいほうの子が親節になるように回転します。この場合、左の子のプライオリティが小さいので右回転します。すると、4 の子は 3 と 5 になります。今度は右の子のプライオリティが小さいので左回転します。4 の子は 3 と None になります。子は左しかないので右回転します。すると、4 は葉になるので、ここで節を削除します。
上図を見ればお分かりのように、最小値のデータと置き換えるよりも木のバランスは保たれています。もちろん、これだけで平衡木のように木のバランスが保たれるわけではありません。また、この操作を行うことで、逆に木のバランスが崩れることもあるでしょう。ですが、トータルで考えると、ある程度の効果は期待できるように思われます。これはあとで実際に試してみましょう。
それではプログラムを作りましょう。次のリストを見てください。
リスト : データの削除
def delete(node, x):
if node is not None:
if x == node.data:
if node.left is None and node.right is None:
return None
elif node.left is None:
node = rotate_left(node)
elif node.right is None:
node = rotate_right(node)
else:
if node.left.priority < node.right.priority:
node = rotate_right(node)
else:
node = rotate_left(node)
node = delete(node, x)
elif x < node.data:
node.left = delete(node.left, x)
else:
node.right = delete(node.right, x)
return node
最初に node が None かチェックします。削除するデータ x が見つからない場合、この条件にあてはまります。次に、node.data と x が等しいかチェックします。その場合は、子の有無をチェックして回転操作で節を葉の方向へ移動します。子がない場合は節を削除します。これは None を返すだけです。次に、左の子がない場合は rotate_left() で左回転します。右の子がない場合は rotate_right() で右回転します。
子が二つある場合はプライオリティを比較します。左の子のプライオリティが小さい場合は右回転し、逆に右の子のプライオリティが小さい場合は左回転します。そして、回転操作したあとの node に対して delete を再帰呼び出しします。これで、削除する節を葉の方向へ移動することができます。
●データ削除のテスト
それでは、ここでデータ削除の簡単なテストを行ってみましょう。テストプログラムは次のようになります。
リスト : データ挿入の簡単なテスト
from tnode import *
# Treap の表示
def print_treap(node, x = 0):
if node is not None:
print_treap(node.left, x + 1)
print(' ' * x, node.data, '{:3f}'.format(node.priority))
print_treap(node.right, x + 1)
# Treap の条件をチェック
def check_treap(node):
if node is not None:
if node.left is not None:
if node.priority > node.left.priority: raise 'Treap error'
if node.right is not None:
if node.priority > node.right.priority: raise 'Treap error'
check_treap(node.left)
check_treap(node.right)
# テスト
a = None
print_treap(a)
for x in range(8):
a = insert(a, x)
check_treap(a)
print_treap(a)
print('-----')
for x in range(8):
print('delete', x)
a = delete(a, x)
check_treap(a)
print_treap(a)
print('-----')
実行結果は次のようになりました。
0 0.655
1 0.778
2 0.255
3 0.424
4 0.049
5 0.520
6 0.186
7 0.911
-----
delete 0
1 0.778
2 0.255
3 0.424
4 0.049
5 0.520
6 0.186
7 0.911
-----
delete 1
2 0.255
3 0.424
4 0.049
5 0.520
6 0.186
7 0.911
-----
delete 2
3 0.424
4 0.049
5 0.520
6 0.186
7 0.911
-----
delete 3
4 0.049
5 0.520
6 0.186
7 0.911
-----
delete 4
5 0.520
6 0.186
7 0.911
-----
delete 5
6 0.186
7 0.911
-----
delete 6
7 0.911
-----
delete 7
-----
二分木の条件とヒープの条件をきちんと満たしていることがわかります。正常に動作していますね。Treap は乱数を使っているので、結果はプログラムを実行するたびに変わります。興味のある方はいろいろ試してみてください。
次は通常の二分木の方法で削除する場合と、Treap の方法で削除する場合で、木の高さがどのように変化するか試してみましょう。テストプログラムは次のようになります。
リスト : データ削除の簡単なテスト (2)
from tnode import *
import random
# 木の高さを求める
def get_height(node):
if node is not None:
a = get_height(node.left)
b = get_height(node.right)
return max(a, b) + 1
return 0
a = None
b = None
buff = [random.randint(0, 0x10000) for _ in range(2000)]
random.seed(1)
for x in buff:
a = insert(a, x)
random.seed(1)
for x in buff:
b = insert(b, x)
count = 0
for x in buff:
if count % 200 == 0:
print(count, get_height(a), get_height(b))
a = delete(a, x)
b = delete1(b, x)
count += 1
二つの Treap を用意します。どちらの Treap も木の形を同じにするため、random.seed() で乱数のシードを設定します。引数に同じ値に設定すると、同じ乱数列が生成されます。そして、200 個削除するたびに、木の高さを関数 get_height() で求めます。関数 delete() は Treap の方法でデータを削除し、関数 delete1() は通常の二分木の方法、つまり右部分木の最小値と置き換える方法でデータを削除します。delete1() の詳細は プログラムリスト をお読みください。
実行結果は次のようになりました。
| 個数 | delete | delete1 |
|---|---|---|
| 0 | 25 | 25 |
| 200 | 24 | 25 |
| 400 | 23 | 24 |
| 600 | 23 | 24 |
| 800 | 21 | 24 |
| 1000 | 22 | 24 |
| 1200 | 21 | 22 |
| 1400 | 17 | 20 |
| 1600 | 18 | 17 |
| 1800 | 17 | 15 |
木の高さは delete の方が低くなる場合が多いようです。ただし、木の高さが増える場合もありますし、delete1 よりも木の高さが高くなる場合もあります。確かに木のバランスを保つ効果はありますが、平衡木のように木のバランスが一定の範囲に収まるわけではありません。ご注意ください。なお、実行結果はプログラムを実行するたびに変わります。興味のある方はいろいろ試してみてください。
●Treap クラスの作成
最後に Treap を表すクラスを作成します。次のリストを見てください。
#
# treap.py : Treap (binary tree + heap)
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import tnode
# 二分木
class Treap:
def __init__(self):
self.root = None
# 探索
def search(self, x):
return tnode.search(self.root, x)
# 挿入
def insert(self, x):
self.root = tnode.insert(self.root, x)
# 削除
def delete(self, x):
self.root = tnode.delete(self.root, x)
# 巡回
def traverse(self):
for x in tnode.traverse(self.root):
yield x
# 表示
def __str__(self):
if self.root is None: return 'Treap()'
buff = 'Treap('
for x in tnode.traverse(self.root):
buff += '%s, ' % x
buff = buff.rstrip(', ')
buff += ')'
return buff
# テスト
if __name__ == '__main__':
import random
tree = Treap()
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)
クラス名は Treap としました。Treap のメソッドはモジュール tnode の操作関数を呼び出すだけです。とくに難しいところはないでしょう。
それでは、テストの実行結果を示します。
[20, 93, 44, 30, 43, 45, 67, 80, 30, 10] Treap() Treap(10, 20, 30, 43, 44, 45, 67, 80, 93) search 20 True delete 20 search 20 False Treap(10, 30, 43, 44, 45, 67, 80, 93) search 93 True delete 93 search 93 False Treap(10, 30, 43, 44, 45, 67, 80) search 44 True delete 44 search 44 False Treap(10, 30, 43, 45, 67, 80) search 30 True delete 30 search 30 False Treap(10, 43, 45, 67, 80) search 43 True delete 43 search 43 False Treap(10, 45, 67, 80) search 45 True delete 45 search 45 False Treap(10, 67, 80) search 67 True delete 67 search 67 False Treap(10, 80) search 80 True delete 80 search 80 False Treap(10) search 30 False delete 30 search 30 False Treap(10) search 10 True delete 10 search 10 False Treap()
●Treap の評価
最後に、AVL 木、赤黒木、Treap の性能を比較してみましょう。次のリストを見てください。
リスト : AVL 木、赤黒木、Treap のテスト
from avltree import *
from rbtree import *
from treap 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, RBtree, Treap]:
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 : Red-Black tree : Treap
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------+---------------------+---------------------+---------------------
10000: 0.058 0.019 0.043 : 0.053 0.019 0.047 : 0.062 0.024 0.047
20000: 0.122 0.041 0.094 : 0.119 0.040 0.105 : 0.143 0.055 0.113
40000: 0.238 0.092 0.204 : 0.256 0.097 0.241 : 0.310 0.151 0.235
80000: 0.507 0.220 0.401 : 0.544 0.226 0.505 : 0.737 0.326 0.503
160000: 0.987 0.475 0.777 : 1.085 0.492 1.018 : 1.487 0.728 1.011
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
データの挿入と探索は Treap が一番遅くなりました。データの削除は赤黒木とほぼ同じくらいの速度です。木の高さは AVL 木や赤黒木よりも Treap のほうが高くなるので、データの探索は Treap が一番遅くなります。データの探索と削除に時間がかかるのは、回転操作の回数が多くなるためだと思われます。そこで、データの個数を 1 / 10 にして回転操作の回数を計測してみました。
表 : 回転操作の回数
: AVL tree : R-B tree : Treap
個数 : 挿入 削除 : 挿入 削除 : 挿入 削除
-----------------------------------------------
1000 : 693 379 : 578 417 : 1923 2019
2000 : 1369 766 : 1137 878 : 3775 3881
4000 : 2769 1559 : 2268 1657 : 7565 7714
8000 : 5044 2881 : 4268 3162 : 14443 14906
16000 : 9367 5428 : 7920 5748 : 27353 27147
回転操作の回数は Treap がとても多いですね。それでも、プログラムがシンプルなので、実行速度は極端に遅くなりません。AVL 木や赤黒木はプログラムが複雑なので、実行に時間がかかることがよくわかります。回転操作を高速に実行できれば、Treap の方が速くなると思われます。たとえば、Ｃ言語で実装すると、異なる結果になるかもしれません。興味のある方は試してみてください。
次はソート済みのデータで試してみました。実行結果は次のようになりました。
表 : ソート済みデータの実行結果 (単位 : 秒)
: AVL tree : Red-Black tree : Treap
個数 : 挿入 探索 削除 : 挿入 探索 削除 : 挿入 探索 削除
------+---------------------+---------------------+---------------------
10000: 0.051 0.016 0.036 : 0.080 0.016 0.042 : 0.035 0.022 0.029
20000: 0.109 0.037 0.084 : 0.173 0.036 0.086 : 0.074 0.054 0.052
40000: 0.203 0.075 0.132 : 0.376 0.094 0.185 : 0.152 0.094 0.104
80000: 0.413 0.158 0.262 : 0.773 0.189 0.419 : 0.327 0.223 0.251
160000: 0.791 0.348 0.524 : 1.503 0.359 0.803 : 0.602 0.432 0.501
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
データの探索は Treap が一番遅くなりましたが、データの挿入と削除は Treap が一番速くなりました。回転操作の回数は次のようになりました。
表 : 回転操作の回数
: AVL tree : R-B tree : Treap
個数 : 挿入 削除 : 挿入 削除 : 挿入 削除
--------------------------------------------------
1000 : 981 486 : 974 487 : 985 981
2000 : 1953 972 : 1945 973 : 1954 1959
4000 : 3823 1906 : 3814 1907 : 3829 3826
8000 : 7378 3683 : 7368 3684 : 7383 7386
16000 : 13651 6819 : 13640 6820 : 13658 13650
データの挿入では、回転操作の回数はどの平衡木もほぼ同じになりました。Treap は回転操作の回数が半減したので、実行時間は大幅に短縮されました。ソートされたデータを扱う場合は、Treap を使ってみるとよいかもしれません。
なお、これらの結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●プログラムリスト
#
# tnode.py : Treap (binary tree + heap) 操作関数
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import random
class Node:
def __init__(self, x):
self.data = x
self.priority = random.random()
self.left = None
self.right = None
# 右回転
def rotate_right(node):
lnode = node.left
node.left = lnode.right
lnode.right = node
return lnode
# 左回転
def rotate_left(node):
rnode = node.right
node.right = rnode.left
rnode.left = node
return rnode
# データの探索
def search(node, x):
while node is not None:
if x == node.data: return True
elif 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)
if node.priority > node.left.priority:
node = rotate_right(node)
else:
node.right = insert(node.right, x)
if node.priority > node.right.priority:
node = rotate_left(node)
return node
# 最小値の探索
def search_min(node):
while node.left is not None: node = node.left
return node.data
# データの削除 (1)
def delete(node, x):
if node is not None:
if x == node.data:
if node.left is None and node.right is None:
return None
elif node.left is None:
node = rotate_left(node)
elif node.right is None:
node = rotate_right(node)
else:
if node.left.priority < node.right.priority:
node = rotate_right(node)
else:
node = rotate_left(node)
node = delete(node, x)
elif x < node.data:
node.left = delete(node.left, x)
else:
node.right = delete(node.right, x)
return node
# データの削除 (2)
def delete1(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 = delete1(node.right, node.data)
elif x < node.data:
node.left = delete1(node.left, x)
else:
node.right = delete1(node.right, x)
return 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
改訂 2022 年 9 月 3 日