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

이진 탐색 트리의 정의

1. 모든 키는 유일하다.
2. 어떤 노드를 특정했을 때 이 노드의 키 값은 왼쪽 서브트리의 그 어떤 키보다 크다.
3. 어떤 노드를 특정했을 때 이 노드의 키 값은 오른쪽 서브트리의 그 어떤 키 값보다 작다.
4. (재귀적 정의) 노드의 서브트리도 이진탐색트리이다.

더 자세한 내용은 여기

Binary search tree - Wikipedia

 

이진 탐색 트리의 ADT

 

BinarySearchTree

• Object

: 유일한 키 값을 가진 노드 집합

 

• Operation

1. BST.insert(key)

: 새로운 키 삽입

2. BST.search(target) → node

: target을 키로 가지는 노드를 찾아 반환

3. BST.delete(target)

: target을 키로 가지는 노드를 삭제

4. BST.min(node) → node

: 매개변수 node를 루트로 하는 이진 탐색 트리에서 가장 작은 key를 가진 노드를 반환

5. BST.max(node) → node

: 매개변수 node를 루트로 하는 이진 탐색 트리에서 가장 큰 key를 가진 노드를 반환

6. BST.prev(cur) → node

: 정렬된 상태에서 cur노드의 바로 이전 노드를 찾아 반환

7. BST.next(cur) → node

: 정렬된 상태에서 cur노드의 바로 다음 노드를 찾아 반환

 

class TreeNode:
    def __init__(self, key):
        self.__key = key
        self.__left = None
        self.__right = None
        self.__parent = None
        
    
    def __del__(self):
        print(f'key {self.__key} is deleted.')
        
    
    @property
    def key(self):
        return self.__key
    
    
    @key.setter
    def key(self, key):
        self.__key = key
        
    
    @property
    def left(self):
        return self.__left
    
    
    @left.setter
    def left(self, left):
        self.__left = left
        
    
    @property
    def right(self):
        return self.__right
    
    
    @right.setter
    def right(self, right):
        self.__right = right
        
        
    @property
    def parent(self):
        return self.__parent
    
    
    @parent.setter
    def parent(self, p):
        self.__parent = p
        
        
    
class BST:
    def __init__(self):
        self.root = None
        
    
    def get_root(self):
        return self.root
    
    
    def preorder_traverse(self, cur, func):
        if not cur:
            return
        
        func(cur)
        self.preorder_traverse(cur.left, func)
        self.preorder_traverse(cur.right, func)
        
    
    def inorder_traverse(self, cur, func):
        if not cur:
            return
        
        self.inorder_traverse(cur.left, func)
        func(cur)
        self.inorder_traverse(cur.right, func)
        
    
    def __make_left(self, cur, left):
        cur.left = left
        if left:
            left.parent = cur
            
    
    def __make_right(self, cur, right):
        cur.right = right
        if right:
            right.parent = cur
            
            
    def insert(self, key):
        new_node = TreeNode(key)
        
        cur = self.root
        if not cur:
            self.root = new_node
            return
        
        while True:
            parent = cur
            if key < cur.key:
                cur = cur.left
                if not cur:
                    self.__make_left(parent, new_node)
                    return
                
            else:
                cur = cur.right
                if not cur:
                    self.__make_right(parent, new_node)
                    return
                
    
    def search(self, target):
        cur = self.root
        while cur:
            if cur.key == target:
                return cur
            
            elif cur.key > target:
                cur = cur.left
            
            elif cur.key < target:
                cur = cur.right
        
        return cur
    
    
    def min(self, cur):
        while cur.left != None:
            cur = cur.left
        return cur
    
    
    def max(self, cur):
        while cur.right != None:
            cur = cur.right
        return cur
    
    
    def __delete_recursion(self, cur, target):
        if not cur:
            return None
        elif target < cur.key:
            new_left = self.__delete_recursion(self, cur.left, target)
            self.__make_left(cur, new_left)
        elif target > cur.key:
            new_right = self.__delete_recursion(self, cur.right, target)
            self.__make_right(cur, new_right)
        else:
            # 리프 노드일 때
            if not cur.left and not cur.right:
                cur = None
            # 왼쪽 자식만 있을 때
            elif not cur.right:
                cur = cur.left
            elif not cur.left:
                cur = cur.right
            # 자식이 둘일 때
            else:
                replace = cur.left
                replace = self.max(replace)
                cur.key, replace.key = replace.key, cur.key
                new_left = self.__delete_recursion(cur.left, replace.key)
                self.__make_left(cur, new_left)
                
        return cur
                
        
    def delete(self, target):
        new_root = self.__delete_recursion(self.root, target)
        selt.root = new_root
        
        
    def prev(self, cur):
        # 왼쪽 자식이 있다면 왼쪽 자식에서 가장 큰 노드
        if cur.left:        
            return self.max(cur.left)
        
        parent = cur.parent
        while parent and cur == parent.left:
            cur = parent
            parent = parent.parent
        
        return parent
    
    
    def next(self, cur):
        if cur.right:
            return self.min(cur.right)
        
        parent = cur.parent
        while parent and cur == parent.right:
            cur = parent
            parent = parent.parent
            
        return parent
    
    
bst = BST()
bst.insert(6)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(5)
bst.insert(8)
bst.insert(10)
bst.insert(9)
bst.insert(11)

f = lambda x : print(x.key, end = ' ')
bst.inorder_traverse(bst.get_root(), f)

BST의 삭제 : 삭제하려는 노드가 리프 노드인지, 자식이 하나만 있는 노드인지, 자식이 둘인지 나누어서 삭제해야 한다.

 

이진 탐색 트리의 시간 복잡도

트리의 높이가 h일 때, 삽입 삭제, 조회 모두 O(h)이다. (h ≒ logN)

그런데, 이진 탐색 트리에 데이터가 정렬된 채로 삽입되어 각 레벨마다 노드가 하나씩만 있는 편향 이진 트리일 경우 삽입, 삭제, 조회 모두 O(n)이 된다.

이런 이유 때문에 생겨난게 레드 블랙 트리 (Red Black Tree) 이다.