자료구조 | 이진 탐색 트리

1. 이진 탐색 알고리즘(binary search algorithm)

---

정렬된 데이터로 된 리스트(배열이나 연결 리스트)가 인수로 들어왔을 때 요소 중에 찾고자 하는 데이터가 있는지 알아보는 알고리즘 → $O(\log n)$

def binary_search(li, target):
	# li: 정렬된 리스트
	start = 0
    end = len(li) - 1
    
    while start <= end:
    	middle = (start + end) // 2
        if li[middle] == target:
        	return middle
        elif li[middle] > target:
        	end = middle - 1
        else:
        	start = middle + 1
    
    return None

2. 이진 탐색 트리(binary search tree, BST)

---

• 노드에 직접 데이터 저장 X → 데이터에 대한 참조만 저장(키)

• 모든 키는 유일

• 어떤 노드를 특정했을 때 이 노드의 키 값은 왼쪽 서브 트리의 그 어떤 키보다 큼

• 어떤 노드를 특정했을 때 이 노드의 키 값은 오른쪽 서브 트리의 그 어떤 키 값보다 작음

• 노드의 서브 트리도 이진 탐색 트리

• 대부분의 경우, 트리 높이 h는 $\log n$ (아닌 경우도 있음)

2-1. 이진 탐색 트리의 활용

• 집합, 딕셔너리 → 내부적으로 이진 탐색 변형인 균형 이진 탐색 트리 사용

• 딕셔너리 구현 → BST(균형 이진 트리 - 레드 블랙 트리), 해시 테이블

2-2. 이진 탐색 트리의 단점

• 이진 탐색 트리에 데이터가 정렬되어 삽입되는 경우 편향 이진 트리를 나타낼 수 있고, 이 때 삽입, 삭제, 탐색 모두 $O(n)$ 이다.

• 앞선 문제를 보완한 이진 탐색 트리가 균형 이진 트리이다.

• 균형 이진 트리는 편향 이진 트리가 되지 않도록 자동으로 트리 높이를 낮춰 최악의 경우라도 $O(\log n)$이 되도록 함

3. 이진 탐색 트리 구현

---

3-1. 트리 노드 구현

class TreeNode:
	def __init__(self, key):
        self.__key = key
        self.left = None
        self.right = None
        self.parent = None

	def __del__(self):
    	print('key {} is deleted'.format(self.__key))
    
    @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

3-2. 편의 함수 구현

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(cur.left, 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 

3-3. 삽입, 삭제, 탐색 함수 구현

• BST.insert(key): 새로운 키 삽입

• BST.search(target): target을 키로 가지는 노드를 찾아 반환

• BST.delete(target): target을 키로 가지는 노드 삭제

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

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

• BST.prev(cur): 정렬된 상태에서 cur 노드의 바로 이전 노드를 찾아 반환

• BST.next(cur): 정렬된 상태에서 cur 노드의 바로 다음 노드를 찾아 반환

• 삽입 (insert)

    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

• 탐색(search)

    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

• 삭제 (delete)
  • 삭제하려는 노드가 리프 노드인 경우, 자식이 하나만 있는 노드인 경우, 자식이 둘인 경우에 따라 나누어 삭제
  • 자식 노드가 두 개일 대는 대체 노드를 찾아 키 값을 교환한 후 대체 노드를 삭제함
  • 대체 노드는 반드시 리프 노드이거나 왼쪽 자식만 있는 노드

    def __delete_recursion(self, cur, target):
        if not cur:
            return None
        elif target < cur.key:
            new_left = self.__delete_recursion(cur.left, 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(repalce)
                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)
        self.root = new_root

• min, max

    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

• prev, next

    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

4. 참고 자료

---

양태환, 『파이썬으로 배우는 자료 구조 핵심 원리』, 길벗