【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
第9章 木構造と2分探索木
本章で学習するのは木構造です。
9-1 木構造
| 木に関する用語 | 説明 |
|---|---|
| 根 | 最も上流のノードで一つの木に対して根は1個だけ存在する |
| 葉 | 最下流のノードで終端節や外部節とも呼ばれる |
| 非終端節 | 葉を除いたノードで非終端節で内部節とも呼ばれる |
| 子 | あるノードと枝で結ばれた下流側のノードが子で、最下流の葉は子をもたない |
| 親 | あるノードと枝で結ばれた上流側のノードが親で各ノードにとって親は一個だけで根だけは親をもたない |
| 兄弟 | 共通の親を持つノード |
| 先祖 | あるノードから上流側にたどれるすべてのノード |
| 子孫 | あるノードから下流側にたどれるすべてのノード |
| レベル | 根からどれくらい離れているかを示すレベル最上流である根はレベル0 |
| 度数 | 各ノードが持つ子の数。すべてのノードの度数がn以下である木をn進木と呼ぶ |
| 高さ | 根から最も遠い葉までの距離(葉のレベルの最大値) |
| 部分木 | あるノードを根としてその子孫から構成される木 |
| 空木 | ノードや枝が全く存在しない木 |
順序木と無順序木
兄弟関係にあるノードの順序関係を区別する木が順序木、区別しない木が無順序木
順序木の探索
順序木の探索は大きく分けて2つ
幅優先探索/横型探索・・・レベルの低い点から始めて左側から右側へとなぞり、それが終わると次のレベルにくだる方法
深さ優先探索/縦型探索・・・葉に到達するまで下流に下るのを優先する方法。葉に到達した場合はいったん親に戻って、それから次のノードへたどっていきます。縦型探索は次の3種類の走査法に分類されます。(A(親)B(子)C(子)というノードを例に補足)
・行きがけ順(前順/先行順)・・・ノードに立ち寄る→左の子にくだる→右の子にくだる（まず最初にAに立ち寄る）
・通りがけ順(間順/中間順)・・・左の子にくだる→ノードに立ち寄る→右の子にくだる（BからCに行く途中でAに立ち寄る）
・帰りがけ順(後順/後行順)・・・左の子にくだる→右の子にくだる→ノードに立ち寄る（BとCが終わってからAに立ち寄る）
9-2 2分木と2分探索木
現実のプログラムで頻発に利用される2分木と2分探索木を学習します。
2分木
各ノードが左の子と右の子をもつ木を2分木と呼びます。ただし、二つの子の一方あるいはりょほうが存在しないノードがあっても構いません。
単なる2進木との違いは、左の子と右の子とが区別されることです。なお、左の子と根とする部分木を左部分木と呼び、右の子を根とする部分木を右部分木と呼びます。
完全2分木
根から下方のレベルへと、ノードが空くことなく詰まっていて、かつ、同一レベル内では左から右へノードが空くことなく詰まっている完全2分木と呼べます。ノードの詰まり方は次のようになります。
・最下流でないレベルは、すべてのノードが詰まっている。
・最下流のレベルに限っては、左側から詰まっていればよく、途中までしかノードがなくてもよい。
高さがkである完全2分木が持つことのできるノード数は、最大で2**(k+1)-1個のため、n個のノードを格納できる完全2分木の高さはlog nとなります。
| コラム9-1 平衡探索木 |
|---|
このあと以降学習する2分探索木は、キーの昇順にノードが挿入されるような状況では、木の高さが深くなるといった欠点があります。
たとえば、空の2分探索木に対して、１、２、３、４、５の順にノードを挿入すると直線的な木になります。
高さをO(log n)に抑えるように工夫された構造をもつ探索木は平衡探索木と呼ばれます。
2分の平衡探索木としては次のような種類の探索木が考案されています。
・AVL木
・赤黒木
・B木
・2-3木
2分探索木
2分探索木はすべてのノードが次の条件を満たす2分木です。
左部分木のノードのキーは、そのノードのキーより小さく、
右部分木のノードのキーは、そのノードのキーより大きい。
そのため、同一キーをもつノードが複数存在することは許されません。
2分探索木を通りがけ順の縦型探索で走査するとキーの昇順でノードが得られます。
2分探索木は
・構造が単純である。
・通りがけ順の縦型探索によってキーの昇順でノードが得られる。
・2分探索法と似た容量での高速な探索が可能である。
・ノードの挿入が容易である。
などの特徴から、幅広く利用されています。
2分探索木の実現
2分探索木を実現するプログラムを次に示します。
2分探索木
from future import annotations
from typing import Any, Type
class Node:
"""2分探索木のノード"""
def init(self, key: Any, value: Any, left:Node = None, right:Node = None):
"""コンストラクタ"""
self.key = key #キー
self.value = value #値
self.left = left #左ポインタ(左の子への参照)
self.right = right #右ポインタ(右の子への参照)
class BinarySearchTree:
"""2分探索木"""
def __init__(self):
"""初期化"""
self.root = None #根
def search(self, key: Any) -> Any:
"""キーkeyをもつノードを探索"""
p = self.root #根に着目
while True:
if p is None: #これ以上進めなければ
return None #探索失敗
if key == p.key: #keyとノードpのキーが等しければ
return p.value #探索成功
elif key < p.key: #keyのほうが小さければ
p = p.left #左部分木から探索
else: #keyのほうが大きければ
p = p.right #右部分木から探索
def add(self, key: Any, value: Any) -> bool:
"""キーがkeyで値がvalueのノードを挿入"""
def add_node(node: Node, key: Any, value: Any) -> None:
"""nodeを根とする部分木にキーがkeyで値がvalueのノードを挿入"""
if key == node.key:
return False #keyは2分探索木上に既に存在
elif key < node.key:
if node.left is None:
node.left = None(key, value, None, None)
else:
add_node(node.left, key, value)
else:
if node.right is None:
node.right = Node(key, value, None, None)
else:
add_node(node.right, key, value)
return True
if self.root is None:
self.root = Node(key, value, None, None)
return True
else:
return add_node(self.root, key, value)
def remove(self, key: Any) -> bool:
"""キーがkeyのノードを削除"""
p = self.root #走査中のノード
parent = None #走査中のノードの親ノード
is_left_child = True #pはparentの左子ノードか？
while True:
if p is None: #これ以上進めなければ
return False #そのキーは存在しない
if key == p.key: #keyとノードpのキーが等しければ
break #探索成功
else:
parent = p #枝をくだる前に親を設定
if key < p.key: #keyの方が小さければ
is_left_child = True #これからくだるのは左の子
p = p.left #左部分木から探索
else: #keyの方が大きければ
is_left_child = False #これからくだるのは右の子
p = p.right #右部分木から探索
if p.left is None:
if p is self.root:
self.root = p.right
elif is_left_child:
parent.left = p.right #親の左ポインタが右の子を指す
else:
parent.right = p.right #親の右ポインタが左の子を指す
elif p.right is None: #pには右の子がいない
if p is self.root:
self.root = p.right
elif is_left_child:
parent.left = p.left #親の左ポインタが左の子を指す
else:
parent.right = p.left #親の右ポインタが左の子を指す
else:
parent = p
left = p.left #部分木の中の最大ノード
is_left_child = True
while left.right is not None: #最大ノードleftを探索
parent = left
left = left.right
is_left_child = False
p.key = left.key #leftのキーをpに移動
p.value = left.value #leftのデータをpに移動
if is_left_child:
parent.left = left.left #leftを削除
else:
parent.right = left.left #leftを削除
return True
def dump(self) -> None:
"""ダンプ(全ノードをキーの昇順に表示)"""
def print_subtree(node: Node):
"""nodeを根とする部分木のノードをキーの昇順に表示"""
if node is not None:
print_subtree(node.left) #左部分木を昇順に表示
print(f'{node.key} {node.value}') #nodeを表示
print_subtree(node.right) #右部分木を昇順に表示
print_subtree(self.root)
def min_key(self) -> Any:
"""最小のキー"""
if self.root is None:
return None
p = self.root
while p.left is not None:
p = p.left
return p.key
def max_key(self) -> Any:
"""最大のキー"""
if self.root is None:
return None
p = self.root
while p.right is not None:
p = p.right
return p.key
| コラム9-2 キーの降順でダンプ |
|---|
降順のダンプが必要な場合はメソッドdumpを次のように書き換えます。
list9C-1
def dump(self) -> None:
"""ダンプ(全ノードをキーの昇順/降順に表示)"""
def print_subtree(node: Node):
"""nodeを根とする部分木のノードをキーの昇順に表示"""
if node is not None:
print_subtree(node.left) #左部分木を昇順に表示
print(f'{node.key} {node.value}') #nodeを表示
print_subtree(node.right) #右部分木を昇順に表示
def print_subtree_rev(node: Node):
"""nodeを根とする部分木のノードをキーの昇順に表示"""
if node is not None:
print_subtree_rev(node.right) #右部分木を降順に表示
print(f'{node.key} {node.value}') #nodeを表示
print_subtree_rev(node.left) #左部分木を降順に表示
print_subtree(self.root) if reverse else print_subtree(self.root)
9-2
#2分探索木クラスBinarySearchTreeの利用例
from enum import Enum
#from bst import BinarySearchTree
Menu = Enum('Menu', ['挿入', '削除', '探索', 'ダンプ', 'キー範囲', '終了'])
def select_Menu() -> Menu:
"""メニュー選択"""
s = [f'({m.value}){m.name}' for m in Menu]
while True:
print(*s, sep=' ', end='')
n = int(input('：'))
if 1 <= n <= len(Menu):
return Menu(n)
tree = BinarySearchTree()
while True:
menu = select_Menu()
if menu == Menu.挿入:
key = int(input('キー：'))
val = int(input('値：'))
if not tree.add(key, val):
print('挿入失敗！')
elif menu == Menu.削除:
key = int(input('キー：'))
tree.remove(key)
elif menu == Menu.探索:
key = int(input('キー：'))
t = tree.search(key)
if t is not None:
print(f'そのキーをもつ値は{t}です。')
else:
print('該当するデータはありません。')
elif menu == Menu.ダンプ:
tree.dump()
elif menu == Menu.キー範囲:
print(f'キーの最小値={tree.min_key()}')
print(f'キーの最大値={tree.max_key()}')
else:
break
以上で、全部の章が終了しました。
結構駆け足で進めていったこともあり、理解度はあまり高くありませんが、こんな知識があるんだな程度で考えておこうと思います。
ありがとうございました。