バイナリナビゲーションツリー

バイナリナビゲーションツリー
バイナリ探索のために作成されたツリーをバイナリ探索ツリーと呼ぶ.
親ノードの右側には、親ノードの値よりも大きい値を配置し、左側には親ノードの値よりも小さい値を配置する必要があります.
バイナリナビゲーションツリーのフィーチャー
バイナリ・ナビゲーション・ツリーは、データの挿入順序によってツリーの形状が異なります.

バランスが良好であれば、以下の時間的複雑さを有する.

リソースナビゲーション:O(logn)

資料挿入:O(logn)

データ消去:O(logn)

資料の重複は許されません.

げんかい
バイナリ・ナビゲーション・ツリーは、ツリーが片側に傾いている場合(データが順番に並んでいる場合)にリンク・リストと同じ時間的複雑さを有します.
したがって、データを挿入するときは、ランダムに入力するか、等化されたツリーを作成するように努力する必要があります.
探索する
これがバイナリ探索ツリーの存在の原因である.バイナリ・ナビゲーション・ツリーは、追加の挿入または削除を必要とせず、主に指定された情報をソートおよびナビゲートするために使用されます.ルートノードより大きい値は右に移動し,小さい値は左に移動し,1回のナビゲーションで候補群の半分を減らすことができるため,O(logn)の時間的複雑さがある.
挿入
時間的複雑度はO(logn)である.まず、この値と重複するノードがあるかどうかを確認し、ない場合は最後の検索ノードの適切な位置に挿入します.冗長ノードをチェックすると、ナビゲーション部分にO(logn)の時間的複雑さが現れます.
削除
時間的複雑度はO(logn)である.適切な値を見つけてノードを削除し、一連の操作が必要です.
1)ノードが1つもない
2)ノードがある場合
3)両方のノードが存在する場合
3つの状況に分けて処理しなければならない.
1)の場合は削除するだけです.巡回するたびに、親ノードと私の下方向を変数に格納します.次に、削除するノードが見つかったら、親ノードの私は完全に接続を解除できます.
2)の場合、削除後に接続したノードを親ノードに直接貼り付ける.
3)の場合、削除後は接続されているすべての幹線を切断する.ノードを削除すると、ノードの左側には値より小さい値が存在し、ノードの右側には値より大きい値しか存在しません.したがって、右側のノードを上に移動して親ノードに接続する場合、切断された左側のノードは、削除する前にノードの右側のノードの一番左側に乗って、そのノードに貼り付ける必要があります.
コード#コード#

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            curr = self.root
            while curr is not None:
                if value == curr.value:
                    print("already there is node")
                    return False

                elif value > curr.value:
                    if curr.right is None:
                        curr.right = Node(value)
                        return
                    curr = curr.right
                elif value < curr.value:
                    if curr.left is None:
                        curr.left = Node(value)
                        return
                    curr = curr.left

    def search(self, value):
        curr = self.root
        while curr is not None:
            if value == curr.value:
                return curr
            if value > curr.value:
                curr = curr.right
            else:
                curr = curr.left
        return False

    def remove(self, value):
        parent = None
        direction = "l"
        isHere = False
        curr = self.root
        while curr is not None:

            if value == curr.value:
                isHere = True
                break
            parent = curr
            if value > curr.value:
                direction = "r"
                curr = curr.right
            else:
                direction = "l"
                curr = curr.left

        if not isHere:
            return False

        # 하위 노드가 없는 경우
        if curr.left is None and curr.right is None:
            if direction == "l":
                parent.left = None
            else:
                parent.right = None
        # 하위 노드가 한개 있는 경우
        #   오른쪽

        elif curr.left is None and curr.right is not None:
            if direction == "l":
                parent.left = curr.right
            else:
                parent.right = curr.right
        #   왼쪽

        elif curr.right is None and curr.left is not None:
            if direction == "l":
                parent.left = curr.left
            else:
                parent.right = curr.left

        # 하위 노드가 두 개 모두 있는 경우
        elif curr.right is not None and curr.left is not None:
            if direction == "l":
                parent.left = curr.right
                parent.right = curr.right
                temp = curr.left
                curr = curr.right
                while curr.left is not None:
                    curr = curr.left
                curr.left = temp
            else:
                parent.right = curr.right
                temp = curr.left
                curr = curr.right
                while curr.left is not None:
                    curr = curr.left
                curr.left = temp
        # parent 노드와, 방향을 저장해두어야 함.
        # 오른쪽 하위 노드들을 전부 부모에 갖다붙이고, 삭제하는 왼쪽 노드들을 오른쪽 노드의 최 왼쪽 노드에 갖다 붙임