OpenDataStructures第6章を自分用にまとめる(二分木)

なにこれ

前回の続き。

blog.frogdusk.com

二分木を扱います。今までデータ構造としてリストと違う概念として捉えていましたが、
ポインタという概念を使った連結リストを勉強した後だと、実装としてはそれの発展系でしかないことがわかり、理解しやすかったです。

• BinaryTree
• BinarySearchTree -> SSetインターフェース

BinaryTree

Treeの概念は以下です。各ノードはparent・left・rightという最大3つのノードへのポインタを保持しています。 rootのみparentがnullです。

各ノードを辿る場合は再帰が使えます。

def traverse(self, u):
        if u == None: return
        self.traverse(u.left)
        self.traverse(u.right)

ただし、再帰の場合は、木が深い場合に、スタックオーバーフローしてしまう可能性があります。 そこで以下の2つの探査方法があります。

深さ優先探索

各ノードを辿るにあたって、どこから来たかによって次の行き先を決めるのが深さ優先探索です。

3つのルールで動いており、黒塗りしているノードを見てみるとわかりやすいです。

1. parentから来た場合はleftにいく
2. leftから戻ってきた場合はrightにいく
3. rightから戻ってきた場合はparentに戻る

幅優先探索

Queueを用意します。
rootをQueueに入れ、Queueの先頭のノード(root)から処理、各ノードは処理する時にleft, rightをQueueに追加します。
次のノードはQueueの先頭から取り出し続けます。

BinarySearchTree

BinaryTreeをベースにノードに値を持たせたものがBinarySearchTreeで、SSetインターフェースの実装にあたります。
値の保持の仕方にルールがあり、あるノードuをみたとき、u.leftを根とする部分木に含まれる値は全てu.xより小さく、u.rightを根とする部分木に含まれる値は全てu.xより大きいです。

• 木の形状を整えるという機構がない実装である
• そのため値の追加の仕方によっては木がすごくアンバランスになることがあり、addやremove・findの実行時間はO(n)である