こんばんは(*´ω｀)
素人の私としては、
ぱっとみ、なんやねん"木"って。。
(有識者の皆様すみませんm(_ _)m)
木構造は、データ間の階層的な関係を表現するデータ構造らしいです。
個人的には前回の Hash chain の延長のように見えました。
どんな考え方なのかワクワクしたので
とりあえず、いじっていきます(笑)
class Node:
def __init__(self,key,value,left:None,right:None):
self.key = key
self.value = value
self.left = left
self.right = right
そのままかもしれませんが、ノードの中身を書いてみました。
このような形で Node の中に入っている left , right の各領域に更に Node が格納されているのでしょう。
もう少し、木っぽくしてみました。
Hash chain と似ていますね、面白い。
きっとデータの格納方法にもルールがあるのでしょう。はい、ありました、ルール。。
2分探索木は、全てのノードが次の条件を満たす2分木です。
左部分木のノードキーは、そのノードキーより小さく
右部分木のノードキーは、そのノードキーより大きい
左部分木とは、左の子、右部分木とは、右ノ子、、子!?(笑)
誰から見て右 or 左を判断するか、それは分岐点で考えれば問題なさそうです。
如何ですか？何処をとっても、前述の条件は満たしていますよね！？
でも、なんでそんなルールを設けるのでしょうか?( 一一)
その理由は、先ほど設けた key の設定ルールにあります。
試しに key = 5 を探しましょう。
1.Start 地点は Root(根)と言われている 11 から始まります。
探している key は 5 でした。
現在地(=11)より小さい key は左側に格納されているのでした。
2.left pointer を開いてみましょう。
その Node の中には、ありました、key = 5!!
めでたく goal です。
では、もう一つ、key = 9 を探してみましょう。
遷移を様子を赤字で色付けしました。
1.start from 11(root), key(=9) < 11 なので、左へ Go!!
2.key(=9) は 5 より大きいので右へ Go!!
3.key(=9) は 7 より大きいので右へ Go!!
あった key = 9 !!, ゴ----ル!!
なるほど、Hash chain で設けた next pointer を工夫することで
更に簡潔でありながら、複雑なデータ構造を論理的に実現しています。
すばらしい!!
class Node:
def __init__(self,key,value,left:None,right:None):
self.key = key
self.value = value
self.left = left
self.right = right
class BinarySearchTree:
def __init__(self):
self.root = None
def search(self,key):
#root から start !!
p = self.root
while True:
#root には何も接続されていない構造なら return None
if p.key is None:
return None
#key が該当したら p.value を return
if p.key == key:
return p.value
#最初は前述の p.key == key は pass されるので、
#以下の右 or 左への遷移を記述
elif p.key < key:
p = p.right
else:
p = p.left
取りあえず、基本となる Node を記述し、
探索する記述を追加しました。
現段階では Tree も何も出来ていません。
今は空である Root しかありません。
ここに Node を追加していきましょう。
まず最初は、root から作っていきましょう。
def add(self,key,value):
#冒頭で以下のように Node で定義していました。
#class BinarySearchTree:
# def __init__(self):
# self.root = None
if self.root is None:
#root にも該当データが格納されている可能性があります。
#left , right はこれから作るので取りあえず、None にしておきます
self.root = Node(key,value,None,None)
else:
#既に root に Node が挿入されている場合、
#root からスタートして Node を追加していく必要があります。
#察しの通り、 add_node を再帰で構成していきます。
BinarySearchTree.add_node(self.root,key,value)
root の作成を完了したら、
root を基準に Node を前述の二分木の定義沿って、ガンガン追加していきます。
次は再帰で分岐していく add_node の記述です。
def add_node(node,key,value):
#key の重複を見つけたら Fail
if key == node.key:
return print("fail to add")
#新規Node.key < 既存Node.key の場合は、left に格納!
elif key < node.key:
# pointer left がカラの場合は、新規 Node として追加
if node.left is None:
node.left = Node(key,value,None,None)
# 既に left には格納がある場合は、再帰で処理
else:
BinarySearchTree.add_node(node.left,key,value)
else:
# pointer right がカラの場合は、新規 Node として追加
if node.right is None:
node.right = Node(key,value,None,None)
# 既に right には格納がある場合は、再帰で処理
else:
BinarySearchTree.add_node(node.right,key,value)
return True
add を実行するたびに root から start し、該当ポインタを探して Node を追加していきます。
まるで、root から栄養を貰った、植物が、自分の成長定義に沿って、
少しずつ伸びていく様は、まさしく"木(tree)"ですね。脈打つ生き物見たいです。
テキストコードを読み、書きしながら、そんなイメージを作って
ニヤニヤしてる自分はおかしいですかね？！(*´з`)
自分の成長を感じてるってことですよ(笑)。
次に remove です。
前述していますが、 Add は root から始まり、
該当箇所を探して随時 Node を追加するアクションを取っています。
よって、 remove も同じで、
削除する Node を root から探しに行きます。
ちょっと複雑です。
難しく考えすぎかもしれませんが、
その時は突っ込みをお願い致します。m(_ _)m
では行きましょう。
前述しているように root から全てが始まります。
それって、root で欲しいものがあれば終わりますし、
root が、そもそも key がなかったら終わりですよね？？
def remove(self,key):
#pointer を p として、root から start します。
p = self.root
#右から来たか、左から来たか、後で役に立つフラグです。
direction_is_left = None
while True:
# root or Node に key が無い場合は、False を返して終了
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
# Node に含まれる key が入力 key と一致したら break で while を抜けます
if p.key == key:
print("find out the Node")
break
# key が Node に該当しない場合は前述にあるルールで進行方向 右、左を選択します。
# この時、進行方向の flag にも値を与えておきます(direction_is_left)
else:
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
下図にあるように、削除する Node に子がいない場合と子が1人しかいない場合、
どのように削除しましょう？？
その場合は一つ上の親.left or .right を触れないと何もやりようが無さそうです。
よって、前述の記述に"親" を追加して、削除 node の探索と、その親も特定して削除しやすくなるようにします。
def remove(self,key):
p = self.root
parent = None #空(カラ)の親を用意
direction_is_left = None
while True:
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
if p.key == key:
print("find out the Node")
break
else:
#右 or 左のどちらに行こうと関係ないので、p の値を p.left or p.rightと
#更新する前に parent として p を代入しておきます。
parent = p
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
さぁ、再掲します!
子が none or 1人いる場合は、左部分 or 右部分に集中している場合です。
# 右が一切ない、そう、左部分の場合を指します
if p.right is None:
# p へは親から見ると左から来たのですよね？
if direction_is_left:
#上図、左の場合、1 の Node の left は None が格納されています
#上図、右の場合、4 の Node の left は Node 1 が可能されています
parent.left = p.left
else:
#?? ↓これなに ? ('Д')。すいません、以下に図示します。
parent.right = p.left
でもこれって、例えば、root を削除したい場合もあるわけですよね？
前述にある記述だと、右側に node が居ないわけですから、
左側の node を代入して root としないといけないですよね？
っというわけで、root を削除する場合も追加します。
if p.right is None:
if p == self.root: # root を削除したいの??
self.root = p.left # じゃあ、左 Node を root としましょう。
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
これは右が無いケースでの話なのであれば、
左が無いケースでも同じですよね？
っというわけで、左がない version も記載しておきます。
if p.left is None:
if p == self.root:
self.root = p.right
if direction_is_left:
parent.left = p.right
else:
parent.right = p.right
elif p.right is None:
if p == self.root:
self.root = p.left
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
では、ここが一番の難所なのですが、
子が 2 人いる Node を削除したい場合はどうしましょう？
上図にあるように 5 を削除したい場合です。
確か、こんなルールありましたよね？
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
2分探索木は、全てのノードが次の条件を満たす2分木です。
左部分木のノードキーは、そのノードキーより小さく
右部分木のノードキーは、そのノードキーより大きい
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
つまり、左部分の子から最大値を抜き出して、
代入出来れば、右部分の子ともつながりますよね？
そうなんです、子が二人いる場合は、
上記の考えで、最大値を探し出し、
削除したい Node を上書きします。
後処理として、探し出した最大値は削除します。
図にある通りにコードに落としてみます、4 が最大ですね。
else:
# 5 の情報を後で使うかもしれません。
# parent として残しておきましょう
parent = p
# parent の左側の Node を left とする
left = p.left
# 進行方向は左なので True です
direction_is_left = True
#上図にあるように、 5 の left にあたる 4 の Node が
#左部分の子の中で最大値になります。
# Node 5 の情報を Node 4 へと書き換えましょう。
p.key = left.key
p.value = left.value
# Node 4 を削除しましょう。
# 具体的には parent.left に left.left の 1 を代入 !! って、そのまま(笑)
if direction_is_left:
parent.left = left.left
# ↓ なんぞ ?? これ ??
else:
parent.right = left.left
最後に謎の記述がありました。
一件、平和に closed した更新ですが、
Tree の構成が、このような場合は如何でしょうか？
left から更に right に分岐していった場合、
right は値がドンドン大きくなります。
そこで最大値を探しだす方法も追加しないといけません。
else:
parent = p
left = p.left
direction_is_left = True
#右側探索を追加!!
#left.right が None になるまで left を更新します
while left.right is None:
#右側の Node を見つけたら、parent と left を更新
parent = left
left = left.right
# 右から来たことを False で宣言
direction_is_left = False
p.key = left.key
p.value = left.value
if direction_is_left:
parent.left = left.left
#右から探し出した Node を最大値とする場合は、
#left.left を parent.right に接続します。
else:
parent.right = left.left
っというわけで、remove は大ボリュームとなりました。
def remove(self,key):
p = self.root
parent = None
direction_is_left = None
while True:
if p.key is None:
print("root has no Node or tree has no Node that you want,faile")
return False
if p.key == key:
print("find out the Node")
break
else:
parent = p
if p.key > key:
direction_is_left = True
p = p.left
else:
direction_is_left = False
p = p.right
if p.left is None:
if p == self.root:
self.root = p.right
if direction_is_left:
parent.left = p.right
else:
parent.right = p.right
elif p.right is None:
if p == self.root:
self.root = p.left
if direction_is_left:
parent.left = p.left
else:
parent.right = p.left
else:
parent = p
left = p.left
direction_is_left = True
while left.right is None:
parent = left
left = left.right
direction_is_left = False
p.key = left.key
p.value = left.value
if direction_is_left:
parent.left = left.left
else:
parent.right = left.left
return True
remove でやりたい事をイメージできていると
何となく読めてくると思います。
お疲れ様でした ( ´ー｀)y-~~