영리한 프로그래밍을 위한 알고리즘 강좌 - Ch2.이진검색트리

10. 트리와 이진트리

 

– 트리(Tree)

계층적인 구조를 표현 (ex. 조직도, 디렉토리와 서브디렉토리 구조, 가계도)

트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨

 

 

용어

부모-자식 관계

형제관계

- 루트노드를 제외한 트리의 모든 노드들은 유일한 부모 노드를 가짐 

리프(leaf node)노드 : 자식이 없는 노드

조상-자손 관계

부트리

트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리를 부트리(subtree)라고 부른다

 

 

- 트리의 기본적인 성질

노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다

트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다(같은 노드를 두 번 이상 방문하지 않는다는 조건하에)

 

 

– 이진트리(Binary Tree)

이진 트리에서 각 노드는 최대 2개의 자식을 가진다

각각의 자식 노드는 자신의 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다(자식이 한 명인 경우에도)

ex ) expression tree , Huffman Code

 

 

- Full and Complete Binary  Trees

높이가 h인 full binary tree는 2^h - 1개의 노드를 가진다

노드가 N개인 full 혹은 complete 이진 트리의 높이는 O(logN)이다

 

 

- 이진 트리의 표현

연결구조(Linked Structure) 표현 - 각 노드에 하나의 데이터 필드와 왼쪽자식, 오른쪽자식, 그리고 부모노드의 주소를 저장

 

 

이진트리의 순회(traversal)

순회 : 이진 트리의 모든 노드를 방문하는 일

- 중순위(inorder) 순회

 

 

- 선순위(preorder) 순회

 

 

- 후순위(postorder) 순회

 

 

- 레벨오더(level-order) 순회

레벨 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로

큐(queue)를 이용하여 구현

 

LEVEL-ORDER-TREE-TRAVERSAL()
visit the root;
Q <- root;
while Q is not empty do
    v <- dequeue(Q);
    visit children of v;
    enqueue children of v into Q;
    END.
end.

 

 

 

 

 

---

 

 

11. 이진검색트리 Binary Search Tree

 

– Dynamic Set

 

여러 개의 키(key)를 저장

insert, search, delete 등의 연산들을 지원하는 자료구조 ex) 심볼 테이블

트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨

 

정렬된 혹은 정렬되지 않은 배열 혹은 연결 리스트를 사용할 경우 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n)

이진탐색트리(Binary Search Tree), 레드-블랙 트리, AVL-트리 등의 트리에 기반한 구조들

Direct Address Table, 해쉬 테이블 등

 

 

- 검색트리

Dynamic set을 트리의 형태로 구현

일반적으로 SEARCH, INSERT, DELETE 연산이 트리의 높이(height)에 비례하는 시간복잡도를 가짐

이진검색트리(Binary Search Tree), 레드-블랙 트리(red-black tree), B-트리 등

 

 

---

 

– 이진검색트리(BST)

 

이진 트리이면서

각 노드에 하나의 키를 저장

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

 

TREE-SEARCH(x,k)
  if x = NIL or k = key[x]
  	then return x
  if k < key[x]
    then return TREE-SEARCH(left[x],k)
    else return TREE-SEARCH(right[x],k)
  while x ≠ NIL and k ≠ key[x]
  	do if k < key[x]
      then x <- left[x]
      else x <- right[x]
  return x

시간복잡도 : O(h), 여기서 h는 트리의 높이

 

 

- 최소값

TREE-MINIMUM(X)
  while left[x] ≠ NIL
    do x <-left[x]
  return x

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

시간복잡도 : O(h)

 

 

- 최대값

TREE-MAXIMUM(X)
  while right[x] ≠ NIL
    do x <-right[x]
  return x

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

시간복잡도 : O(h)

 

 

- SUCCESSOR

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

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

항상 존재하는 건 아님

 

3가지 경우

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

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

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

- 그런 노드 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

시간복잡도 : O(h)

 

 

- Predecessor

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

Successor와 반대

 

 

- INSERT

TREE-INSERT(T,z)
  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] // Tree T was empty
           then left[y] <- z
           else right[y] <- z

 

 

- DELETE

case 1: 자식노드가 없는 경우 -> 그냥 삭제

case 2 : 자식노드가 1개인 경우 -> 자신의 자식노드를 원래 자신의 위치로

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

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

   2. successor 노드를 대신 삭제한다(Case 1 or 2에 해당)

 

TREE-DELETE(T,z)
  if left[z] = NIL or right[z] = NIL
    then y <- z
    else y <- TREE-SUCCESSOR(z)
  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

시간복잡도 : O(h)

 

---

 

BST

각종 연산의 시간복잡도 : O(h)

그러나, 최악의 경우 트리의 높이 h = O(n)

균형잡힌(balanced) 트리 

    - 레드-블랙 트리 등

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