<エンコードテストレベル1>12日-バイナリナビゲーションツリー

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

이진 탐색 트리は、이진 탐색と링크드 리스트とを組み合わせた資料構造である.
バイナリ検索の時間的複雑度はO(Logn)と非常に速いが,配列されているため,資料の挿入や削除はできない.
また,링크드 리스트では,資料の入力や削除に要する時間的複雑度はO(1)であるが,資料を探索するためにはO(n)の時間的複雑度が必要である.
すなわち,バイナリ検索とリンクリストはいずれも利点と欠点を明確にしているので,2つの利点のみを組み合わせたのが이진 탐색 트리である.
バイナリ・ナビゲーション・ツリーは、次の条件が追加されたツリーです.

例として、上記の条件を満たすツリーを使用します.

1番と2番の条件が満たされているかどうか見てみましょう.
ルートノード7の左側サブツリーには3,1,5ノード,右側サブツリーには10,8ノードが存在する.
左側のサブツリーの値はルートノードより小さく、右側のサブツリーの値はルートノードより大きく、条件を満たします.
また,すべてのノードは重複せず,左側サブツリーと右側サブツリーもバイナリナビゲーションツリーであるため,すべての条件を満たす.

📌 バイナリナビゲーションツリーの巡回

前章では、3種類の木の巡り方を学びました.
バイナリナビゲーションツリーの特性を考慮して、ルートノードから左側のサブノードに沿って下に進むと、どのような値が得られますか?
ツリー全体にわたって、最小の値が得られます.
1つのノードAの左側のサブノードは、Aより小さい値を含む必要があるからである.
右側の木に沿って歩き続けると、もちろん木に最大の値があります.
すなわち、最も左側のノードからナビゲーションを開始し、最も右側のノードからナビゲーションを終了する중위 순회方式を用いて、バイナリナビゲーションツリーのすべての値を順番に読み出すことができる.

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

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

    def set_root(self, data):
        self.root = Node(data)

BST = BinarySearchTree()
BST.set_root(1)

print(BST.root.data)

📌 バイナリナビゲーションツリーの検索

バイナリナビゲーションツリーには、基本的にデータ挿入、データ検索、データ削除機能があるはずです.演算を実行する前に、ツリーの参照方法について説明しましょう.
バイナリ・ナビゲーション・ツリーの例を使用して、バイナリ・ナビゲーション・ツリーでデータを検索する方法を説明します.

バイナリ・ナビゲーション・ツリーには、親ノードが左側の子ノードより大きく、右側の子ノードより小さい特性があります.これを利用して,有効な探索を行うことができる.
上記の例では、8を参照する方法について説明します.

8は7より大きいため、ターゲット値は右側のサブツリーに存在します.
したがって,左側サブツリー(1,3,5)を考慮する必要はない.右側のサブツリーに移動します.


今回、右側のサブノードの値はターゲット値8より大きい.
したがって,ターゲット値は左側のサブツリーに存在することが分かった.
左側のサブツリーに移動します.


希望する値が見つかり、検索に成功しました.
ツリーに必要な値が存在しない場合は、どのように判断しますか?
""ツリーに必要な値はありません.
さて、今回は目標値を4に設定して、ナビを行います.
一般的には、すぐにノード5に移動して経過を確認してください.

ノード5に着きました.ノード5とターゲット値4を比較すると、ターゲット値が小さくなるため、左側のサブツリーに移動します.
ただし、ノード5は、サブノードが存在しない리프 노드(leaf node)である.
△木の葉のことをLeaf Nodeと言います.
この場合、値が見つからないタグを返し、ブラウズを終了します.

📌 データ・ナビゲーションの実装

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

    def set_root(self, data):
        self.root = Node(data)

    def find(self, data):
        if self.find_node_by_data(self.root, data) == False:
            return False
        else:
            return True

    def find_node_by_data(self, current_node, data):
        if current_node == None:
            return False
        print(current_node.data)
        if data == current_node.data:
            return current_node

        if data < current_node.data:
            return self.find_node_by_data(current_node.left, data)
        if data > current_node.data:
            return self.find_node_by_data(current_node.right, data)

def temp_data_insert(root):
    node_2 = Node(3)
    node_3 = Node(10)
    root.left = node_2
    root.right = node_3

    node_4 = Node(1)
    node_5 = Node(5)
    node_2.left = node_4
    node_2.right = node_5

    node_6 = Node(8)
    node_3.left = node_6
    return root

BST = BinarySearchTree()
BST.set_root(7)
BST.root = temp_data_insert(BST.root)
BST.find(5)

基本構造は木の巡りと同様に再帰構造を呈する.
現在のノードがターゲット値より大きい場合は、左側のサブノードに戻ります.
現在のノードがターゲット値より小さい場合は、右側のサブノードに戻ります.
tmp data insert関数は、データの挿入を学習する前に一時的に使用される関数です.
ノードの左、右に直接値を挿入するのはよくありません.

📌 バイナリ・ナビゲーション・ツリーのデータの挿入

新しいデータノードは、既存のツリーのリーフノードに貼り付ける必要があります.
サンプルツリーからデータ4を追加すると、次のように追加されます.

ここで12,15を順に挿入すると、ツリーは以下のようになります.

ツリーにデータを挿入するには、レイヤごとに値を比較する必要があります.
木の高さが100の場合、最悪の場合は100回の値を比較します.したがって,データ挿入の時間的複雑さはO(h)である.

📌 データ挿入の実装

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

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

    def set_root(self, data):
        self.root = Node(data)

    def find(self, data):
        if self.find_node_by_recursion(self.root, data) == False:
            return False
        else:
            return True

    def find_node_by_recursion(self, current_node, data):
        if current_node == None:
            return False
        if data == current_node.data:
            return current_node

        if data < current_node.data:
            return self.find_node_by_recursion(current_node.left, data)
        if data > current_node.data:
            return self.find_node_by_recursion(current_node.right, data)

    def insert(self, data):
        if self.root == None:
            self.set_root(data)
        else:
            self.insert_node(self.root, data)

    def insert_node(self, current_node, data):
        if data == current_node.data:
            print(f"이미 {data}값이 존재합니다. 중복된 값은 삽입할 수 없습니다.")
            return
        if data < current_node.data:
            if current_node.left == None:
                current_node.left = Node(data)
            else:
                self.insert_node(current_node.left, data)

        elif data > current_node.data:
            if current_node.right == None:
                current_node.right = Node(data)
            else:
                self.insert_node(current_node.right, data)

BST = BinarySearchTree()
BST.set_root(7)

BST.insert(3)
BST.insert(1)
BST.insert(5)
BST.insert(10)
BST.insert(8)

print("root -> left -> left : ", BST.root.left.left.data)
print("root -> left -> right : ", BST.root.left.right.data)
print("root -> right -> left : ", BST.root.right.left.data)

BST.insert(4)
BST.insert(12)
BST.insert(15)

print("root -> right -> right : ", BST.root.right.right.data)
print("root -> right -> right -> right : ", BST.root.right.right.right.data)

📌 データ消去

1つ目は、削除されたターゲットノードにサブノードがないことです.
この場合、ノードを削除するだけで済みます.上記の例では、1、4、8、15番のノードに対応しています.


サブノードが1つしかない場合.
このとき、ターゲットを削除する親ノードは、ターゲットを削除する子ノードに関連付けられます.

上記の例では、12は10の右側のサブツリーです.
すなわち,12をルートノードとするすべてのサブツリーは10より大きい.
10より小さいと、10の右側の子供に入ることができないからだ.
したがって,12を削除しながら10と15を接続すると,12ノードの削除は終了する.


サブノードが2つある場合.

上記の例では3番ノードを削除すべきであることを考慮してください.
7番ノードと3番ノードのサブノードはどのように接続すればよいのでしょうか
上のツリー중위 순회 방식に移動すると、以下のリストが表示されます.

1 3 4 5 7 8 10 12 15

このとき,3番ノードの右側のサブツリーの最小値を見ると,4番ノードであることがわかる.そして中尉巡回出力のリストには、三と四がある.
したがって,3番ノードの位置に4を代入し,既存の4番ノードを削除すると,中尉巡行時にデータが整列状態を保ち,バイナリ探索ツリー構造も崩壊しない.

1  /3/  4 5 7 8 10 12 15

Marinの例では、4番ノードにはサブノードがありませんが、サブノードがある場合、コードは葛藤しませんか?
削除先ノードの場所にコピーされるノードの制限は次のとおりです.

ターゲットノードの右側のサブツリーの最小値を削除
バイナリ検索ツリーのループでは、ツリーの最小値は、ルートノード上で左側のサブノードに沿って下に進むと見つかります.

ツリーの最小値は、左側のサブノードが存在しないことを示します.
したがって、コピー先ノード(削除先ノードの右側のサブツリーの最小値)は、データ削除方法の1回または2回に相当するサブノードが最大1つしかありません.

📌 データ消去の実装と完全なコード

削除するノードの右側のサブノードをパラメータとして受信し、サブノードをルートノードとするサブツリーの最小値ノードを返します.
サンプルツリーでは、3番ノードを削除しようとすると、関数は5番ノードをパラメータとして受け入れ、最小ノード4番を返します.

削除を担当する関数.

ターゲットノードを削除します.サブノードはありませんか?

削除対象ノードは左側のサブノードのみですか?

ターゲットノードを削除するには右側のサブノードしかありませんか?

ターゲットノードの2つのサブノードを削除しますか?

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

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

    def set_root(self, data):
        self.root = Node(data)

    def find(self, data):
        if self.find_node_by_recursion(self.root, data) == False:
            return False
        else:
            return True

    def find_node_by_recursion(self, current_node, data):
        if current_node == None:
            return False
        if data == current_node.data:
            return current_node

        if data < current_node.data:
            return self.find_node_by_recursion(current_node.left, data)
        if data > current_node.data:
            return self.find_node_by_recursion(current_node.right, data)

    def insert(self, data):
        if self.root == None:
            self.set_root(data)
        else:
            self.insert_node(self.root, data)

    def insert_node(self, current_node, data):
        if data == current_node.data:
            print(f"이미 {data}값이 존재합니다. 중복된 값은 삽입할 수 없습니다.")
            return
        if data < current_node.data:
            if current_node.left == None:
                current_node.left = Node(data)
            else:
                self.insert_node(current_node.left, data)

        elif data > current_node.data:
            if current_node.right == None:
                current_node.right = Node(data)
            else:
                self.insert_node(current_node.right, data)

    def get_next_node(self, node):
        while node.left != None:
            node = node.left
        return node

    def delete(self, data):
        if self.root == None:
            print("트리에 노드가 존재하지 않습니다.")
        else:
            self.delete_node(None, self.root, data)

    def delete_node(self, parent, current_node, data):
        if current_node == None:
            print(f"트리에 {data}가 존재하지 않습니다.")
            return

        if data < current_node.data:
            self.delete_node(current_node, current_node.left, data)
        elif data > current_node.data:
            self.delete_node(current_node, current_node.right, data)
        else:
            if current_node.left == None and current_node.right == None:
                if data < parent.data:
                    parent.left = None
                else:
                    parent.right = None
            elif current_node.left != None and current_node.right == None:
                if data < parent.data:
                    parent.left = current_node.left
                else:
                    parent.right = current_node.left
            elif current_node.left == None and current_node.right != None:
                if data < parent.data:
                    parent.left = current_node.right
                else:
                    parent.right = current_node.right

            elif current_node.left != None and current_node.right != None:
                next_node = self.get_next_node(current_node.right)

                current_node.data = next_node.data
                self.delete_node(current_node, current_node.right, next_node.data)

def in_order(node):
    if node == None:
        return
    in_order(node.left)
    print(f"{node.data}  ", end="")
    in_order(node.right)

BST = BinarySearchTree()
BST.set_root(7)

BST.insert(3)
BST.insert(1)
BST.insert(5)
BST.insert(10)
BST.insert(8)

BST.insert(4)
BST.insert(12)
BST.insert(15)

BST.delete(10)

in_order(BST.root)