こんばんは(*´ω｀)

素人の私としては、
ぱっとみ、なんやねん"木"って。。
(有識者の皆様すみませんm(_ _)m)

木構造は、データ間の階層的な関係を表現するデータ構造らしいです。

個人的には前回の Hash chain の延長のように見えました。
どんな考え方なのかワクワクしたので
とりあえず、いじっていきます(笑)

test.py

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 を工夫することで
更に簡潔でありながら、複雑なデータ構造を論理的に実現しています。
すばらしい!!

test.py

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 から作っていきましょう。

test.py

    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 の記述です。

test.py

    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 がなかったら終わりですよね？？

test.py

    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 の探索と、その親も特定して削除しやすくなるようにします。

test.py

    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 右部分に集中している場合です。

test.py

          # 右が一切ない、そう、左部分の場合を指します
          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 を削除する場合も追加します。

test.py

          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 も記載しておきます。

test.py

        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 が最大ですね。

test.py

        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 は値がドンドン大きくなります。
そこで最大値を探しだす方法も追加しないといけません。

test.py

        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 は大ボリュームとなりました。

test.py

    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-~~