[Introduction to Algorithms] 이진 검색 트리

 

1) 이진 검색 트리란?

 

- 검색 트리 자료구조는 SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE를

  비롯해 많은 동적 집합 연산을 지원한다.

  따라서 검색 트리를 사전(dictionary) 및 우선순위 큐(priority queue)로 사용할 수 있다.

 

- 이진 검색 트리에 대한 기본 연산은 트리의 높이에 비례하는 시간에 수행된다.

  n개의 노드로 이루어진 완전 이진 검색 트리(complete binary search tree)에 대해

  이런 연산들은 최악의 경우, O(lgn) 시간에 실행된다.

  그러나 트리가 n개의 노드가 선형으로 연결된 모양일 경우 평균 O(n) 시간에 수행된다.

 

- 앞으로 만들어진 이진 검색 트리의 높이의 기댓값이 O(lgn)임을 확인할 것이다.

  따라서 이런 트리에 대한 기본 동적 집합 연산들은 평균 O(lgn) 시간에 수행된다. 

 

- 실제 상황에서 이진 검색 트리가 항상 임의로 만들어진다고 보장할 수는 없다.

  하지만 기본 연산들에 대해서 최악의 경우에도 빠른 실행 속도를 보장할수 있는 

  이진 검색 트리의 변형을 설계할 수 있다.

  레드블랙 트리라고 하는 변종은 높이가 O(lgn)이다.

  이차 저장공간(디스크)에서 데이터베이스를 관리하는데 특히 유용한 B-트리도 존재한다.

 

- 이진 검색 트리의 기본 특성을 제시한 후 

  (1) 이진 검색 트리를 순회(walk)하는 방법

  (2) 이진 검색 트리에서 하나의 값을 검색하는 방법,

  (3) 최대 원소 또는 최소 원소를 찾는 방법

  (4) 한 원소의 직전원소 또는 직후원소를 찾는 방법,

  (5) 이진 검색 트리에 삽입 또는 삭제를 수행하는 방법을 다룬다.

 

2) 이진 검색 트리의 개념

- 이진 검색 트리는 각 노드를 객체로 하는 연결 자료구조로 표현할 수 있다.

  또한 key, 부속 데이터(satellite data)와 함께 left, right, p 필드를 가지는데, 

  이들은 각각 왼쪽 자식, 오른쪽 자식, 부모에 해당하는 노드를 가리킨다.

 

- 자식이나 부모가 없으면 해당 필드는 NIL 값을 가진다.

  그리고 루트 노드는 부모가 NIL인 유일한 노드다. 

 

- 이진 검색 트리에서 키들은 항상

  다음의 이진 검색 트리 특성(binary-search-tree property)을 만족하도록 저장된다.

  x를 이진 검색 트리의 한 노드라고 하자. y가 x의 왼쪽 서브 트리의 한 노드면 y.key<=x.key를
  만족한다. 그리고 y가 x의 오른쪽 서브 트리의 한 노드면 y.key >= x.key를 만족한다.

 

- 이진 검색 트리 특성에 의해 중위 트리 순회(inorder tree walk)라고 하는

  간단한 재귀 알고리즘을 통해서 이진 검색 트리의 모든 키를 정렬된 순서대로 출력할 수 있다.

 

- 이 알고리즘 이름은 루트의 키를 왼쪽 서브 트리의 키와 오른쪽 서브 트리의 키 사이에 출력한다는 사실에서 유래한다

  (이와 유사하게, 전위 트리 순회는 루트를 양쪽 서브 트리의 키보다 먼저 출력하고,  

   후위 트리 순회는 루트를 양쪽 서브 트리의 키보다 나중에 출력한다)

 

- 이진 검색 트리 T의 모든 원소를 출력하려면

  다음 프로시저 INORDER-TREE-WALK의 (T.root)를 호출하면 된다.