[3. 검색트리] 이진트리 검색 (2)

0. Dynamic Set

Dynamic Set은 여러 개의 키(key)를 저장하며 Insert(새로운 키 삽입), Search(키 탑색), Delete(키 삭제)와 같은 연산들을 지원하는 자료구조이다.

문제는 정렬되거나 정렬되지 않는 배열, 또는 연결 리스트를 사용할 때 insert, search, delete 중 적어도 하나는 $O(n)$의 시간복잡도를 피할 수 없게 된다. 때문에 이를 해결하고자 여러 방법들이 연구되었는데 그 해결방법들은 다음과 같다.

• 검색트리: 이진탐색트리(Binary Search Tree), 레드-블랙 트리, AVL-트리 등에 기반
• 해슁: 해쉬 테이블, Direct Address Table 등

 

1. 검색트리

Dynamic Set을 트리의 형태로 추상적으로 구현한 자료구조이다. 일반적으로 search, insert, delete 연산이 트리의 높이($O(logN)$)에 비례하는 시간복잡도를 가진다.

 

(1) 이진검색트리(Binary Search Tree, BST)

이진검색트리는 다음과 같은 특성을 만족한다.

• 이진 트리이면서
• 각 노드에 하나의 키를 저장
• 각 노드 v에 대해 왼쪽 부트리(subtree)에 있는 키들은 key[v]보다 작거나 같고, 오른쪽 부트리에 있는 값은 key[v]보다 크거나 같다

이진검색트리 예시

 

#binary search pseudo code

# 1) recursive
def tree_search(x, k):
	# x: 루트 노드
    # k: 찾는 값
    if x == Null or k = key[x]:
    	return x
    if k < key[x]:
    	return tree_search(left[x], k)
    else:
    	return tree_search(right[x], k)
        
        
        
# 2) iterative
def iterative_tree_search(x, k)
	while x != Null o k != key[x]:
    	if k < key[x]:
        	x = left[x]
        elsee:
        	x = right[x]
    
    return x

트리의 높이만큼 탐색하므로 시간 복잡도는 $O(logN)$이다(최악의 경우에는 $O(N)$).

 

 

(2) 이진검색트리의 Search

BST는 각 노드의 보다 큰 값이 오른쪽에, 작은 값이 왼쪽에 위치해 있으므로 seach하는 과정은 루트노드 부터 출발하여 찾고자 하는 값이 노드의 값보다 큰지 작은지만 확인하면 된다.

 

이진검색트리에서의 search

 

이진트리에서의 최대값, 최소값

이진트리에서는 최대값은 루트에서 오른쪽 노드만 쭉 따라가다가 나오는 leaf 노드의 값이며, 최소값은 왼쪽으로만 내려가다가 나오는 leaf 노드의 값이다.

 

Successor & Predecessor

Succesor: 어떤 노드 값의 바로 다음 값으로, 노드 $x$의 successor란 $key[x]$보다 크면서 가장 작은 키를 가진 노드이다.(모든 키들이 서로 다르다고 가정)

다음과 같이 3가지 경우가 존재한다.

• 노드 $x$의 오른쪽 부트리가 존재할 경우, 오른쪽 부트리의 최소값
• 오른쪽 부트리가 없는 경우, 어떤 노드 $y$의 왼쪽 부트리의 최대값이 $x$가 될 때 $y$가 $x$의 successor가 됨(부모를 따라 루트까지 올라가다가 처음으로 누군가의 왼쪽 자식이 되는 해당 노드의 값)
• 이러한 노드 $y$가 존재하지 않을 경우 successor가 존재하지 않음(즉, x가 최대값)

#tree successor pseudo code

def tree_seccessor(x)
	if right[x] != Null:
    	return tree_minimum(right[x])
    
    y = parent[x]
    while y != Null and x = right[y]: 
    	# y,x가 부모자식 관계가 되도록 유지하면서 계속 오른쪽 링크를 따라 올라감
    	x = y
        y = parent[y]
        
    # x가 처음으로 y의 왼쪽자식이 되는 경우, y가 x의 successor이며 loop를 빠져나오게 됨    
    # x가 root가 되는 경우 y는 Null임. 즉 successor가 존재하지 않는 경우
    return y

시간 복잡도는 $O(logN)$이다.

 

Predecessor : 노드 $x$의 predecessor란 $key[x]$보다 작으면서 가장 큰 키를 가진 노드로, 어떤 노드 값의 바로 이전 값을 의미한다. Successor와 반대로 생각하면 된다.

 

 

 

(3) 이진검색트리의 Insert

BST에서 insert를 할 때는 원래 트리의 구조는 바뀌지 않으며, insert 하고자 하는 값을 알맞은 leaf 노드 자리에 추가해주기만 하면된다.

 

이진검색트리에서의 Insert

2개의 포인터 $x,y$를 사용하며 계속 노드를 탐색하며 $x$가 $y$의 자식 노드가 되도록 유지하며 알맞은 leaf 노드 위치를 찾아나가게 된다. 이진검색트리 $T$가 구성되어 있다고 가정할 때 insert를 해보자

#tree insert pseudo code

def tree_insert(T,z):
	y = Null
    x = root[T]
    while x != Null:
    	y = x
        if key[z] < key[x]:
        	x = left[x]
        else:
        	x = right[x]
    
    # while문이 끝나면 x: Null, y:x의 parent인 상황임
    parent[z] = y
    if y = Null:  
    	root[T] = z  # tree가 empty인 경우 z를 추가
    else:
    	if key[z] < key[y]:
    		left[y] = z
    	else:
    		right[y] = z

시간 복잡도는 $O(logN)$이다.

 

 

(4) 이진검색트리의 Delete

BST에서는 delete 연산이 제일 복잡하다.

 

i. Case 1: 자식노드가 없는 경우

삭제할 노드를 트리에서 바로 삭제하면 된다.

 

 

 

ii. Case 2: 자식노드가 1개인 경우

삭제하고자 하는 노드가 부모의 오른쪽 자식이었다면, 내 자식노드를 내 부모노드와 연결시키면 된다. 

 

 

iii. Case 3: 자식노드가 2개인 경우

제일 복잡한 경우이다. 아래와 같은 이진검색트리에서 13을 삭제한다고 해보자.

 

 

우선 13의 노드는 두고 데이터, 또는 데이터 주소를 삭제한다.  그럼 어떤 값을 가져오는게 제일 좋을까? 가장 근접한 값인 successor나 predecessor를 찾으면 된다.

13을 삭제하고 successor인 15를 가져오면 bst의 크기관계 조건이 훼손되지 않는 장점이 있다. 또한 successor라는 것은 왼쪽자식을 가지지 않는 것이 보장되어 있으므로 자식노드가 0개 또는 1개이다. 즉 case1,2에 해당하므로 노드 삭제가 간편하다.

 

 

삭제할 노드를 찾은 상황 이후에 Delete은 다음과 같이 수행한다.

#tree delete pseudo code

def tree_delete(T,z):
	# z: 삭제할 노드(입력값)
    # y: 실제로 tree에서 삭제될 노드
    
    if left[z] == Null or right[z] == Null:  # case 0,1
    	y = z
    else
    	y = tree_successor(z)
        
    ### y는 실제로 삭제되는 노드이며
    ### case 1,2,3 모두 자식이 0개이거나 1개이다.
    
    ### case 1,2의 경우 y == z이며
    ### case 3의 경우 y != z 이다. (successor가 삭제되기 때문)
    
    # 노드 y 삭제하는 부분
    if left[y] == Null:
    	x = right[y]
    else:
    	x = left[y]
    
    if x != Null:
    	# y를 삭제하고 x를 y자리로 이동
        parent[x] = parent[y]
    
    if parent[y] == Null:  
    	# y가 root 노드인 경우
    	root[T] = y
    else:
    	if y == left[parent[y]]:
        	# y가 부모의 왼쪽 자식인 경우
            left[parent[y]] = x
        else:
        	right[parent[y]] = x
    
    # case 3 경우
    if y != z:
    	key[z] = key[y]
        copy y's satellite data into z
    
    return y

 

 

*정리

이진검색트리에서 각종 연산의 시간 복잡도는 $O(logN)$이며 최악의 경우는 $O(N)$이다.

키의 삽입이나 삭제시 트리의 균형을 잡아줌으로써 균형잡힌(balanced) 트리를 만들고 높이를 $O(logN)$으로 유지하면 이를 개선할 수 있다.(e.g. 레드-블랙 트리)

 

 

 

 

 

[References]

• 권오흠 교수, 알고리즘(강의 링크)