이진검색트리(Binary Search Tree)

이진검색트리(Binary Search Tree)

-Dynamic set을 트리의 형태로 구현

정의

-이진트리이면서 각 노드에 하나의 키를 저장

- 각 노드 v에 대해서 그 노드의 왼쪽 부트리(subtree)에 있는 키들은 key[v]보다 작거나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.

**Binary Search Tree하고 heap은 다르다.

최소값 찾기

: 왼쪽 자식이 없어야 하고 어떤 노드의 오른쪽 서브트리이면 안된다.

TREE-MINIMUM(x)

while left[x]≠NIL

do x <- left[x]

return x

(최소값은 항상 가장 왼쪽 노드에 존재)

최대값 찾기

TREE-MAXIMUM(x)

while right[x]≠NIL

do x <- right[x]

return x

(최대값은 항상 가장 오른쪽 노드에 존재)

Successor

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

(모든 키들이 서로 다르다고 가정)

3가지 경우

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

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

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

3.  그런 노드 y가 존재하지 않을 경우 successor가 존재하지 않음

(즉, x가 최대값)

TREE-SUCCESSOR(x)

if right[x] ≠ NIL

then return TREE-MINIMUM(right[x])

y<-p[x]

while y ≠ NIL and x = right[y]

do x<-y

y<-p[y]

return y

predecessor

: 노드 x의 predecessor란 key[x]보다 작으면서 가장 큰 키를 가진 노드 ( successor와 반대)

INSERT

TREE-INSERT(T,z)   //T : tree  , z:insert할 노드

y<-NIL

x<-root[T]

while x ≠ NIL

do y <- x

if key[z] < key[x]

then x<-left[x]

else x<-right[x]

p[z] <- y

if y = NIL

then root[T] <- z

else if key[z] < key[y]

then left[y] <- z

else right[y] <- z

DELETE

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

-> 그냥 삭제

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

->자신의 자식노드를 원래 자신의 위치로

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

노드는 그대로 두고 노드의 data만 지운다.

제거하는 값의 가장 근접한 값, 즉 predecessor/successor를 가져온다.

원래 있던 값보다 큰값이 왔으므로 왼쪽 서브트리와 오른쪽 서브트리 관계없다.

그 다음은 case1이나 case2를 이용

TREE-DELETE(T,z)  //z는 삭제할노드

if left[z] = NIL or right[z] = NIL

then y<-z

else y<- TREE-SUCCESSOR(z)   //y는 실제로 삭제할 노드

if left[y] ≠ NIL

then x <- left[y]   

else x <- right[y]

if x ≠ NIL

then p[x] <- p[y]

if p[y] = NIL

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]

copy y's satellite data into z

return y