バイナリナビゲーションツリー
原理:値がParent Nodeより小さい場合は左にノードを生成し、値がParent Nodeより大きい場合は右にノードを生成します.

ノードの作成

class Node:
  def __init__(self,value):
     self.value=value
     self.left= None
     self.right=None

リンクリスト接続の使用

バイナリナビゲーションツリーの挿入

    def insert(self,value): #이진트리 탐색 삽입
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left!=None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left= Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node= self.current_node.right
                else:
                    self.current_node.right=Node(value)
                    break      

現在のノードをルートノードとして指定し、挿入位置を検索します.
現在のノード値より小さい場合は左に移動します.
現在のノード値より大きい場合は右に移動
重要なのは、値を比較するときの空間です
たとえば、現在のノードの値より小さい場合は左に移動する必要がありますが、現在のノードの左側にノードが存在しない場合は、その空間にノードを挿入するだけで、ノードが存在する場合は、現在のノードを左に移動するだけです.

バイナリ検索ツリーのナビゲート

許容値がツリーに存在するかどうかを決定します.

def search(self,value):
        self.current_node= self.head
        while self.current_node:
            if self.current_node.value==value:
                return print(True)
            elif value < self.current_node.value:
                self.current_node=self.current_node.left
            else :
                self.current_node=self.current_node.right
        return print(False)

while文に現在のノードの値が存在する場合にのみ機能します.
現在のノードの値が入力値より大きい場合は、左に移動します.
時間右に移動
どうじぎゃくしん

バイナリ検索ツリーの削除

削除が多すぎる
まず,入力値に対応するノードの位置をブラウズする.

        searched = False # 이 트리에 FAlse면 존재X
        self.current_node=self.head
        self.parent= self.head # 삭제할 노드 위에 있는 parent node
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent= self.current_node
                self.current_node= self.current_node.left
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right
        if searched == False:
            return print(False)

ナビゲーション時
削除するノードの場所を見つけて削除を続行

を削除するノードがリーフノードである場合
リーフノードとは、子孫がいない場合のことです
この場合、子孫がいないので文句はありません.
削除するノードの親ノードとの接続を解除すると

になります.

  if self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
            del self.current_node

削除するノードにはサブノードがあります.
削除するノードの子ノードが削除するノードの左側か右側かを検索し、削除するノードを削除し、削除するノードの子ノードを親ノードに接続すると

になります.

   if self.current_node.left != None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left=self.current_node.left
            else:
                self.parent.right=self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left= self.current_node.right
            else :
                self.parent.right=self.current_node.right

3.最後にすべてのサブノードがある場合
この場合状況の数は少し複雑です
まず二つの種類に分けます.

削除ノードが親ノードの左側にある場合、

削除ノードが親ノードの右側にある場合、

1番目の場合
ノードを削除する右側のノードで、一番安いやつを見つければいい.
その馬は削除ノードの右側ノードから左に移動し続けるだけです.
ここでまた状況の数が起こった
1-1. ノードの右側のノードを削除して一番左のノードを検索するときに、ノードにサブノード(つまりノードの右側のノード)がある場合
1-2. ノードの右側のノードを削除して最も左側のノードを検索すると、そのノードにはサブノードがありません.

つまり,17番ノードが存在するか否かで区切る.

            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent= self.change_node
                    self.change_node = self.change_node.left
                self.change_node_parent.left = None
                if self.change_node.right != None:
                    self.change_node_parent.left=self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.current_node.left

change nodeとchange nodeの親ノードを作成します.
ドアを通って一番左へ移動
ノードがこれ以上左に移動できない場合は,右側のノードがあるか否かに応じて処理する.
右側のノードがない場合、current nodeはchange nodeになります.
Change nodeの左右側はcurrent nodeの左右側です.
親ノードから削除するノードが左側にあるためです.
親ノードの左側には、削除するノードではなくchange nodeが表示されます.
逆に、親ノードの右側に削除するノードがある場合は、現在作成されているコードで親ノードのchange nodeを右側に接続するだけです.