트리(2) - 이진탐색트리

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 알고리즘 내용입니다

목차

• <이진 탐색 트리(BST)>
• 이진 탐색 트리 구축, 탐색 과정을 그림으로 이해
• 이진 탐색 트리 구현

 

<이진 탐색 트리(BST)>

이진 탐색 트리(BST, Binary search tree)

• 이진탐색(binary search)과 연결리스트(linked list)를 결합한 트리
• 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됨.

 - 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)으로 빠르지만 자료 입력, 삭제가 불가능하다.

 - 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)이다.

 

이진 탐색 트리의 속성

• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드만 존재한다.
  
• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드만 존재한다.
  
• 중복된 노드가 없어야 한다. 
  
• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.

 

이진 탐색 트리 구축, 탐색 과정

구축 과정

탐색 과정 - 정렬된 배열보다 효율적임.

 

이진 탐색 트리 구현

# None 클래스 정의 - 노드값, 왼쪽/오른쪽 노드
class Node(object):
    def __init__(self, data):
    self.data = data
    self.left = self.right = None

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

    #삽입
    def insert(self, data):
        self.root = self._insert_value(self.root, data)
        return self.root is not None
    def _insert_value(self, node, data):
        if node is None:
            node = Node(data)
        else:
            if data <= node.data:
                node.left = self._insert_value(node.left, data)
            else:
                node.right = self._insert_value(node.right, data)
        return node
    
    #탐색
    def find(self, key):
        return self._find_value(self.root, key)
    
    def _find_value(self, root, key):
        if root is None or root.data == key:
            return root is not None
        elif key < root.data:
            return self._find_value(root.left, key)
        else:
            return self._find_value(root.right, key)

    #삭제
    def delete(self, key):
        self.root, deleted = self._delete_value(self.root, key)
        return deleted
    def _delete_value(self, node, key):
        if node is None:
            return node, False
        
        deleted = False
        if key == node.data:
            deleted = True
            if node.left and node.right:
                # replace the node to the leftmost of node.right
                parent, child = node, node.right
                while child.left is not None:
                    parent, child = child, child.left
                child.left = node.left
                if parent != node:
                    parent.left = child.right
                    child.right = node.right
                node = child
            elif node.left or node.right:
                node = node.left or node.right
            else:
                node = None
        elif key < node.data:
            node.left, deleted = self._delete_value(node.left, key)
        else:
            node.right, deleted = self._delete_value(node.right, key)
        return node, deleted

#결과
array = [40, 4, 34, 45, 14, 55, 48, 13, 15, 49, 47]

bst = BinarySearchTree()
for x in array:
    bst.insert(x)

# Find
print(bst.find(15)) # True
print(bst.find(17)) # False

# Delete
print(bst.delete(55)) # True
print(bst.delete(14)) # True
print(bst.delete(11)) # False