面接準備/資料構造7/ツリー


代表的なデータ構造7:ツリー


1.ツリー構造

  • ツリー:NodeとBranchを使用して構築されたデータ構造
  • は実際にどこでよく使われていますか?
  • ツリー構造におけるバイナリツリーは、検索アルゴリズム
  • の実装によく用いられる.

    2.必要な用語

  • ノード:ツリーに格納データの基本要素(データおよび他の関連ノードのブランチ情報を含む)
  • Root Node:ツリー上部のノード
  • レベル:トップレベルノードが0レベルの場合、
  • はサブブランチに接続されたノードの深さを表します.
  • ノード:あるノードに接続する次のレベルノード
  • Child Node:あるノードに接続するより高いレベルのノード
  • Leaf Node:Child Nodeのノードが1つもない
  • Brother Node:同じParent Nodeを持つノード
  • Depth:ツリー内のノードの最大レベル
  • 3.バイナリツリーとバイナリ検索ツリー

  • バイナリツリー:ノードの最大分岐数が2のツリー
  • バイナリ検索ツリー:バイナリ検索ツリーには、次の追加条件があります.
  • 左側ノードはノードより小さい値を有し、右側ノードはノードより大きい値を有する.

  • (出典:https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

    4.資料構造バイナリナビゲーションツリーの利点と主な用途

  • 主な用途:データ検索(ナビゲーション)
  • の利点:ナビゲーション速度
  • が向上
    欠点は、バイナリナビゲーションツリーアルゴリズムを理解してから表示する必要があることです.

    バイナリツリーと整列配列間のナビゲーション比較



    (出典:https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

    5.オブジェクト向けPythonプログラミングによるリンクリストの実装


    5.1. ノードクラスの作成

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

    5.2. バイナリナビゲーションツリーにデータを入れる

  • バイナリナビゲーションツリーの条件を満たすデータ
  • を入力する.
    class NodeMgmt:
        def __init__(self, head):
            self.head = head
        
        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
    head = Node(1)
    BST = NodeMgmt(head)
    BST.insert(2)

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

    class NodeMgmt:
        def __init__(self, head):
            self.head = head
        
        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 True
                elif value < self.current_node.value:
                    self.current_node = self.current_node.left
                else:
                    self.current_node = self.current_node.right
            return False        
    head = Node(1)
    BST = NodeMgmt(head)
    BST.insert(2)
    BST.insert(3)
    BST.insert(0)
    BST.insert(4)
    BST.insert(8)
    BST.search(-1)

    5.4. バイナリナビゲーションツリーの削除

  • は非常に複雑です.もしそうであれば、それらを別々に理解したほうがいい:
  • 5.4.1. Leafノードの削除

  • Leaf Node:Child NodeのないNode
  • 削除するノードのParentノードは削除するノードを指しません.
  • 5.4.2. Childノードが1つしかないノードを削除

  • 削除するノードのParentノードは、削除するノードのChildノードを指す.
  • 5.4.3. 2つのChild NodeのNodeを削除

  • ノードを削除する右側のサブノードのうち、最小値のノードを削除するParentノード.
  • 削除するノードの左側のサブノードで、最大値を削除するノードのParentノードが指します.
  • 5.4.3.1. ノードの右側のサブノードを削除するには、最小値を削除するノードのParent Nodeがそのノードを指します.
    削除するノードの右側のサブノード
  • を選択
    右サブアイテムの一番左のノード
  • を選択
  • ノードの左側のブランチは、そのノードを削除するノード
  • を指す.
  • ノードの左側ブランチは削除するノードの左側Childノードを指し、
  • である.
  • このノードの右側ブランチは削除するノードの右側Childノードを指し、
  • .
  • ノードが右側のChildノードを有する場合、ノードの元のノードの左側ブランチは、右側のChildノード
  • を指す.

    5.5. バイナリナビゲーションツリー削除コードの実装と分析


    5.5.1削除するノードへ移動


    削除するノード
  • がなければ、処理も行わなければならない
  • に削除可能なノードがない場合はFalseに戻り、関数
  • を終了する.
    # def delete(self, value):
        searched = False
        self.current_node = self.head
        self.parent = self.head
        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 False
        
        ### 이후부터 Case들을 분리해서, 코드 작성

    5.5.2. ケース1:削除するノードがLeaf Nodeの場合


    # self.current_node 가 삭제할 Node, self.parent는 삭제할 Node의 Parent Node인 상태
        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

    5.5.2. Case 2:削除するノードがChildノードが1つしかない場合。


        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

    5.5.3. Case 3-1:削除するノードにChildノードが2つある場合(削除するノードがParentノードの左側にある場合)

  • 基本利用可能戦略
  • ノードを削除する右側のサブノードのうち、最小値のノードを削除するParentノード.
  • 削除するノードの左側のサブノードで、最大値を削除するノードのParentノードが指します.
  • 基本利用可能ポリシーでは、1番ポリシー実装コードを使用します.
  • には2つのケースがあります
  • Case 3-1:削除するノードがParent Nodeの左側にあり、削除するノードの右側のサブノードに最小値のノードがないChild Nodeの場合、
  • .
  • Case 3-1-2:削除するノードがParent Nodeの左側にあり、削除するノードの右側のサブノードのうち、最小値を持つノードの右側にChild Nodeがある場合.
  • の最小値を有するノードのChild Nodeは左側にない.左側Nodeがあることは、ノードよりも小さな値を有するノード
  • を意味するからである.
        if self.current_node.left != None and self.current_node.right != None: # case3
            if value < self.parent.value: # case3-1
                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
                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.change_node.left

    5.5.4. Case 3-2:削除するノードに2つのChildノードがある場合(削除するノードがParentノードの右側にある場合)

  • 基本利用可能戦略
  • ノードを削除する右側のサブノードのうち、最小値のノードを削除するParentノード.
  • 削除するノードの左側のサブノードで、最大値を削除するノードのParentノードが指します.
  • 基本利用可能ポリシーでは、1番ポリシー実装コードを使用します.
  • には2つのケースがあります
  • Case 3-2-1:削除するノードがParent Nodeの右側にあり、削除するノードの右側のサブノードに最小値のノードがないChild Nodeの場合、
  • .
  • Case 3-2:削除するノードがParent Nodeの右側にあり、削除するノードの右側のサブノードのうち、値が最も小さいノードの右側にChild Nodeがある場合
  • の最小値を有するノードのChild Nodeは左側にない.左側Nodeがあることは、ノードよりも小さな値を有するノード
  • を意味するからである.
            else:
                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
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right

    5.5.5. Pythonフルコードの実装

    class Node:
        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None
    
            
    class NodeMgmt:
        def __init__(self, head):
            self.head = head
        
        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 True
                elif value < self.current_node.value:
                    self.current_node = self.current_node.left
                else:
                    self.current_node = self.current_node.right
            return False        
        
        def delete(self, value):
            # 삭제할 노드 탐색
            searched = False
            self.current_node = self.head
            self.parent = self.head
            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 False    
    
            # case1
            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
            
            # case2
            elif 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        
            
            # case 3
            elif self.current_node.left != None and self.current_node.right != None:
                # case3-1
                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
                    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.change_node.left
                # case 3-2
                else:
                    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
                    if self.change_node.right != None:
                        self.change_node_parent.left = self.change_node.right
                    else:
                        self.change_node_parent.left = None
                    self.parent.right = self.change_node
                    self.change_node.right = self.current_node.right
                    self.change_node.left = self.current_node.left
    
            return True
    注意:http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html

    5.5.6. Pythonフルコードのテスト

  • ランダムライブラリの使用
  • random.randint(最初の数値、最後の数値):最初の数値から最後の数値までの数値をランダムに選択し、返します.
  • 例:random.randint(0,99):0から99までランダムに数値を選択し、
  • を返します.
    # 0 ~ 999 숫자 중에서 임의로 100개를 추출해서, 이진 탐색 트리에 입력, 검색, 삭제
    import random
    
    # 0 ~ 999 중, 100 개의 숫자 랜덤 선택
    bst_nums = set()
    while len(bst_nums) != 100:
        bst_nums.add(random.randint(0, 999))
    # print (bst_nums)
    
    # 선택된 100개의 숫자를 이진 탐색 트리에 입력, 임의로 루트노드는 500을 넣기로 함
    head = Node(500)
    binary_tree = NodeMgmt(head)
    for num in bst_nums:
        binary_tree.insert(num)
        
    # 입력한 100개의 숫자 검색 (검색 기능 확인)
    for num in bst_nums:
        if binary_tree.search(num) == False:
            print ('search failed', num)
    
    # 입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택
    delete_nums = set()
    bst_nums = list(bst_nums)
    while len(delete_nums) != 10:
        delete_nums.add(bst_nums[random.randint(0, 99)])
    
    # 선택한 10개의 숫자를 삭제 (삭제 기능 확인)
    for del_num in delete_nums:
        if binary_tree.delete(del_num) == False:
            print('delete failed', del_num)

    6.バイナリナビゲーションツリーの時間的複雑さと欠点


    6.1. 時間の複雑さ(ナビゲート時)

  • の深さ(木の高さ)をhと表記すると、O(h)
  • n個のノードがある場合、h=log 2{n}$であるため、時間的複雑度は$O(log{n})$-bigoシンボルでは、$log{n}のログの下部は10ではなく2であることに注意してください.
    -実行するたびに実行可能なコマンドの50%が削除されることを意味します.これは、稼働時間を50%削減できることを意味します.
  • (出典:https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

    6.2. バイナリナビゲーションツリーの欠点

  • の平均時間複雑度は$O(log)$であった.
  • はツリーバランス時の平均時間複雑度であり,
  • である.
  • は、(O(n)O(n)O(n)O(n)O(n)