[Day 2]バイナリ検索ツリー-第1部

バイナリ検索ツリー

すべてのノードについて、

- 왼쪽 서브트리에 있는 데이터는 모두 혀냊 노드의 값보다 작고
- 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 

上記の性質を満たすバイナリツリー(ただし、重複データがないと仮定)
バイナリ・ナビゲーションを適用するには、ナビゲーション・ターゲットの配列を事前にソートする必要があるため、その配列にデータ要素を追加したり、配列からデータ要素を削除したりするのに要する時間はnに比例します.

整列配列を使用したバイナリナビゲーションと比較

長所

バイナリナビゲーションツリーを使用すると、配列を使用するよりも
データの追加、削除が容易

短所

ですが、スペースが大きいのが欠点です

時間複雑度O(logn)

なし

バイナリナビゲーションツリーの抽象データ構造

データは

を表す.

各ノードは、キー値対

として表す.

キーを使用して

を検索できます.

は、複雑なデータ記録

に拡張可能である.

数字は鍵

名前value

演算の定義

insert(key,data):指定したデータ要素

をツリーに追加

remove(キー):ツリーから特定の要素を削除する

ルックアップ(キー):特定の要素を検索

inorder():キー順にデータ要素

をリストする

分()、max():最小キーと最大キーを持つ要素

に移動

バイナリナビゲーションツリーに要素を挿入

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

初期化

class Node:
    # 초기화
    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None
        
class BinSearchTree:
    # 저번에는 인자를 주었는데 이번에는 none으로 초기화
    def __init__(self):
        self.root = None

inorder traversal

class Node:

    # 이번에는 노드들의 리스트를 만들어서 리턴한다.
    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal

class BinSearchTree:

    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []

min(), max()

# 노드 클래스
class Node:
    
    def min(self):
        if self.left:
            return self.left.min()
        else:
            return self

    def max(self):
        if self.right:
            return self.right.max()
        else:
            return self
            
            
# 이진 탐색 트리 클래스
class BinSearchTree:
    
    def min(self):
        # 루트 노드가 존재하면
        if self.root:
            return self.root.min()
        else:
            return None

    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

lookup()

入力パラメータ:検索対象鍵

は、親ノード(削除用)が見つかったノードを返します.ない場合はNone

を返します

# 노드 클래스
class Node:

    # parent 인자가 주어지지않으면 None으로 생각하라는 말
    def lookup(self, key, parent=None):
        # 지금 방문된 노드(self.key)보다 탐색하려는 키가 작으면 왼쪽으로 가야함
        if key < self.key:
            # 왼쪽 자식이 있을 때
            if self.left:
                # 재귀적으로 호출
                return self.left.lookup(key, self)
            else:
                # 찾으려는 키가 없구나
                return None, None
        
        # 지금 방문된 노드보다 찾으려는 키가 크면 오른쪽으로 가야함
        elif key > self.key:
            # 오른쪽 자식이 있을 때
            if self.right:
                return self.right.lookup(key, self)
            else:
                return None, None
        
        # 찾았다 해당 노드!
        else:
            return self, parent
            
            
# 이진 탐색 트리 클래스
class BinSearchTree:

    def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None

insert()

入力パラメータ:キー、データ要素

戻り:

なし

class Node:
    def insert(self, key, data):
        # 찾으려는 키가 해당노드보다 작은 경우 왼쪽으로
        if key < self.key:
            # 왼쪽 자식 노드가 존재하는 경우
            if self.left:
                self.left.insert(key, data)
            # 존재하지않으면 노드를 단다.
            else:
                self.left = Node(key, data)
                
        # 찾으려는 키가 해당 노드보다 큰 경우 오른쪽으로        
        elif key > self.key:
            # 오른쪽 자식 노드가 존재하는 경우 
            if self.right:
                self.right.insert(key, data)
            # 존재하지 않으면 노드를 단다.
            else:
                self.right = Node(key, data)
                
        # 중복된 노드가 존재하는 경우 에러 발생
        else:
            print("중복된 노드가 존재")

        return True
        
        
class BinSearchTree:
    # 노드 삽입
    def insert(self, key, data):
        # 존재하는 트리라면
        if self.root:
            self.root.insert(key,data)
        
        # 트리가 존재하지않다면 해당 노드를 루트에 넣는다.
        else:
            self.root = Node(key, data)