이진탐색트리(Binary Search Tree) - 삭제 연산

이진탐색트리의 핵심은 정렬된 상태를 유지하면서 빠르게 탐색하는것 입니다.

배열은 정렬하면 탐색은 빠르지만 삽입/삭제가 느리고, 리스트는 삽입은 빠르지만 탐색이 느립니다.

 

이 이진탐색트리는 그 중간을 노린 구조입니다.

 

대표적인 활용케이스는

1. 검색 시스템

• 값 찾기 : O(log n)
• 예 : 사용자 ID, 세션, 키-값 조회
• 내부적으로는 Redis 같은 시스템도 트리/해시 기반 구조를 섞여 사용합니다.

2. 정렬된 데이터 유지

• 항상 왼쪽< 부모 < 오른쪽
• 중위 순회(inorder)하면 자동 정렬
• 예:
  • 로그 시간순 정렬
  • 점수 랭킹 시스템

3. 범위 검색(Range Query)

• 10이상 50이하 데이터만 뽑고싶을때
• BST는 이런 범위 탐색이 효율적
• DB 인덱스에서 핵심 개념

즉, 삽입/삭제/탐색을 모두 적당히 빠르게 처리하면서 정렬 상태를 유지해야 할 때 사용하게되는 구조입니다.

아래 그림을 보면서 이해해 봅시다.

 

[그림1]

[그림1]삭제하고 싶은 노드를 x, x의 자식인 왼쪽 subtree를 a, 오른쪽 subtree를 b라고 칭했을때 

x자리에 a subtree를 올리고, a subtree에서 maxnode(가장 높은값을 가진 노드)아래에 b subtree를 붙입니다.

[그림2]

따라서 위 [그림2]와 같은 형태가 되어야합니다.

 

이것을 Python을 이용하여 구현하면 아래와 같습니다.

 

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

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

    def deleteByMerging(self, x):
        a = x.left
        b = x.right
        pt = x.parent

        if a != None:
            c = a
            m = a
            while m.right != None:
                m = m.right
            m.right = b
            if b != None:
                b.parent = m
        else:
            c = b

        if c != None:
            c.parent = pt

        if pt != None:
            if pt.left == x:
                pt.left = c
            else:
                pt.right = c
        else:
            self.root = c
            if c != None:
                c.parent = None