이진검색트리3

DELETE 연산

-삭제할 노드를 찾음(key를 가진 노드)

-사전 작업으로 search

 

1.DELETE할 노드가 자식이 없는 경우

2.DELETE할 노드가 자식이 한명인 경우

3.DELETE할 노드가 자식이 두명인 경우

 

세가지 케이스를 나누어 각각 처리하는 알고리즘

 

1.DELETE할 노드가 자식이 없는 경우 (위그림에서 숫자 4의 경우) : 그냥 삭제 

 

2.DELETE할 노드가 자식이 한명인 경우 ( 위그림에서 숫자 7의 경우)  : 자신의 자식노드를 원래 자신의 위치로

부모도,자식도 유일하므로 바로 부모-자식으로 연결해줌 

 

3.DELETE할 노드가 자식이 두명인 경우 (위 그림에서 13을 삭제하는 경우)

-노드 13을 트리로 부터 제거하면 상황이 복잡해짐,, 6과 18이 부모노드가 없어지기때문,,

그래서 노드 13을 두고 노드 13에 저장된 데이터만 삭제 다른 노드 데이터를 가져온다.

 

-13이 제거되는 대신 13에 가장 가까운 값을 가져오는게 유리하다.

(13보다 작으면서 가장 큰값, 13보다 크면서 가장 작은값)

 

1.successor의 값을 삭제하려는 노드로 copy한다.

2.successor 노드를 대신 삭제한다.

TREE-DELETE(T, z)

 if left[z] = NULL or right[z] = null //자식 노드가 0이거나 1인경우
  then y <- z
 else y <- TREE-SUCCESSOR(z) //왼쪽,오른쪽 자식노드 null이아니고 (y: 실제로 삭제할 노드)
 if left[y] != NULL   //노드 y를 삭제하는 코드 6~14 
 then x <- left[y]
 else x <- right[y]
 if x != NULL
 then p[x] <- p[y]  // x의 부모자리 < - y의 부모
 if p[y] = NULL    //즉 y가 루트노드 
 then root[T] <- x    
 else if y = left[p[y]]
 then left[p[y]] <- x
 else right[p[y]] <- x   
 if y != z
 then key[z] <- key[y]    // 노드 y에 저장된  데이터를 z로 카피
 copy y's satellite data into z
  return y

 

이진 검색 트리 (insert, search, delete)

-각종 연산의 시간 복잡도 o(h)

-최악의 경우 트리 높이 h=o(h)

-균형 잡힌 트리

  -레드-블랙 트리

  - 키의 삽입이나 삭제시 추가로 트리의 균형을 잡아줌으로 높이를 O(log2n)으로 유지

 

 

참고 영상

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=note