[Python 자료 구조] 이진 탐색 트리 (Binary Search Trees)

(A binary search tree of size 9, wikipedia)

#이진 탐색 트리이진 탐색 트리 (Binary Search Trees)

- 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리 (중복되는 데이터 원소는 없는 것으로 가정)

 

#연산의 정의

• insert(key, data) : 트리에 주어진 데이터 원소를 추가
• remove(key) : 특정 원소를 트리로 부터 삭제
• lookup(key) : 특정 원소를 검색
• inorder() : 키의 순서대로 데이터 원소를 나열
• min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색

 

#insert(key, data) 

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)

 

 

#remove(key)

    def remove(self, key):
        node, parent = self.lookup(key)

        if node:
            nChildren = node.countChildren()

            if nChildren == 0:
                if parent:
                    if parent.left == node:
                        parent.left = None
                    if parent.right == node:
                        parent.right = None

                else:
                    self.root = None

 

 

#lookup()

    def lookup(self, key, parent=None):
        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

 

 

#inorder()

    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal

 

 

#min(), max()

    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

 

 

#이진 탐색 트리의 원소 삽입 연산 구현

class Node:

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

    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:
            raise KeyError
        
        return True

    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 __init__(self):
        self.root = None

    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)

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

def solution(x):
    return 0

 

 

 

#원소 삭제

(1) 방법

 - 키(key)를 이용해서 노드를 찾는다

 - 해당 키의 노드가 없으면 삭제할 것도 없음

 - 노드가 있으면 찾은 노드의 부모 노드도 알고 있어야 함

 - 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리함

(2) 인터페이스 설계

 - 입력: 키(key)

 - 출력: 삭제한 경우 True, 해당 키의 노드가 없는 경우 False

 def remove(self, key):
        node, parent = self.lookup(key)
        if node:
			...
            return True
        else:
            return False

(3) 이진 탐색 트리 구조의 유지

 - 삭제되는 노드가 말단(leaf) 노드인 경우

    : 그냥 그 노드를 없애면 됨

    → 부모 노드의 링크를 조정 

 - 자식을 하나 가지고 있는 경우

    : 삭제되는 노드 자리에 그 자식을 대신 배치

    → 자식이 왼쪽인지 오른쪽인지

    → 부모 노드의 링크를 조정 (좌/우 알고 있어야 함)

 

- 자식을 둘 가지고 있는 경우

    : 삭제되는 노드보다 바로 다음 큰 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치

    → 해당 노드를 삭제

#이진 탐색 트리가 효율적이지 못한 경우

 - 순서대로 삽입하는 경우 효율적이지 못하다

 - 한쪽으로 치우치는 모양