[ 알고리즘 / 탐색 ] 이진 탐색 트리 (Binary Search Tree)

Dynamic Set이란?

- 배열, 링크드 리스트, 트리 등등..

- 여러 개의 키(key) 저장

- 다음과 같은 연산을 지원하는 자료구조

① INSERT - 새로운 키의 삽입

② SEARCH - 키 탐색

③ DELETE - 키의 삭제

다양한 방법들

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

- 이진 탐색 트리(Binary Search Tree), 레드-블랙 트리, AVL-트리

- Direct Address Table, 해쉬 테이블 등

검색 트리란?

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

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

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

 

이진 탐색 트리 (Binary Search Tree)란?

- 이진 트리이다.

- 각 노드에 하나의 키(key)를 저장

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

이진 탐색 트리

Heap VS Binary Search Tree

Heap은 Complete 이진 트리이고, Max-Heap-Property(부모는 자식보다 크다.)를 만족해야 한다. 

Binary Search Tree은 제한 없는 이진트리이며, 내 왼쪽은 나보다 작고, 내 오른쪽은 나보다 크다.

 

 검색 (SEARCH) 

시간 복잡도 O( h ) , h = 트리의 높이

h 값은?

skewd tree(한 쪽으로만 쭉 내려온 트리)일 경우 : h = n

이상적인 트리 : h = logn

 

Binary Search Tree에서 13를 찾을 때

1. 먼저 루트노드로 접근한다.

2. 루트노드 15보다 작기 때문에 왼쪽 자식으로 내려간다.

3. 왼쪽 자식인 6보다 크기 때문에 오른쪽 자식으로 내려간다.

4. 13을 찾았기 때문에 종료한다.

 

 

[ 재귀 사용 ]

 

Tree-Search( X , K )   // X = root, 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 )

[ 반복문 사용 ]

 

Tree-Search( X , K )   // X = root, K = 찾는 값
    whlie x != NIL and K != key[ X ]
             do if K < key[ X ]
                       then X <- left[ X ]
                       else X <- right[ X ]
   return X

최소값 찾기

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

시간복잡도: O(h)

 

Tree-Minimum( X )
   while left[ X ] != NIL
              do X <- left[ X ]
   return X

최대값 찾기

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

시간복잡도: O(h)

 

Tree-Minimum( X )
   while right[ X ] != NIL
              do X <- right[ X ]
   return X

Successor

노드 X의 Successor란 key[ X ]보다 큰 값 중에 가장 작은 키를 가진 노드

3가지 경우

1. 노드 X의 오른쪽 서브트리가 존재하면, 오른쪽 서브트리의 최소값.

2. 오른쪽 서브트리가 없는 경우, 부모를 따라 루트노드로 올라가다가 처음으로 어떤 노드의 왼쪽 노드가 되는 노드 Y.

즉, 어떤 노드 Y의 왼쪽 서브트리의 최대값이 X가 되는 그런 노드 Y가 X의 Successor이다. 

3. 그런 노드 Y가 존재하지 않는 경우, Successor가 존재하지 않는다. -> X가 최대값

 

Tree-Succesor( 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) 

이진 검색 트리에서 새로운 데이터를 추가할 때 기존의 노드를 변경하거나 자리를 바꾸지 않고, 새로운 노드를 기존 트리의 리프 노드에 추가한다.

 

시간 복잡도 O( h ) , h = 트리의 높이

 

Binary Search Tree에서 14를 삽입할 때

1. 루트 노드와 비교하여 작으면 왼쪽, 크면 오른쪽으로 이동한다.

2. 이동한 자식 노드부터 1번 반복한다.

3. 이동하려는 위치의 자식 노드가 NULL이면 그 위치에 추가한다.

 

 

Empty BST에 하나씩 데이터를 추가할 때

 

Tree-Insert( T, z )
    y <- NIL
    x <- root[ T ]
    whlie x != NIL
          do
                y <- x
                if key[ z ] < key[ x ]
                      then x <- left[ x ]
                      else x <- right[ x ]
    p[ z ] <- y     // 의 부모가 y가 된다.

    if y == NIL     // 트리가 비어있을 때
           then root[ T ] <- z
           else if key [ z ] < key [ y ]
                      then left[ y ] <- z
                      else right[ y ] <- z

 

 삭제 (DELETE) 

① 자식 노드가 없는 경우 O( 1 )

② 자식노드가 1개인 경우 O( 1 )

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

③ 자식노드가 2개인 경우 O( h )

13을 삭제하면 6, 18이 부모가 없어진다.

13의 값을 삭제하고 어떤 노드의 값을 가져와야 할까?

삭제하려는 13보다는 크면서, 가장 작은 값을 가져와야 한다. 즉, 13의 Successor를 가져와야 한다.

자식이 2개이기 때문에 오른쪽 자식 노드 소유는 보장된다. 오른쪽 서브트리의 최소값을 찾아 변경해주면 된다.

찾아낸 노드는 최소값이기 때문에 왼쪽 자식노드는 항상 없고, 오른쪽 자식 노드는 있거나 없기 때문에 ①, ② 중 적용해주면 된다.

Tree-Delete( T, z )    // z = 삭제할 노드
   if left[ z ] == NIL or right[ z ] == NIL  // 자식이 0개 or 1개
           then y <- z
           else y <- Tree-Successor( z ) // 자식 2개
   // y = 삭제할 노드
   // 자식이 없거나 1개이면 z를 바로 삭제하고, 자식이 2개이면 Successor가 삭제할 대상
   // Successor일지라도 왼쪽 자식노드는 없기 때문에 자식이 0개 or 1개 보장

   if left[ y ] != NIL
           then x <- left[ y ]            // y의 왼쪽 자식이 있다면
           else x <- right [ y ]          // y의 오른쪽 자식이 있다면

   // x = 삭제할 y노드 자리에 변경될 노드

  if x != NIL
           then p[ x ] <- p[ y ]                   // x의 부모를 y의 부모로

  if p[ y ] == NIL                                    // y가 루트라면
           then root[ T ] <- x                     // x가 루트가 된다
           else if y == left[ p[ y ] ]              // 삭제할 노드 y가 부모의 왼쪽 자식이었으면
                      then left[ p[ y ] ] <- x     // x가 왼쪽 자식이 되고
                      else right[ p[ y ] ] <- x    // 오른쪽 자식이었으면 x가 오른쪽 자식이 된다
 
// ③인지? ③이었으면 삭제할 y가 Successor로 바뀌었기 때문
  if y != z
           then key[ z ] <- key[ y ]
  
  return y

이진 탐색 트리 (Binary Search Tree)의 시간복잡도

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

평균적으로 O(h = logn)이지만,

최악의 경우 한 쪽으로 편향된 트리의 높이가 n이 되어 O(n)

균형잡힌(balanced) 트리

레드-블랙 트리 등

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