なにこれ

前回の続き。

blog.frogdusk.com

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

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

BinaryTree

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

f:id:frogdusk:20190719171123p:plain

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

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

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

深さ優先探索

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

f:id:frogdusk:20190719171202p:plain

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

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

幅優先探索

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

f:id:frogdusk:20190719171215p:plain

BinarySearchTree

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

f:id:frogdusk:20190719171227p:plain