[알고리즘] 탐색 알고리즘 - 탐색 트리 2

https://souffledata.tistory.com/46

[알고리즘] 탐색 알고리즘 - 탐색 트리 1

앞에서 이진 탐색 트리는 삽입, 삭제가 일어남에 따라 트리의 형태가 달라질 수 있다고 언급하였다.

이번 글에서는 이를 해결하면서 이진 탐색 트리의 장점을 유지할 수 있는 트리인 균형 탐색 트리에 대해 소개해본다.

 

1. 흑적 트리

 

흑적 트리는 이진 탐색 트리로 다음의 성질을 만족하는 균형 탐색 트리이다.

• (성질1) 모든 노드는 흑색이거나 적색이다.
• (성질2) 루트 노드와 리프 노드는 흑색이다. 단, 모든 리프 노드는 Null 노드이다.
• (성질3) 적색 노드의 부모 노드는 항상 흑색이다.
• (성질4) 임의의 노드로부터 리프 노드까지의 경로상에는 동일한 개수의 흑색 노드가 존재한다.

흑적 트리는 우선 (성질2)와 (성질3)에 의해 흑색 노드가 적색 노드보다 항상 많게 된다. 또한, (성질4)에 대해 루트 노드부터 리프 노드까지 경로 상에 동일한 개수의 흑색 노드가 존재하게 되어, 모든 리프 노드의 깊이는 두 배 이상 차이날 수가 없다. 이러한 성질 때문에 흑적 트리는 균형 탐색 트리가 되게 된다.

아래의 그림은 흑적 트리의 예라 할 수 있다.

① 탐색

흑적 트리에서의 탐색은 이진 탐색 트리와 동일하다.

 

② 삽입

흑적 트리의 삽입도 이진 탐색 트리와 유사하게 삽입할 원소를 이용하여 탐색하다가 비교할 노드가 Null 노드이면, 그 노드에 원소를 추가하고 적색으로 바꾼 뒤, 두 개의 자식 노드를 Null 노드로 만든다. 하지만 적색 노드의 부모 노드는 적색이 될 수 없기 때문에, 노드의 구조나 색깔을 바꾸게 된다. 다음과 같이 3가지 경우가 나타날 수 있다.

• 부모 노드의 형제 노드가 적색인 경우 : 부모 노드, 부모 노드의 형제 노드, 부모 노드의 부모 노드의 색깔까지 모두 변경한다.
• 부모 노드의 형제 노드가 흑색, 현재 노드의 키 값이 부모 노드와 부모 노드의 부모 노드의 키 값 사이인 경우 : 현재 노드와 부모 노드를 회전 시킨다.
• 부모 노드의 형제 노드가 흑색, 현재 노드의 키 값보다 부모 노드와 부모 노드의 부모 노드의 키값이 큰 경우(혹은 작은 경우) : 부모 노드와 부모 노드의 부모 노드를 회전시키고 색깔을 변경한다.

정확한 이해를 위해 예시를 들어보겠다.

왼쪽 흑적 트리에 새로운 원소 x = 50을 넣어본다고 해보자.

x = 50을 삽입할 곳을 찾기 위해 탐색을 진행하게 되면, 30보다 크기 때문에 오른쪽으로, 60보다 작기 때문에 왼쪽으로, 40보다 크기 때문에 오른쪽에 도달하여, 40의 우측 자식 노드 Null에 도달하게 된다.

해당 위치에 적색 노드 50을 넣고 나서 위의 규칙에 맞춰본다.

 

 

노드 50과 그 부모 노드 40 모두 적색이므로, 색을 변경해야하는데, 부모 노드의 형제 노드가 모두 적색임을 알 수 있다. 이 경우, 부모 노드, 부모 노드의 형제 노드, 부모 노드의 부모 노드의 색깔까지 변경해야 한다. 따라서 40, 70은 흑색 노드로 / 그 부모 노드인 60은 적색 노드로 변경한다.

 

그럼 지금 만들어진 흑적 트리에 x = 45를 추가한다고 해보자.

그림에서 볼 수 있듯이 이번에도 노드 45와 그 부모 노드 50이 모두 적색이므로 색을 변경해야 한다. 하지만 이번에는 50의 형제 노드가 Null로 흑색 노드임을 알 수 있다. 또한 이번에 추가한 노드 45는 부모 노드와 부모 노드의 부모 노드 값 사이에 위치한다. 이 경우(2번째 규칙) 현재 노드와 부모 노드를 회전시킨다. 즉, 오른쪽 흑적 트리의 빨간색 화살표처럼 회전시킨다는 것이다.

이번엔 50이 가장 아래로 내려가면서 45의 형제 노드가 Null로 흑색 노드이면서, 가장 아래에 있는 50이 부모 노드와 부모 노드의 부모 노드보다 크다는 것을 알 수 있다. 이 경우 (3번째 규칙) 부모 노드와 부모 노드의 부모 노드를 회전시키고 색을 변경하게 된다. 즉, 오른쪽 흑적 트리와 같이 완성되는 것을 알 수 있다.

 

(1) 알고리즘

흑적 트리에서의 노드 구조는 위와 같다. 이를 가지고 알고리즘을 구성하면 다음과 같다.

 

① 탐색 알고리즘

def RB_Search(T,x): # T : 흑적 트리, x : 탐색 값
    CNode = T의 루트 노드
    while CNode != False:
        if x == CNode.key :
            return CNode
        elif x < CNode.key :
            CNode = CNode.Left #왼쪽 서브트리 탐색
        else :
            CNode = CNosde.Right #오른쪽 서브트리 탐색
    return False # 탐색키가 존재하지 않는 경우

② 삽입 알고리즘

def RB_Insert(T,x):
    PNode = CNode = T의 루트 노드
    while CNode != False:
        if x == CNode.key:
            return T # 삽입할 원소가 이미 존재
        else:
            PNode = CNode
            if x < CNode.key :
                CNode = CNode.Left # 왼쪽 서브트리 탐색
            else :
                CNode = CNode.Right
    # 새 노드 생성. Left와 Right는 Null
    NewNode.key = x
    NewNode.color = RED
    if x < PNode.key :
        PNode.Left = NewNode # 왼쪽 자식으로 새 노드 추가
    else :
        PNode.Right = NewNode
    CNode = NewNode
    PNode = CNode.parent
    #현재 노드와 부모 노드가 둘 다 적색이라면
    while (CNode.color == RED and PNode.color == RED) :
        if PNode.sibling.color == RED : # 첫번째 규칙
            PNode.color = BLACK
            PNode.sibling.color = BLACK
            PNode.parent.color = RED
            CNode = PNode.parent
            PNode = CNode.parent
        else : # 두번째 규칙
            if (CNode.key < PNode.key and CNode.key > PNode.parent.key): 
                CNode = PNode
                PNode = CNode.parent #CNode를 PNode 위치로 올리고, PNode를 CNode의 오른쪽 자식으로 내림
            elif (CNode.key > PNode.key and CNode.key < PNode.parent.key):
                CNode = PNode
                PNode = CNode.parent #CNode를 PNode 위치로 올리고, PNode를 CNode의 왼쪽 자식으로 내림
            PNode.color = BLACK
            PNode.parent.color = RED #규칙3
            PNode와 PNode.parent 회전시킴
    return T

 

(2) 성능 분석

 

흑적 트리는 균형 탐색 트리이므로, 모든 리프 노드의 깊이가 2배 이상 차이나지 않는다. 따라서 최악의 경우에도 트리의 높이는 logn이기 때문에 탐색 알고리즘은 O(logn)이라는 시간 복잡도를 갖는다.

삽입의 경우 역시 O(logn)이라는 시간 복잡도를 갖게 되며, 여기서 다루지 않은 삭제 알고리즘도 O(logn)의 시간복잡도를 갖는다.