Data structures (with python) - 8.Tree - 8.2 Binary Search Tree

Data structures (with python) - 8.Tree - 8.2 Binary Search Tree

 

💡 A binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node’s left subtree and less than the ones in its right subtree.

정렬된 이진 트리 또는 정렬된 이진 트리라고도 하는 이진 검색 트리는 각 내부 노드의 키가 해당 노드의 왼쪽 하위 트리에 있는 모든 키보다 크고 오른쪽 하위 트리에 있는 키보다 작은 루팅된 이진 트리 데이터 구조입니다.

 

8.1 binary tree 에 이어서

Binary search tree 입니다.

 

Binary Search Tree 는 이름에 왜 Search가 들어가 있을까?

이름만 봐서는 search 가 중간에 들어가 있는데 보이듯이, 이진트리의 한 종류이지만 search 하는데 (특정 조건하에) 장점이 있어서 따로 배운다고 볼 수 있다.

 

이진트리의 정의는 8.1 에서 각 노드가 최대 두개의 자식 노드를 가지는 트리 구조이다. 노드의 배치에 제한이나 규칙이 없다.

 

반면, 이진 검색 트리(이하 BST)에서는 노드의 배치에 특별한 규칙이 있다.

BST에서는 각 노드에 대해 그 노드의 값이 왼쪽 서브트리의 모든 노드의 값보다 크고, 오른쪽 서브트리의 모든 노드의 값보다 작아야 한다는 규칙이 있다.

이 규칙 덕분에 BST에서는 값을 검색 할 떄, 현재 노드의 값과 찾고자 하는 값을 비교하여 왼쪽 or 오른쪽 서브트리로 이동하면 됩니다.

 

따라서 BST는 데이터를 효율적으로 검색할 수 있는 구조를 가지게 됩니다. 이러한 이유로 'Search'가 이름에 표함 되어 있습니다.

 

 

BST의 특징

- 각 노드의 키는 고유

- 왼쪽 서브트리의 모든 노드의 키는 그 루트의 키보다 작다.

- 오른쪽 서브트리의 모든 노드의 키는 그 루트의 키보다 크다.

- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

 

이러한 특징 덕분에, BST는 검색, 삽입, 삭제 등의 연산을 효율저긍로 수행할 수 있습니다.

평균저긍로 이러한 연산들의 시간 복잡도는 O(log N) 입니다.

 

In Python

Python 에서 BST를 구현하려면 이진트리 때와 비슷하게 유사하게 노드 클래스를 생성하고, 이 클래스에 검색, 삽입, 삭제 메소드를 추가해야 합니다.

 

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

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

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert(self.root, key)

    def _insert(self, node, key):
        if key < node.key:
            if node.left is None:
                node.left = Node(key)
            else:
                self._insert(node.left, key)
        else:
            if node.right is None:
                node.right = Node(key)
            else:
                self._insert(node.right, key)

    def search(self, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node is None or node.key == key:
            return node
        if key < node.key:
            return self._search(node.left, key)
        return self._search(node.right, key)

 

BST 클래스는 BST의 루트 노드를 저장하며,

insert 메소드와 search 메소드를 제공합니다.

 

Insert 메소드는 새로운 키를 삽입, search 메소드는 주어진 키를 가진 노드를 검색합니다.

이 메소들들은 _insert , _search 메소드를 사용해 재귀적으로 작동한다.

 

BST는 이런 방식으로 구현할 수 있지만, 위의 코드는 균형 잡힌 트리를 유지하지 못하는 문제가 있습니다.

최악의 경우 트리가 한 쪽으로 치우쳐져서 시간복잡도가 O(n)이 될 수 있다.

 

이를 해결하기 위해서는 AVL 트리나 레드-블랙 트리 등의 균형 검색 트리를 사용해야 한다.

(균형 검색트리는 차후 다룬다.)