개념 - 이진 탐색 트리

탐색

탐색이란 방대한 자료에서 원하는 자료를 찾아내는 자료구조적인 관점에서 중요한 작업이다. 이진 탐색 트리는 탐색에 특화된 이진트리다. 

용어

레코드 (record) : 하나 이상의 필드(field)로 구성됨. (ex : 이름, 나이, ...)

테이블 (table) : 레코드들의 집합.

키 (key) : 레코드를 식별할 수 있는 하나의 필드로, 레코드들간에 중복되지 않는 고유한 값을 주요 키(primary key)라고 부른다.

이진 탐색트리의 특성

효율적인 탐색을 위한 자료구조로써, 다음과 같이 순환적으로 정의된다.

- 모든 노드는 유일한 키를 갖는다.

- 왼쪽 서브트리의 키들은 루트의 키보다 작다.

- 오른쪽 서브트리의 키들은 루트의 키보다 크다.

- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리다.

이진 탐색 트리의 ADT

- 일단 BST도 이진 트리 이기에, 이진트리의 ADT를 모두 포함시킬 수 있다. 

- 삽입 : 이진 탐색 트리의 특성을 유지한채로 삽입.

- 삭제 : 이진 탐색 트리의 특성을 유지한채로 삭제.

- 키를 통한 검색

이진 탐색 트리의 연산

탐색 : 순환, 반복으로 구현

1. 주어진 키 값과 루트 값을 비교한다.

2. 루트 값이 키 값이 일치하면 해당 노드 리턴

2-1. 키 값이 루트 값 보다 작으면 왼쪽 노드로 가서 1~2반복 (null 까지)

2-2. 키 값이 루트 값 보다 크면 오른쪽 노드로 가서 1~2반복 (null 까지)

삽입 : 

1. 주어진 키 값과 루트 값을 비교한다.

2-1. 키 값이 루트 값 보다 작을 때

왼쪽 노드가 비었다면 거기에 삽입

아니라면 왼쪽 노드로 가서 1~2반복 

2-2. 키 값이 루트 값 보다 클 때

오른쪽 노드가 비었다면 거기에 삽입

아니라면 오른쪽 노드로 가서 1~2 반복

삭제 :

삭제 후에도 이진 검색 트리의 특성을 유지해야하는 조건 때문에, 삭제연산은 생각해야할 경우의 수가 좀 있다.

1. 삭제할 노드가 단말 노드일 때

-> 삭제할 노드와 부모 노드만 알면 된다.

2. 삭제할 노드의 자식이 하나 일 때

-> 삭제한 노드를 자식으로 대체하기 위해서 (썩시딩 유, 파더)

    삭제할 노드, 삭제할 노드의 부모 노드, 삭제할 노드의 자식 노드를 알아야 한다.

3. 삭제할 노드의 자식이 둘 일 때

-> 삭제할 노드를 어떤 노드로 대체할 것인가?

-> 제일 복잡한 상황으로, 그림을 보면서 이해하는 게 좋다.

이진 검색 트리를 중위 순회할 때 (즉 오름차순으로 순회할 때), 순서상으로 삭제할 노드의 바로 앞 노드는 왼쪽 서브트리의 제일 오른쪽 노드이며, 바로 뒤 노드는 오른쪽 서브트리의 제일 왼쪽 노드다. 이 때 어느 걸 선택해도 상관없으나, 책에선 오른쪽 노드를 사용한다.

코드가 복잡하니, 시간을 들여 단순하게 구현해보자.

이진 탐색 트리의 성능

트리의 높이가 h일 때, 탐색, 삽입, 삭제 연산의 시간 복잡도는 O(h)가 된다.

n 개의 노드를 가지는 이진 탐색 트리는 평균적인 높이가 log 2 n이므로 이진 탐색 트리 연산의 평균적인 경우의 시간 복잡도는 O(log2 n)이다. 선형 복잡도(n)보다 훨씬 빠르다. 2^32 번의 연산이 필요한 선형 복잡도 계산을 32번만에 할 수 있으니 말이다. 단, 이 때의 '평균'이란 트리의 좌우가 균형을 이루고 있을 때에만 해당된다. 대각선으로 치우쳐진 최악의 경우의 경사 이진 탐색 트리의 수행시간은 O(n)이 된다. 

AVL 등의 방법으로 트리의 높이를 log2 n로 고정하는 방법은 나중에 공부한다.

구현 : 

http://kid5.tistory.com/271