探索木の動作
平衡２分探索木の考えですが、以下の関係を壊さないように、気に対してノードの追加と削除進めていきます。
左の子ノードの値 ≦ ノードの値 ≦ 右の子ノードの値
加えて、木の平衡状態、つまり
各ノードの左右の部分木の高さの差が１以下にする
という状態を保つために
ノードの追加や削除が行われた後に回転が行われます。
このロジックの理解を深めるため、どのように木が変化していくかを可視化してみます。
こんな感じです。
数がデータ最大値までの乱数を出力しながら
２分探索木のルールを守りながらアニメーションしていきます。
ソースコードですが、クラスをいくつか作成します。
- Controller クラス
- View クラス
- Node クラス
- Tree クラス
あとは関数をいくつも作成しています。
以下にサンプルプログラムを掲載します。
2TreeSamplePython.py
import tkinter
import time
import math
import random
# キャンバスのサイズ
CANVAS_WIDTH = 1200
CANVAS_HEIGHT = 700
# データの最大値
DATA_NUM = 120
# 描画時のウェイト（s）
WAIT = 0.1
# 円の半径
RADIUS = 30
class Node():
def __init__(self, number):
self.left = None
self.right = None
self.number = number
class Tree():
# 枝の方向を指す定数
LEFT = 0
RIGHT = 1
# 処理を表す定数
ADD = 0
LEFT_ROTATE = 1
RIGHT_ROTATE = 2
DELETE = 3
def __init__(self, view):
# 木構造を制御するオブジェクト生成
self.view = view
# 木の根をNoneに初期化
self.root = None
def add_node(self, number):
# ノードを追加
# まだノードがない場合
if not self.root:
# 根ノードとしてノードを追加
self.root = Node(number)
self.draw(Tree.ADD)
return True
# 根ノードから順に追加する場所を探索
node = self.root
# 根ノードからどう辿ったかを覚えておくリスト
branch = []
while True:
# 追加する値がノードの値よりも小さい場合
if number < node.number:
# 左の枝を辿った情報を格納
branch.append(Tree.LEFT)
# そのノードの左の子が無い場合
# （もう辿るべきノードが無い場合）
if not node.left:
# その左の子の位置にノードを追加
node.left = Node(number)
# 追加完了し処理終了
break
# 左の子がある場合
# 左の子を新たな注目ノードに設定
node = node.left
# 追加する値がノードの値よりも大きい場合
elif number > node.number:
# 右の枝を辿った情報を格納
branch.append(Tree.RIGHT)
# そのノードの右の子が無い場合
# （もう辿るべきノードが無い場合）
if not node.right:
# その右の子の位置にノードを追加
node.right = Node(number)
# 追加完了し処理終了
break
# 右の子がある場合
# 右の子を新たな注目ノードに設定
node = node.right
# 追加する値とノードの値が同じ場合
else:
print(str(number) + " Already Exist")
return False
# 一旦追加した状態で描画
self.draw(Tree.ADD)
# 平衡に保つための回転
self.balancing(self.root, None, None, branch)
return True
# numberの値を持つノードを削除
def delete_node(self, number):
if not self.root:
return False
# 削除するノードを探索
node = self.root
# 親ノードはNone
parent = None
# 根ノードからどう辿ったか情報を格納するリスト
branch = []
while node:
# 探索する値よりもnodeの値が大きい場合
if number < node.number:
# 左の枝を辿った情報を格納
branch.append(Tree.LEFT)
# 左の子ノードを辿る
parent = node
node = node.left
# 探索する値よりもnodeの値が小さい場合
elif (number > node.number):
# 右の枝を辿った情報を格納
branch.append(Tree.RIGHT)
# 右の子ノードを辿る
parent = node
node = node.right
# 見つかった場合
else:
# 処理終了
break
# 見つからなかった場合
else:
print(str(number) + "を持つノードはありません")
return False
# 子がいないノードの削除
if not node.left and not node.right:
self.delete_no_child_node(node, parent)
# 左の子のみいるノードの削除
elif node.left and not node.right:
self.delete_one_child_node(node, node.left)
# 右の子のみいるノードの削除
elif not node.left and node.right:
self.delete_one_child_node(node, node.right)
# 左の子と右の子両方がいるノードの削除
else:
self.delete_two_child_node(node, branch)
# キャンバスから削除したノードの情報を除去
self.remove(number)
# 除去後の木を描画
self.draw(Tree.DELETE)
# 平衡にするため回転
self.balancing(self.root, None, None, branch)
return True
# 子のいないノード(node)を削除
def delete_no_child_node(self, node, parent):
# 親がいる場合
if parent:
# nodeへの参照を外す
if parent.left == node:
parent.left = None
else:
parent.right = None
# 親がいない場合
else:
self.root = None
# 子が一方にだけいるノード(node)の削除
def delete_one_child_node(self, node, child):
# child のデータを node にコピー
node.number = child.number
node.left = child.left
node.right = child.right
# 子が２つあるノード(node)の削除
def delete_two_child_node(self, node, branch):
# nodeの左の子孫ノードの中から最大値を持つノードを探索
max_node = node.left
max_parent = node
# 左の枝を辿った情報を格納
branch.append(Tree.LEFT)
# 必ず右の子ノードの方が値が大きい
while max_node.right:
max_parent = max_node
max_node = max_node.right
# 右の枝を辿ったことを覚えておく
branch.append(Tree.RIGHT)
# 最大ノードのデータ(number)をnodeにコピー
node.number = max_node.number
# 最大ノード(max_node)を削除
# 最大ノードなので右の子ノードはいない
if not max_node.left:
# max_nodeに子がいない場合
self.delete_no_child_node(max_node, max_parent)
else:
# 子が１つある場合
self.delete_one_child_node(max_node, max_node.left)
# 各ノードの平衡係数を±1以下にする
def balancing(self, node, parent, direction, branch):
if not node:
return
# 辿れる場合はまず目的のノードまで辿る
if len(branch) > 0:
# 辿る子ノードを設定
if branch[0] == Tree.LEFT:
next = node.left
else:
next = node.right
# 子ノードを辿る
self.balancing(next, node, branch[0], branch[1:])
# 平衡係数を計算
left_height = self.get_height(node.left)
right_height = self.get_height(node.right)
balance = right_height - left_height
# 右の部分木が高くて並行状態でない場合
if balance > 1:
# ２重回転が必要かどうかを判断
if self.get_height(node.right.left) > self.get_height(node.right.right):
# ２重回転（Right Left Case）
self.right_left_rotate(node, parent, direction)
else:
# １重回転（左回転）
self.left_rotate(node, parent, direction)
# 左の部分木が高くて並行状態でない場合
elif balance < -1:
# ２重回転が必要かどうかを判断
if self.get_height(node.left.right) > self.get_height(node.left.left):
# ２重回転（Left Right Case）
self.left_right_rotate(node, parent, direction)
else:
# １重回転（右回転）
self.right_rotate(node, parent, direction)
# ２重回転（Right Left Case）を行う
def right_left_rotate(self, node, parent, direction):
print("right_left_rotate:" + str(node.number))
# nodeの右の子ノードを根として右回転
self.right_rotate(node.right, node, Tree.RIGHT)
# nodeを根として左回転
self.left_rotate(node, parent, direction)
# ２重回転（Left Right Case）を行う
def left_right_rotate(self, node, parent, direction):
print("left_right_rotate:" + str(node.number))
# nodeの左の子ノードを根として左回転
self.left_rotate(node.left, node, Tree.LEFT)
# nodeを根として右回転
self.right_rotate(node, parent, direction)
# nodeを根として左回転を行う
def left_rotate(self, node, parent, direction):
print("left_rotate:" + str(node.number))
# 新しい根とするノードをpivotとして設定
pivot = node.right
# 左回転
if pivot:
node.right = pivot.left
pivot.left = node
# parentもしくはrootに新しい根ノードを参照させる
if not parent:
self.root = pivot
self.draw(Tree.LEFT_ROTATE)
return
# どちらの子に設定するかはdirectionから判断
if direction == Tree.LEFT:
parent.left = pivot
else:
parent.right = pivot
self.draw(Tree.LEFT_ROTATE)
# nodeを根として右回転を行う
def right_rotate(self, node, parent, direction):
print("right_rotate:" + str(node.number))
# 新しい根とするノードをpivotとして設定
pivot = node.left
# 右回転
if pivot:
node.left = pivot.right
pivot.right = node
# parentもしくはrootに新しい根ノードを参照させる
if not parent:
self.root = pivot
self.draw(Tree.RIGHT_ROTATE)
return
# どちらの子に設定するかはdirectionから判断
if direction == Tree.LEFT:
parent.left = pivot
else:
parent.right = pivot
self.draw(Tree.RIGHT_ROTATE)
# nodeを根とした木の高さを取得する
def get_height(self, node):
# nodeが無いなら高さは0
if not node:
return 0
# 左右の子を根とした木の高さを取得
left_height = self.get_height(node.left)
right_height = self.get_height(node.right)
# 大きい方に+1したものを木の高さとして返却
if left_height > right_height:
tree_height = left_height
else:
tree_height = right_height
return tree_height + 1
# 木の描画
def draw(self, process):
# rootを根とする木を描画
self.draw_node(self.root, [], process)
# キャンバスのアップデート依頼
self.view.update()
# スリープ
time.sleep(WAIT)
# 枝を辿りながらnodeを根とする木を描画
def draw_node(self, node, branch, process):
if not node:
return
# 処理によって円の色を変える
if process == Tree.LEFT_ROTATE:
diff_color = "#FFDDDD"
elif process == Tree.RIGHT_ROTATE:
diff_color = "#DDDDFF"
elif process == Tree.ADD:
diff_color = "#DDFFDD"
elif process == Tree.DELETE:
diff_color = "#FFFFDD"
# そのノードと親ノードを繋ぐ線を描画
self.view.draw_line(node, branch)
# そのノードを描画
self.view.draw_oval(node, branch, diff_color)
# そのノードの数字を描画
self.view.draw_text(node, branch)
# 左の子孫ノードを描画
branch.append(0)
self.draw_node(node.left, branch, process)
del branch[-1]
# 右の子孫ノードを描画
branch.append(1)
self.draw_node(node.right, branch, process)
del branch[-1]
# numberをデータに持つノードの描画を除去
def remove(self, number):
self.view.remove_oval(number)
self.view.remove_line(number)
self.view.remove_text(number)
class View():
# UI関連のオブジェクト生成
def __init__(self, master):
self.master = master
# 各種設定
self.drawn_oval = []
self.drawn_line = []
self.drawn_text = []
# キャンバスのサイズを決定
self.canvas_width = CANVAS_WIDTH
self.canvas_height = CANVAS_HEIGHT
# 情報表示用のフレームを作成
self.canvas_frame = tkinter.Frame(
master,
)
self.canvas_frame.grid(column=1, row=1)
# 操作用ウィジェットのフレームを作成
self.operation_frame = tkinter.Frame(
master,
)
self.operation_frame.grid(column=2, row=1, padx=10)
# キャンバスの生成と配置
self.canvas = tkinter.Canvas(
self.canvas_frame,
width=self.canvas_width,
height=self.canvas_height,
bg="#F0F0F0"
)
self.canvas.pack()
# 開始ボタンの生成と配置
self.button = tkinter.Button(
self.operation_frame,
text="開始",
)
self.button.pack()
# キャンバス上の円の中心座標を取得
def get_oval_coord(self, branch):
# まずは木のどの位置の円を描画するかをbranchから計算
# branchの長さよりこのノードの縦方向の位置を計算
tree_y = len(branch)
# branchの要素より左から何番目のデータかを計算
tree_x = 0
i = 0
for n in branch[::-1]:
tree_x += n * 2 ** i
i += 1
# tree_xとtree_yをキャンバス上の座標に変換していく
# データ数より木の最大高さを計算
max_tree_height = math.ceil(math.log2(DATA_NUM + 0.5)) + 1
# マスの数を計算
# 平衡
num_horizontal = 2 ** (max_tree_height - 1) * 2
# 垂直
num_vertical = max_tree_height * 2
# １マスの幅を計算（キャンバスの幅とマス数より）
one_width = self.canvas.winfo_width() / num_horizontal
# １マスの高さを計算（キャンバスの高さとマス数より）
one_height = self.canvas.winfo_height() / num_vertical
# 円の中心座標を計算
x_space = num_horizontal / (2 ** tree_y * 2)
x = x_space * (tree_x * 2 + 1) * one_width
y = (tree_y * 2 + 1) * one_height
return x, y
# ２つの座標が同じである角かを判断
def judge_same_coord(self, coord1, coord2):
# どちらか一方が None
if not coord1 or not coord2:
return False
# 長さが違う
if len(coord1) != len(coord2):
return False
# 座標が同じかを１つ１つチェック
for i in range(len(coord1)):
if not math.isclose(coord1[i], coord2[i]):
# 異なればFalse
return False
# 全部同じならTrue
return True
# ノードを表す円をdiff_color色で描画
def draw_oval(self, node, branch, diff_color):
# 円の中心座標を取得
x, y = self.get_oval_coord(branch)
# 円の左上（x1, y1）と円の右下（x2, y2）を計算
coord = (
x - RADIUS,
y - RADIUS,
x + RADIUS,
y + RADIUS,
)
# タグを作成
tag = "oval_" + str(node.number)
# 前回描画時の円の座標を取得
bcoord = self.canvas.coords(tag)
# 前回と座標差分のあるノードだけ色を付ける
if self.judge_same_coord(coord, bcoord):
color = "#FFFFFF"
else:
color = diff_color
# 前回描画した円を削除
if tag in self.drawn_oval:
self.drawn_oval.remove(tag)
self.canvas.delete(tag)
# 円を新しく描画
self.canvas.create_oval(
coord[0], coord[1],
coord[2], coord[3],
fill=color,
tag=tag
)
# 描画した円のタグを覚えておく
self.drawn_oval.append(tag)
# ノードと親ノードを繋ぐ線を描画
def draw_line(self, node, branch):
if len(branch) == 0:
# タグを作成
tag = "line_" + str(node.number)
# 前回描画時した線を削除
if tag in self.drawn_line:
self.drawn_line.remove(tag)
self.canvas.delete(tag)
# 親がないので線は描画しない
return
# ノードの中心座標取得
x, y = self.get_oval_coord(branch)
# 親ノードの中心座標取得
px, py = self.get_oval_coord(branch[:-1])
width = px - x
height = py - y
rad = math.atan2(height, width)
# タグを作成
tag = "line_" + str(node.number)
# 前回描画時した線を削除
if tag in self.drawn_line:
self.drawn_line.remove(tag)
self.canvas.delete(tag)
# 新しく線を描画
self.canvas.create_line(
x + RADIUS * math.cos(rad),
y + RADIUS * math.sin(rad),
px + RADIUS * math.cos(math.pi + rad),
py + RADIUS * math.sin(math.pi + rad),
tag=tag
)
# 描画した線のタグを覚えておく
self.drawn_line.append(tag)
# ノードの数字を描画
def draw_text(self, node, branch):
# ノードの中心座標取得
x, y = self.get_oval_coord(branch)
# タグを作成
tag = "text_" + str(node.number)
# 前回描画時した数字を削除
if tag in self.drawn_text:
self.drawn_text.remove(tag)
self.canvas.delete(tag)
# 新しくテキストを描画
self.canvas.create_text(
x, y,
text=str(node.number),
tag=tag,
font=("", RADIUS, "bold")
)
# 描画したテキストのタグを覚えておく
self.drawn_text.append(tag)
# numberを持つノードの円を除去'
def remove_oval(self, number):
# タグを作成
tag = "oval_" + str(number)
# 前回描画時した線を削除
if tag in self.drawn_oval:
self.drawn_oval.remove(tag)
self.canvas.delete(tag)
# numberを持つノードの線を除去
def remove_line(self, number):
# タグを作成
tag = "line_" + str(number)
# 前回描画時した線を削除
if tag in self.drawn_line:
self.drawn_line.remove(tag)
self.canvas.delete(tag)
# numberを持つノードの数字を除去
def remove_text(self, number):
# タグを作成
tag = "text_" + str(number)
# 前回描画時した円を削除
if tag in self.drawn_text:
self.drawn_text.remove(tag)
self.canvas.delete(tag)
# キャンバスのアップデート
def update(self):
self.canvas.update()
class Controller():
# SortとViewを制御するオブジェクトを生成
def __init__(self, view, tree):
# 制御するViewとTreeのオブジェクト設定
self.view = view
self.tree = tree
self.num_list = []
# ボタンクリック時のイベントを受け付け
self.view.button["command"] = self.button_click
# ボタンクリック時の処理
def button_click(self):
for i in range(DATA_NUM):
self.add(i)
for i in range(DATA_NUM):
self.delete(i)
# 木へのノードの追加を行う
def add(self, i):
num = random.randint(0, DATA_NUM)
# 木へのnumを持つノード追加
self.tree.add_node(num)
print("add:" + str(num))
# 木へのノードの削除を行う
def delete(self, i):
num = random.randint(0, DATA_NUM)
# 木からnumを持つノードを削除
self.tree.delete_node(num)
print("delete:" + str(num))
# アプリ生成
app = tkinter.Tk()
app.title("二分木")
# Viewオブジェクト生成
view = View(app)
# Treeオブジェクト生成
tree = Tree(view)
# Controllerオブジェクト生成
controller = Controller(view, tree)
# mainloopでイベント受付を待機
app.mainloop()
まとめ
この際に２分探索木の復讐をなさってはいかがでしょうか。
そうそう、このPGを動かすときに
開始ボタンがあります。
「反応しねぇな。。。」と思わないで、ボタン押下お願いしますね。