[자료구조] 이진 탐색 트리(2) (삭제, 시간 복잡도)

이진 탐색 트리 삭제 II

3. 삭제하려는 데이터의 노드가 두 개의 자식이 있을 때

우선 지우려는 노드의 오른쪽 자식(16)으로 간다. 여기서, find_min 메소드의 파라미터에 root 대신 이 16을 넣어주면 된다. 여기서 가장 작은 노드는 14이다. 여기서 어떻게 이진 탐색 트리의 속성을 해치지 않고 12의 위치를 대체할 수 있는지 생각해보자.

12 기준 오른쪽 자식 노드는 왼쪽 자식 노드들보다 전부 크다. 그렇기 때문에 12를 14로 바꿔도 왼쪽 노드는 상관이 없다. 14는 12보다 큰 데이터 중 가장 작은 데이터이다. 14가 12의 위치를 대체해도 오른쪽 모든 노드는 14보다 크다.

이진 탐색 트리에서는 어떤 노드보다 큰 모든 노드 중 가장 작은 노드, 그러니까 값 기준으로 어떤 노드의 바로 다음 순번인 노드를 successor라고 한다. 지우려는 노드를 successor 노드로 대체하는 방법을 알아보자.

successor 노드 데이터를 지우려는 노드 데이터에 저장한다. 즉 노드 내부의 데이터만 바꾸는 것이다. 그 이후 successor 노드를 지운다. 이 때 successor 노드는 오른쪽 자식 노드만 갖고 있거나(successor는 대상 노드보다 큰 값 중 가장 작은 값이므로 왼쪽 자식 노드가 있다면 모순이다.) leaf노드여야 한다.

이진 탐색 트리 삭제 연산 시간 복잡도

1. 탐색

삭제 연산을 하려면 우선 삭제하려는 데이터를 갖는 노드를 탐색해야 한다. 탐색 트리 높이를 h라고 할 때, 탐색 연산은 O(h)의 시간 복잡도가 걸린다.

삭제는 세 가지 경우가 있다고 했다.

지우려는 데이터 노드가 leaf 노드일 때

이 때는 탐색한 노드의 부모에서 자식 레퍼런스를 None으로 지정해주면 됐다. 걸리는 시간이 노드 개수나 트리 높이에 비례하지 않고 O(1)이 걸린다.

지우려는 데이터 노드가 하나의 자식이 있을 때

삭제하려는 노드의 부모의 자식을 삭제하려는 노드의 자식으로 만들어 줬다. 이 때는 어떤 노드인지와 상관없이 그냥 레퍼런스 2개만 연결시켜주면 된다. 이 경우도 O(1)이 걸린다.

지우려는 데이터 노드가 두 개의 자식이 있을 때

이 경우 세 단계가 있었다.

1. 먼저 지우려는 데이터 노드의 successor 노드를 찾는다.
2. 지우려는 노드에 successor 노드의 데이터를 저장한 후
3. successor 노드를 지운다.

1단계에서 successor 노드를 구하는 연산은 얼마나 걸릴까? successor 노드는 삭제하려는 노드의 오른쪽 자식을 find_min 메소드의 파라미터로 넘겨줘서 구했었다.

find_min.py

def find_min(node):
    """(부분)이진 탐색 트리의 가장 작은 노드 리턴"""
    temp = node

    while temp is not None:
        if temp.left_child is not None:
            temp = temp.left_child
        else:
            return temp

find_min 메소드는 총 O(h)가 걸린다고 했다. 그렇기 때문에 1단계에선 O(h)이 걸린다.

2단계는 단순히 노드에 데이터를 넣는 단계라서 O(h)가 걸리고, 3단계는 successor가 오른쪽 자식 노드가 있으면 O(2), 없으면 O(1)이 걸리기 때문에 결국 O(1)이 걸린다.

합쳐 보면 총 O(h + h + 1) = O(h)이 걸린다.

정리해보면,

	탐색	탐색 후 단계들
경우 1	O(h)	O(1)
경우 2	O(h)	O(1)
경우 3	O(h)	O(h)

이렇게 된다. 이제 탐색 후 단계들의 시간 복잡도에, 방금 잠시 제외해뒀던 탐색 연산 자체의 시간 복잡도 O(h)까지 더해주면 각 경우의 시간 복잡도는 모두 O(h)이 걸린다. 삭제 연산도 나머지 연산들과 마찬가지로 총 O(h)의 시간 복잡도를 갖는 것이다.

이진 탐색 트리 높이 h 분석

트리의 높이가 h라고 할 때, 이진 탐색의 가장 기본적인 연산들인 탐색, 삽입, 삭제의 시간 복잡도는 모두 O(h)이다. 따라서 이진 탐색 트리는 높이가 낮을수록 여러 연산을 하기에 효율적이라는 것을 알 수 있다.

이진 탐색 트리는 완전 이진 트리가 아닌 경우가 더 많다. 그렇기 때문에 노드가 n개 있을 때, 높이 h가 항상 O(log(n))이라고 할 수 없다.

최악의 경우를 예로 들자면, 이진 탐색 트리의 높이는 O(n)이 될 수 있는데, 이진 탐색 트리에 데이터로 1, 2, 3, 4, 5, 6을 순서대로 삽입한다면:

이진 탐색 트리가 이렇게 된다. 노드의 개수가 n일 때, 트리의 높이도 n이다. 이런 식으로 트리 안에서 노드가 직선적인 모양으로 저장됐을 때 트리가 한쪽으로 편향됐다 또는 치우쳤다 라고 표현한다.

반대로, 이진 탐색 트리가 이러한 형태로 저장되어 있다면:

root 노드를 기준으로 트리의 왼쪽과 오른쪽이 균형을 이루고 있다. 이런 균형잡힌 모양이 될수록 이진 탐색 트리의 높이는 작아지게 된다. 그러므로 그 높이가 log(n)에 가까울 수록 트리가 균형이 잡혔다 라고 한다.

이진 탐색 트리 연산들의 시간은 모두 그 높이 h에 비례한다. 그러면 결론적으로

• 편향된 트리일수록 연산들이 비효율적으로,
• 균형이 잡힌 트리일수록 연산들이 효율적으로

이루어진다고 볼 수 있다.

이진 탐색 트리 평균 높이

최악의 경우 이진 탐색 트리의 높이는 n이 되지만, 항상 최악의 경우가 일어나는 건 아니다. 이진 탐색 트리의 높이가 평균적으로는 어떻게 되는지 생각해보자.

총 n개의 데이터를 이진 탐색 트리에 삽입하면, 삽입을 할 때 그 순서의 경우의 수는 n!이다. 1 ~ 6의 정수 데이터를 삽입하는 경우 총 경우의 수는 6 * 5 * 4 * 3 * 2 * 1이다. 수학적으로 모든 순서의 확률이 동일하다고 가정하고 이 경우들의 평균 높이를 계산하면 O(log(n))이 된다.

즉, 평균적으로 이진 탐색 트리의 높이 h는 O(log(n))이라고 할 수 있긴 하지만, 이진 탐색 트리에 삽입 연산과 삭제 연산들을 반복적으로 계속 하면 높이가 O(log(n))일 것이라는 보장을 할 수 없다. 실제로 생각보다 균형을 잃기가 쉽다.

정리하자면, 이진 탐색 트리에 n개의 데이터들이 임의의 순서대로 삽입되었다고 가정을 하면 트리의 높이 h는 평균적으로 O(log(n))으로 표현할 수 있다. 이를 이진 탐색 트리의 삽입, 탐색, 삭제 연산에 적용해보면 세 연산의 시간 복잡도는 모두 평균적으로는 O(log(n))인 것이다.

이진 탐색 트리 연산	시간 복잡도
삽입	O(h) (평균 O(log(n), 최악 O(n)))
탐색	O(h) (평균 O(log(n), 최악 O(n)))
삭제	O(h) (평균 O(log(n), 최악 O(n)))

하지만 삽입과 삭제 연산들을 반복하다보면 이진 탐색 트리의 노드들이 한쪽으로 편향될 수 있기 때문에 이진 탐색 트리의 연산들의 시간 복잡도는 보통 높이 그대로 O(h)로 표기한다.

이진 탐색 트리로 딕셔너리 구현하기

이진 탐색 트리를 구현하면 추상 자료형 딕셔너리를 구현할 수 있다고 했다. 딕셔너리(또는 맵)는 key-value 데이터 쌍을 찾고, 저장하고, 지울 수 있게 해주는 추상 자료형이다. 이진 탐색 트리를 사용해서 어떻게 딕셔너리를 구현할 수 있는지 알아보자.

이진 탐색 트리 노드

이진 탐색 트리 노드 클래스

class Node:
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.left_child = None
        self.right_child = None

여기서 조금만 바꿔주면 된다.

딕셔너리용 이진 탐색 트리 노드

class Node:
    def __init__(self, data):
        self.key = key
        self.value = value
        self.parent = None
        self.left_child = None
        self.right_child = None

이렇게 이진 탐색 트리 노드를 새롭게 정의해주면 된다. 전에는 노드의 데이터, 변수 data를 이용해서 원하는 노드를 삽입, 삭제, 탐색했었는데, 이렇게 노드를 새롭게 정의하면 노드를 data가 아닌 변수 key를 사용해서 찾고 저장하고 지운다.

즉 특정 key가 주어졌을 때, 이 key에 해당하는 노드를 찾고, 저장하고 지울 수 있는 것이다. 크게 바뀌는 건 없고, 이진 탐색 트리 클래스의 연산들도 이 새로운 노드 클래스의 내용에 맞게 수정해주기만 하면 된다.

 

이렇게 하면 이제 이진 탐색 트리 노드에 key-value 데이터 쌍을 자연스럽게 저장할 수 있는 것이다.

어차피 연산들 자체는 data 변수 대신 key를 사용하는 것으로 바뀌었을 뿐이다. 노드에 data 대신 key-value 두 변수를 저장한다고 시간 복잡도가 바뀌는 건 없다.

이진 탐색 트리 연산	시간 복잡도
key를 이용한 key-value 데이터 쌍 삭제	O(h)(평균 시간 복잡도 O(log(n)))
key를 이용한 노드 또는 value 탐색	O(h)(평균 시간 복잡도 O(log(n)))
key-value 쌍 삽입	O(h)(평균 시간 복잡도 O(log(n)))

세 가지 연산을 모두 O(h)로 할 수 있다.

이진 탐색 트리 평가

이진 탐색 트리가 다른 자료 구조들에 비해서 실제로 얼마나 효율적인지 살펴보자.

이진 탐색 트리를 사용하는 가장 대표적인 예시는 추상 자료형, 세트(set)와 딕셔너리(dictionary)를 구현하는 것인데, 해시 테이블을 사용해도 두 추상 자료형을 구현할 수 있었다.

	이진 탐색 트리	해시 테이블
삽입	O(h)(평균 O(log(n)), 최악 O(n))	평균 O(1), 최악 O(n)
탐색	O(h)(평균 O(log(n)), 최악 O(n))	평균 O(1), 최악 O(n)
삭제	O(h)(평균 O(log(n)), 최악 O(n))	평균 O(1), 최악 O(n)

삽입, 탐색, 삭제 세 연산 모두 이진 탐색 트리보다 해시 테이블을 사용하는 게 더 효율적이다.

그럼 이진 탐색 트리는 언제 사용할까? 이진 탐색 트리에서만 사용할 수 있는 게 뭔지 생각해보자.

 

이진 탐색 트리는 데이터 사이에 순서를 저장해주는 자료 구조이다. in-order 순회를 단순히 트리 안에 있는 데이터를 출력하는 용도로 사용했었는데, 이런 출력 용도가 아니더라도 모든 데이터를 정렬된 상태로 갖고 오거나, 정렬된 상태로 뭔가 하고 싶을 때도 in-order 순회를 통해 모든 데이터를 빠르게 정렬해서 갖고 올 수 있다.

 

반면 해시 테이블은 데이터 사이에 순서 관계를 저장할 수 없는 자료 구조이다. 데이터를 정렬하고 싶으면 순서를 저장하는 다른 자료 구조에 똑같은 데이터를 저장한 뒤에 정렬시켜야 한다.

 

세트와 딕셔너리는 데이터 사이에 순서 관계를 약속하지 않는 추상 자료형이긴 하다. 하지만 이 두 가지를 사용하면서도 데이터 사이의 순서 관계를 저장해야하는 경우들이 생길 수 있다. 이런 경우에는 해시 테이블을 사용하기가 힘들다. 이럴 때 바로 이진 탐색 트리를 사용해야 한다.

 

정리하면 추상 자료형, 세트나 딕셔너리를 코드로 구현할 때 일반적인 경우에는 해시 테이블을 사용하는 게 이진 탐색 트리를 사용하는 것보다 더 효율적이다. 하지만 세트의 데이터나 딕셔너리의 key를 정렬된 상태로 사용하고 싶을 때는 이진 탐색 트리를 사용해야 한다. 물론 이때 해시 테이블보다는 연산의 효율성은 조금 포기해야한다.

출처: 코드잇