11-3강. 이진검색트리 (Binary Search Tree)

지난 강의 공부 내용...

• 이진검색트리의 탐색, 삽입

 

 

• 이진검색트리/이진탐색트리의 삭제

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

   -> 해당 노드를 그냥 삭제한다.

 

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

   -> 자신의 자식노드를 원래 자신의 위치로 보낸다.

 

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

   -> 해당 노드의 자리는 그대로 두고, 데이터만 삭제한다. 그리고 해당 노드와 가자아 가까운 값인 다른 노드를 해당 자리로 가져 온다.

   그 다른 노드는 삭제하려는 노드의 successor이다. 삭제하려는 노드의 successor는 최대 1개의 자식노드를 가진다.

 

이진검색트리 삭제의 예. (a) Case1, (b) Case2, (c) Case3

 

TREE-DELETE(T, z)	// z : 삭제할 노드
{
if left[z] == null or right[z] == null
    	then y <- z
    	else y <- TREE-SUCCESSOR(z)
        
// 노드 y를 삭제하는 것으로 생각한다.
    if left[y] != null
    	then x <- left[y]
        else x <- right[y]
    if x != null
    	then p[x] <- p[y]
    if p[y] == null
    	then root[T] <- x
        else if y == left[p[y]]
        		then left[p[y]]	<- x
                else right[p[y]] <- x
                
// 그런데 y가 z가 아니라면, (Case3)
	if y != z
    	then key[z] <- key[y]
        	copy y's satellite data into z
    return y
}

시간복잡도 : O(h)

 

 

 

• Binary Search Tree

Search, Insert, Delete의 시간복잡도는 모두 O(h)이다.

레드-블랙 트리는 이진검색트리의 한 형태이다.

 

(강의 참고 : www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4095?tab=curriculum)