자료 구조 - 이진 탐색 트리

‘c++로 쉽게 풀어쓴 자료구조 1판 - 천인국, 최영규’ 책을 참고하여 작성한 포스트입니다.

탐색이란?

• 컴퓨터 프로그램에서 탐색은 레코드(record)의 집합에서 특정 레코드를 찾는 작업이다.
• 레코드는 하나 이상의 필드(field)로 구성된다.
  • 예로, 학생의 레코드는 이름, 주소 등의 필드들로 이루어진다.
• 레코드들의 집합을 테이블(table) 이라고 한다.
• 레코드들은 보통 키(key)라고 불리는 하나의 필드에 의해 식별될 수 있다.
  • 키는 서로 중복되지 않는 고유한 값을 가지는데, 이를 사용해 레코드들을 구별할 수 있어 주요키(primary key) 라고 부른다.
  • 주민등록번호 등이 이에 해당 되겠죠.
• 탐색 작업은 어떤 키가 입력되었을 때 이 키를 가진 레코드를 찾는 작업이라고 볼 수 있다.

이진 탐색 트리(BST, Binary Search Tree)

이진 탐색 트리는 이진트리 기반의 탐색을 위한 자료구조로 효율적인 탐색 작업을 위한 자료구조이다.

• 다음과 같은 성질을 만족하는 이진트리이다.
  • 모든 노드는 유일한 키를 갖는다.
  • 왼쪽 서브트리의 키들은 루트의 키보다 작다.
  • 오른쪽 서브트리들의 키들은 루트의 키보다 크다.
  • 왼쪽과 오른쪽 서브트리도 이진 탐색 트리다.

이진 탐색 트리의 추상 자료형

데이터: 이진 탐색 트리의 특성을 만족하는 이진트리
연산
 - insert(n) : 이진 탐색 트리의 특성을 유지하면서 새로운 노드 n을 이진 탐색 트리에 삽입한다.
 - remove(n) : 이진 탐색 트리의 특성을 유지하면서 노드 n을 트리에서 삭제한다.
 - search(key) : 키 값이 key인 노드를 찾아 반환한다.

• 이진 탐색 트리는 키 값을 기준으로 정렬되어 있다. 다른 필드를 이용한 탐색도 가능하지만 탐색 효율이 떨어질 것이다.

이진탐색트리를 위한 클래스 (해보기!!)

이진 탐색 트리의 연산

탐색 연산

1. 비교한 결과가 같으면 탐색이 성공적으로 끝난다.
2. 비교한 결과 탐색키가 루트 노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작한다.
3. 비교한 결과 탐색키가 루트 노드의 키 값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.

구현 (해보기 !!)

삽입 연산

• 이진 탐색 트리에서는 같은 키 값을 갖는 노드가 없어야 한다.
• 탐색하는 과정에서 같은 키가 있다면 중복되므로 삽입이 불가능하다.
• 탐색을 하는 과정에서 어디선가 탐색이 실패로 끝나면 끝난 위치가 삽입할 위치다.

삭제 연산

노드를 삭제하는 것은 이진 탐색 트리에서 가장 복잡한 연산이다.
다음 3 가지 경우를 고려해야 한다.

• 삭제하려는 노드가 단말 노드일 경우
• 삭제하려는 노드가 왼쪽이나 오른쪽 서브트리 중 하나만 가지고 있는 경우
• 삭제하려는 노드가 두 개의 서브트리를 모두 가지고 있는 경우

삭제하려는 노드가 단말 노드일 경우

• 단말 노드 아래에 더 이상의 노드가 없으므로 단말 노드만 지우면 된다.

삭제하려는 노드가 하나의 서브트리만 가지고 있는 경우

• 해당 노드를 삭제하고 삭제된 노드의 유일한 자식을 부모 노드에 붙여주면 된다.

삭제하려는 노드가 두 개의 서브트리를 가지고 있는 경우

• 핵심은 삭제 후 서브트리에 있는 어떤 노드를 삭제 노드 위치로 가지고 오느냐이다. 왼쪽 자식이나 오른쪽 자식을 그냥 가져오면 안 된다.
• 삭제되는 노드와 가장 값이 비슷한 노드를 가져와야 한다.
• 가장 값이 비슷한 노드는 왼쪽 서브트리에서 가장 큰 값이나, 오른쪽 서브트리에서 가장 작은 값이다.

구현 (해보기!!)

최종 이진 트리 프로그램(구현 해보기!!)

이진 탐색 트리의 성능 분석

이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때 $O(h)$ 가 된다.
n개의 노드를 가지는 이진 탐색 트리의 경우, 일반적으로 높이는 $log_2n$이므로 이진 탐색 트리 연산의 평균적인 시간의 경우 시간 복잡도는 $O(log_2n)$ 이다.
물론 이것은 좌우의 서브트리가 균형을 이루고 있는 경우에 해당한다. 만약 한쪽으로 치우치는 완전한 경사 이진트리일 경우 트리의 높이가 n과 같게 되어 선형 탐색과 같은 $O(n)$이 된다.
결국 효율을 높이기 위해서는 가능한 한 트리가 좌우로 균형 잡히게 만들어야 한다.
AVL 트리 같은 기법들이 있다.