이진검색트리2

어떤 노드가 최소값이 되려면  :  왼쪽 자식이 없어야하고 누군가의 오른쪽 서브트리에 속해서는 안된다.

---

Successor

key[x] 보다 크면서 가장 작은 키를 가진 노드 

successor의 3가지 경우

- 노드 x의 오른쪽 부트리가 존재할 경우, 오른쪽 부트리의 최솟값. 

 (15의 successor 17 / 6의 successor는 7)  경우가 이경우 ,,

 

- 오른쪽 부트리가 없는 경우, 어떤 노드 y의 왼쪽 부트리의 최대값이 x가 되는 그런 노드 y가 x의 successor 

   - 부모를 따라 루트까지 올라가면서 처음으로 누군가의 왼쪽 자식이 되는 노드 

 

- 그런 노드 y가 존재하지 않을경우 successor 

  (위 그래프에서 20)

TREE-SUCCESSOR(x)
  if right[x] != NULL  
    then return TREE-MINIMUM(right[x])
  y <- p[x]
while y != NULL and x = right[y]  
   do x <- y
   y <- p[y]
  return y  

 

Predecessor

key[x]보다 작으면서 가장 큰 키를 가진 노드

Successor와 반대

 

---

INSERT

기존의 노드들의 위치나 구조는 전혀 변경하지않는다.

마치 검색을 할때처럼 따라나와서 13의 오른쪽 자식에 14를 추가하는 식,,

인서트를 할때 기존의 노드는 변함이없고 새로운 노드가 추가된다.

그래서 delete하지않는다면 맨처음 insert한 노드가 root를 차지하게된다.

 

TREE-INSERT(T, z)      //T (binary search tree ) Z (insert할 노드)
  y <- NULL            
  x <- root[T]         
  while x!= NULL           //x가 null 이 될때까지
    do y <- x               //y에 x를 저장
      if key[z] < key[x]    //z와 x의 키값을 비교해서 z의 키값이 x의 키값보다 작으면 왼쪽노드,,
        then x <- left[x]    //z의 키값이 더 크면 오른쪽 노드
          else x <- right[x]
  p[z] <- y                  //y가 null 이라면 tree가 null이라는 의미고 z는 root
  if y = NULL
    then root[T] <- z         //z의 키 값이 y보다 작다면 왼쪽자식
  else if key[z] < key[y]      
    then left[y] <- z           //z의 키값이 y보다 크다면 오른쪽 자식
  else
   then right[y] <- z



시간복잡도 : 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/4094?tab=note