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

탐색 트리: 탐색을 위한 트리 기반의 자료 구조

일상생활이나 컴퓨터에서 탐색은 매우 중요한 역할을 한다. 우리가 원하는 데이터를 찾을 때 반드시 거쳐야 하는 과정이 탐색이다.
앞서 이진 탐색을 배웠지만, 레코드의 삽입과 삭제가 빈번히 일어나는 테이블에 대해서는 그다지 효율적이라고 말할 수 없었다. 해싱을 사용하면 매우 효율적이지만 메모리를 많이 사용할 뿐더러 해시 충돌과 오버플로 문제를 처리해야 하므로 매우 복잡하다는 단점이 있다.

그래서 고안된 방안이 탐색에 트리 구조를 이용하는 것이다. 즉 탐색을 위한 이진 트리 기반의 자료 구조가 고안되었는데, 이를 이진 탐색 트리라고 한다.

 

이진 탐색 트리의 특성

• 모든 노드는 유일한 키를 갖는다.
• 왼쪽 서브 트리의 키들은 루트의 키보다 작다.
• 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

이진 탐색 트리 역시 이진 트리의 한 종류이므로 순회 연산을 가진다.
그러나 이진 탐색 트리의 목적은 탐색을 하는 것이기 때문에 탐색 연산을 추가로 구현해 주어야 한다.
자신 노드를 기준으로 자신의 키보다 작은 키들은 왼쪽 서브 트리에, 자신의 키보다 큰 키들은 오른쪽 서브트리에 저장되어 있으므로 키를 이용한 탐색은 비교적 쉽게 구현할 수 있으며 매우 효율적이다(O(log n)).
값을 이용한 탐색 역시 구현할 수 있다. 그러나 트리의 모든 노드를 검사해야 하므로 탐색의 효율은 떨어진다(O(n)).

삽입 연산의 구현은 간단하게 할 수 있다. e를 삽입하고 싶다면, 이진 탐색 트리에서 e를 탐색한 후(당연히 탐색에 실패할 것이다) 탐색에 실패한 위치에 e를 삽입해주면 된다.

그러나 삭제 연산의 구현이 비교적 복잡할 수도 있다. 삭제 연산은 삭제할 노드가 단말 노드인 경우, 하나의 자식을 갖는 경우, 두 개의 자식을 갖는 경우로 3가지로 나누어서 각각 구현해 주어야 한다.

• 단말 노드의 경우: 자식 노드가 없기 때문에 그 노드만 지우면 된다.
• 자식이 하나인 노드의 경우: 자신 대신에 유일한 자식을 부모 노드에 연결해주고 자신을 삭제한다.
• 두 개의 자식을 모두 갖는 노드의 경우: 삭제할 노드와 킷값이 비슷한 노드(후계자)를 부모 노드와 연결한 후 자신을 삭제한다. 후계자 노드는 최대/최소 키 탐색 방법을 이용한다.

---

이진 탐색 트리의 구현

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

def search_bst(n, key): # 키를 이용한 탐색 재귀
    if n is None:
        return None
    elif n.key == key:
        return n
    elif n.key > key:
        return search_bst(n.left, key)
    else:
        return search_bst(n.right, key)

def search_value_bst(n, value): # 값을 이용한 탐색 (전위 순회)
    if n is None:
        return None
    elif value == n.value:
        return n
    res = search_value_bst(n.left, value)
    if res is not None:
        return res
    else:
        return search_value_bst(n.right, value)

def search_max_bst(n):
    while n is not None and n.right is not None:
    # n.right가 None인 노드가 가장 오른쪽 노드임. 그 n을 반환.
        n = n.right
    return n

def search_min_bst(n):
    while n is not None and n.left is not None:
    # n.left가 None인 노드가 가장 왼쪽 노드임. 그 n을 반환.
        n = n.left
    return n

def insert_bst(root, node):
    if node.key < root.key: # 삽입할 노드의 키가 루트의 키보다 작을 경우
        if root.left is None: # node는 루트의 왼쪽 자식이 됨.
            root.left = node
            return True # 삽입 성공
        else:
            return insert_bst(root.left, node)
    elif node.key > root.key: # 삽입할 노드의 키가 루트의 키보다 클 경우
        if root.right is None: # node는 루트의 오른쪽 자식이 됨.
            root.right = node
            return True # 삽입 성공
        else:
            return insert_bst(root.right, node)
    else: # 키가 중복될 경우
        return False # 키가 중복되면 삽입하지 않음.

def delete_bst_case1(parent, node, root): # 단말 노드의 삭제
    if parent is None: # node == root로 비교해도 될 듯?
        root = None
    else:
        if parent.left == node:
            parent.left = None
        else:
            parent.right = None
    return root

def delete_bst_case2(parent, node, root): # 자식이 하나인 노드의 삭제
    if node.left is not None:
        child = node.left
    else:
        child = node.right

    if node == root:
        root = child
    elif node == parent.left:
        parent.left = child
    else:
        parent.right = child
    return root

def delete_bst_case3(parent, node, root): # 두 개의 자식을 모두 갖는 노드의 삭제
    succp = node # 후계자의 부모 노드
    succ = node.right # 후계자 노드는 node의 오른쪽 자식
    while succ.left != None: # 후계자의 왼쪽 노드가 없을 때까지 찾는다.
        succp = succ 
        succ = succ.left

    if succp.left == succ: # 후계자가 후계자 부모의 왼쪽 자식이면
        succp.left = succ.right # 후계자의 자리(후계자 부모의 왼쪽 자식)에 후계자의 자식 연결.
    else: # 근데 이 경우가 있을 수 있나...? 오른쪽 서브트리의 가장 왼쪽 자식이 후계자인데.
        succp.right = succ.right # 후계짜의 자리(후계자 부모의 오른쪽 자식)에 후계자의 자식 연결.

    node.key = succ.key # 삭제할 노드의 키를 후계자의 키로 바꿔줌.
    node.value = succ.value # 삭제할 노드의 값을 후계자의 값으로 바꿔줌.

    return root # 반환 안해줘도 되는데 일관성을 위해 root 반환.

def delete_bst(root, key): # 이 3가지 경우를 종합한 삭제 연산
    if root is None: # 공백 트리
        return None

    parent = None
    node = root
    while node is not None and node.key != key:
        parent = node
        if key < node.key:
            node = node.left
        else:
            node = node.right
    # 여기까지 parent를 찾는 과정!
    # 찾을 key값을 가진 노드(node)도 찾았다!

    if node == None: # 삭제할 노드가 없을 때
        return None
    elif node.left is None and node.right is None: # 자식 노드가 없는 노드 삭제
        root = delete_bst_case1(parent, node, root)
    elif node.left is None or node.right is None: # 자식 노드가 1개인 노드 삭제
        root = delete_bst_case2(parent, node, root)
    else: # 자식 노드가 2개인 노드 삭제
        root = delete_bst_case3(parent, node, root)

    return root # 삭제 완료한 루트 노드 반환

 

시간 복잡도

트리 연산의 시간 복잡도는 트리의 높이에 비례한다.
포화 이진 트리의 높이가 log n이므로 최선 경우 모든 연산의 시간 복잡도는 O(log n)이 된다.
그러나 만약 n개의 노드들이 한 쪽으로 치우친 경사 이진 트리의 경우 높이는 n이 되므로 최악 경우 모든 연산의 시간 복잡도는 O(n)이 된다.

---

이진 탐색 트리의 응용) 맵

import 탐색트리

def inorder(n):
    if n is not None:
        inorder(n.left)
        print(n.key, end=" ")
        inorder(n.right)
        
class BSTMap:
    def __init__(self):
        self.root = None

    def isEmpty(self):
        return self.root == None

    def clear(self):
        self.root = None
        
    def search(self, key):
         return 탐색트리.search_bst(self.root, key) # 이진탐색트리에서 구현한 키로 탐색

    def findMax(self):
        return 탐색트리.search_max_bst # 이진탐색트리에서 구현한 최대값 탐색

    def findMin(self):
        return 탐색트리.search_min_bst # 이진탐색트리에서 구현

    def insert(self, key, value=None):
        n = 탐색트리.BSTNode(key, value)
        if self.isEmpty():
            self.root = n
        else:
            탐색트리.insert_bst(self.root, n)

    def delete(self, key):
        self.root = 탐색트리.delete_bst(self.root, key)

    def display(self, msg="BSTMap :"):
        print(msg, end="")
        inorder(self.root)
        print()

 

이진 탐색 트리의 응용) AVL 트리와 AVL 트리로 구현한 맵

위에서 이진 탐색 트리의 효율성을 위해서 노드들이 균형을 이루는 게 좋다는 것을 알 수 있었다.
AVL트리는 균형 인수를 이용해 항상 균형 트리를 보장하기 때문에, 탐색과 삽입, 삭제 연산에서 항상 O(log n)의 처리 시간을 보장한다.

AVL 트리는 모든 노드에서 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차가 1을 넘지 않는 이진 탐색 트리이다. 즉 모든 노드의 균형 인수는 0이나 1, -1이 된다.

이렇게 균형 인수를 유지하기 위해 삽입 연산이 일어날 때 회전이 발생한다. 균형을 유지하기 위해 때에 따라 LL회전, LR회전, RL회전, RR회전의 네 종류 회전이 알맞게 선택된다.

import 이진트리8장
import 탐색트리
import 탐색트리맵

def rotateLL(A):
    B = A.left
    A.left = B.right
    B.right = A
    return B

def rotateRR(A):
    B = A.right
    A.right = B.left
    B.left = A
    return B

def rotateRL(A):
    B = A.right
    A.right = rotateLL(B)
    return rotateRR(A)

def rotateLR(A):
    B = A.left
    A.left = rotateRR(B)
    return rotateLL(A)

def calc_height_diff(parent): # 왼쪽과 오른쪽 서브트리의 높이 차를 반환하는 함수
    if parent is None:
        return 0
    return 이진트리8장.calc_height(parent.left) - 이진트리8장.calc_height(parent.right)

def reBalance(parent):
    hDiff = calc_height_diff(parent)

    if hDiff > 1: # 왼쪽에 불균형
        if calc_height_diff(parent.left) > 0:
            return rotateLL(parent) # 왼쪽-왼쪽 불균형
        else:
            return rotateLR(parent) # 왼쪽-오른쪽 불균형
    elif hDiff < -1: # 오른쪽에 불균형
        if calc_height_diff(parent.right) < 0:
            return rotateRR(parent) # 오른쪽-오른쪽 불균형
        else:
            return rotateRL(parent) # 오른쪽-왼쪽 불균형
    return parent # 불균형이 아니면 아무것도 없이 반환

def insert_avl(parent, node): # 재균형 함수(회전)을 사용한 삽입 연산
    if node.key < parent.key:
        if parent.left is not None:
            parent.left = insert_avl(parent.left, node) # return 쓰는 재귀 아님...
        else:
            parent.left = node
        return reBalance(parent)

    elif node.key > parent.key:
        if parent.right is not None:
            parent.right = insert_avl(parent.right, node) # 역시 재귀 아님...
        else:
            parent.right = node
        return reBalance(parent)

    else:
        print("중복된 키 에러")


class AVLMap(탐색트리맵.BSTMap): # AVL트리로 맵을 구현한다. BST맵과 다 동일하고 insert, display만 바뀐다.
    def __init__(self):
        super().__init__()

    def insert(self, key, value=None):
        n = 탐색트리.BSTNode(key, value)
        if self.isEmpty():
            self.root = n
        else:
            self.root = insert_avl(self.root, n)

    def display(self, msg='AVLMap :'):
        print(msg, end='')
        이진트리8장.levelorder(self.root) # 이진트리 맵과 달리 레벨순회를 사용한다.

 

 

작성일자: 2023-03-14