알고리즘 이론 12강. 이진 검색 트리

 

[이진 검색 트리의 개념]

: 각 노드를 객체로 하는 연결 데이터 구조

 

# 노드의 구성

노드 구성도

- key 값 영역

- 부속 데이터

- Left : 왼쪽 자식노드 포인터 (자식노드 없으면 NIL)

- Right : 오른쪽 자식노드 포인터 (자식노드 없으면 NIL)

- Parent : 부모노드 포인터 (노드가 root면 NIL)

 

 

 

[이진 검색 트리 특성]

x가 이진 검색트리의 한 노드이고, y가 x의 왼쪽 서브트리의 한 노드일때, y.key <= x.key 를 만족한다. ( 오른쪽일때는 y.key >= x.key 만족 )

 

 

 

[이진 검색 트리의 연산]

- 종류 : SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE

- 연산 평균 시간 복잡도 : Θ(logn)

- 최악 시간 복잡도 : Θ(n) : 노드들이 선형일때(한쪽으로만 쏠려을때)

 

 

 

[이진 검색 트리 순회 방식]

1. 중위 트리 순회 : left, root, right

2. 전위 트리 순회 : root, left, right

3. 후위 트리 순회 : left, right, root

 

# 중위 트리 순회 의사코드

INORDER-TREE-WALK(x)    if x != NIL     INORDER-TREE-WALK(x.left)     print x.key     INORDER-TREE-WALK(x.right)

: 내부의 3문장의 순서의 위치를 바꿈으로써 전위, 중위, 후위 방식으로 변경할 수 있다.

 

---

 

[이진 검색 트리 검색]

# 재귀 방식의 검색 의사코드

TREE_SEARCH(x, k)   if x == NIL or k == x.key     return x   if k < x.key     return TREE-SEARCH(x.left, k)   else     return TREE-SEARCH(x.right, k)

: 검색한 key값 나올때까지 key값 기준 오른쪽 or 왼쪽으로 내려가 재귀적으로 검색.

 

# 순환 방식의 검색 의사코드

ITERATIVE-TREE-SEARCH(x, k)   while x != NIL and k != x.key     if k < x.key       x = x.left     else       x = x.right     return x

 

 

 

[최소 최대 원소 찾기]

: 이진 검색트리에서 최소값, 최대값을 찾는 방식 (O(logn))

 

# 최소 원소 찾기

TREE-MINIMUM(x)   while left[x] != NIL     do x <- left[x]   return x

: 이진 검색 트리 특성상, 최소값은 트리의 왼쪽 최하단에 위치해 있다.

 

# 최대 원소 찾기

TREE-MAXIMUM(x)   while x.right != NIL     x = x.right   return x

: 이진 검색 트리 특성상, 최대값은 트리의 오른쪽 최한단에 위치해 있다.

 

 

 

[직후원소(Successor) 찾기]

: 이진 검색 트리내에서 크기 기준 다음 노드를 찾는다. (2가지 상황으로 나뉜다)

case1. 원소 x의 오른쪽 자식 노드가 있을때

  : 원소 x보다 다음으로 큰 노드는 오른쪽 자식 트리중 가장 왼쪽에 있는 원소 이다.

case2. 원소 x의 오른쪽 자식 노드가 없을때

  : 현재 노드가 왼쪽 자식 노드일때까지 트리를 올라간다. 그때의 부모노드가 다음으로 큰 노드이다.

  : 만약 해당되는 경우가 없으면, 현재 원소 x가 트리내의 최대값 원소이다.

 

# 직후원소 검색 의사 코드

TREE-SUCCESSOR(x)   if x.right != NIL                                        # case 1     then return TREE-MINIMUM(x.right)   y = x.p                                                   # case 2 (x.p = x.parent)   while y != NIL and x == y.right     x = y     y = y.p   return y

 

 

 

[직전원소(Predecessor) 찾기]

: 직후원소 찾는 방식과 유사

- case1. 원소 x의 왼쪽 자식 노드가 있을때

  : 원소 x보다 다음으로 큰 노드는 왼쪽 자식 트리중 가장 오른쪽에 있는 원소 이다.

- case2. 원소 x의 오른쪽 자식 노드가 없을때

  : 현재 노드가 오른쪽 자식 노드일때까지 트리를 올라간다. 그때의 부모노드가 다음으로 큰 노드이다.

  : 만약 해당되는 경우가 없으면, 현재 원소 x가 트리내의 최소값 원소이다.

# 직전원소 의사코드 생략

 

---

 

[삽입(Insertion)]

: 값 v를 이진 검색 트리의 알맞은 위치에 삽입 (비교적 간단)

: 값 v에 해당되는 자식 NIL 위치에 삽입하면 된다.

 

# 이진트리 삽입 의사코드

TREE-INSERT(T, z)         # 이진트리 T에 값 z 삽입   y = NIL                    # y는 현재 노드, x는 다음 비교 노드   x = T.root     while x != NIL           # 알맞은 잎 노드위치로 이동     y = x     if z.key < x.key       x = x.left     else x = x.right   z.p = y                       # y가 알맞은 잎노드인 상황 (x은 NIL), 주어진 노드 z의 parent에 y 저장 if y == NIL                  # 트리 T가 빈 트리일때   T.root = z   elseif z.key < y.key        # 마지막으로 주어진 z와 y값 비교해 잎노드의 왼쪽 or 오른쪽 자식에 z 노드 삽입   y.left = z else y.right = z

 

 

 

[삭제(Deletion)] **

: 주어진 노드 값 z를 이진 검색 트리에서 삭제

- case1. 원소 z가 자식 노드가 없을때

  : 노드 z의 부모 노드의 z 포인터를 NIL 변경해주기만 하면 된다

- case2. 원소 z가 한개의 자식 노드를 가지고 있을때

  : 노드 z의 부모 노드의 z 포인터를 z 노드의 자식 노드로 변경해주기만 하면 된다

- case3. 원소 z가 두개의 자식 노드를 가지고 있을때

  : 노드 z의 직후원소(Succesor) y를 찾고, y가 z의 자리를 차지하도록 한다.

  (이때 노드 y도 이 삭제작업  case1, 2일어날때까지 재귀적으로 수행해야한다.

 

# 이진 검색 트리 삭제 의사 코드 1

TREE-DELETE(T, z)   if z.left == NIL or z.right == NIL            #case 1, 2일때, y는 z     then y <- z     else y <- TREE-SUCCESOR(z)               # case 3일때, y = z의 직후원소     if y.left != NIL                                         then x <- y.left     else x <- y.right     if x != NIL     then x.p <- p.y     if y.p = NIL     then T.root <- x     else if y = y.p.left       then y.p.left <- x       else y.p.right <- x     if y != z     then x.key <- y.key       y의 부가 data를 z에 복사   return y

 

# 이진 트리의 삭제 의사 코드 2(둘중에 하나만..)

TRANSPLANT(T, u, v)   # 트리 T와 두개의 노드 u, v 위치교환 함수   if u.p == NIL           # u가 T의 루트일때     T.root = v   elseif u == u.p.left      # u가 T의 왼쪽 자식 노드일때, 해당 노드 v로 갱신     u.p.left = v   else u.p.right == v      # u가 T의 오른 오른 자식 노드일때, 해당 노드 v로 갱신   if v != NIL                 # v가 NIL아니면 v.p 갱신     v.p = u.p     TREE-DELETE(T, z)   if z.left == NIL                      # 노드 z가 왼쪽 자식 노드 없을때     TRANSPLANT(T, z, z.right)   elseif z.right == NIL               # 노드 z가 오른쪽 자식 노드 없을때     TRANSPLANT(T, z, z.left)   else y == TREE_MINIMUM(z.right)    # 노드 z가 두자식 노드를 가지는 경우(z의 직후원소 y 찾음)     if y.p != z                               TRANSPLANT(T, y, y.right)           # y의 오른자식 노드가 y의 부모의 자식노드가 되게 바꾸고       y.right = z.right                        # z의 오른자식노드를 y의 오른자식 노드로 삼는다.       y.right.p = y     TRANSPLANT(T, z, y)                   # 노드 z의 부모의 자식으로 y를 교체해 넣고     y.left = z.left                              # y의 오른자식노드가 y의 부모 자식노드가 되게 바꾸고     y.left.p = y                                 # y의 왼쪽 자식 노드를 z의 왼쪽 자식으로 교체한다.