C++로 쉽게 풀어쓴 자료구조/ 이진 탐색 트리

이진 탐색 트리

탐색이란?

컴퓨터 프로그램에서 탐색은 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미한다.

레코드는 하나 이상의 필드(field)로 구성된다. 예컨대 학생의 레코드는 이름, 주소, 주민등록번호 등의 필드들로 이루어진다. 일반적으로 레코드들의 집합을 테이블(table)이라고 한다.

레코드들은 보통 키(key)라고 불리는 하나의 필드에 의해 식별할 수 있다. 키는 서로 중복되지 않는 고유한 값을 가지는데, 키를 사용하면 각각의 레코드들을 구별할 수 있다. 이러한 키를 주요키(primary key)라고 한다.

이진 탐색 트리란?

이진 탐색 트리는 이진트리 기반의 탐색을 위한 자료구조로 효율적인 탐색 작업을 위한 자료구조이다. 이진 탐색 트리는 특별한 성질을 만족하는 이진트리를 말하는데, 다음과 같이 순환적으로 정의된다.

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

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

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

이진 탐색 트리의 연산

탐색 연산

이진 탐색 트리에서 어떤 탐색키를 가진 노드를 찾기 위해서는 먼저 주어진 탐색키와 현재의 루트 노드의 키 값을 비교해야 한다.

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

삽입 연산

이진 탐색 트리에서 원소를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요하다. 이유는 이진 탐색 트리에서는 같은 키 값을 갖는 노드가 없어야 하기 때문이고, 또한 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치가 되기 때문이다.

삭제 연산

노드를 삭제하는 것은 이진 탐색 트리에서 가장 복잡한 연산이다. 노드를 삭제하기 위해서는 먼저 노드를 탐색하여야 한다는 것은 삽입과 마찬가지다. 노드의 삭제에는 다음의 3가지 경우를 고려해야 한다.

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

이진 탐색 트리에서 삭제는 어떤 조직에서 후계자를 정하는 것과 비슷하다. 첫 번째 경우는 물려줄 사람이 없으므로 간단하다. 두 번째 경우는 후계자가 하나 뿐이므로 그 사람에게 물려주면 된다. 세 번째 경우는 조직 안에 두 개의 파벌이 존재하는 경우인데, 이 경우에는 양쪽 파벌 중에서 제일 중도 노선을 걷는 사람에게 물려주는 편이 가장 반발을 적게 할 수 있다.

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

삭제하려는 노드가 단말 노드인 경우 노드 아래에 더 노드가 없으므로 단말 노드만 지우면 끝난다. 단말 노드를 지운다는 것은 단말 노드의 부모를 찾아서 부모 노드의 링크 필드를 null 로 만든다는 뜻이다.

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

삭제되는 노드가 왼쪽이나 오른쪽 서브트리 중 하나만 갖고 있는 경우 그 노드는 삭제하고 삭제된 노드의 유일한 자식을 부모 노드에 붙여 주면 된다.

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

이 경우 삭제되는 노드와 가장 값이 비슷한 노드가 삭제되는 위치에 와야 한다. 그렇다면 가장 가까운 노드는 어디에 있을까? 왼쪽 서브트리에서 가장 큰 값이나 오른쪽 서브트리에서 가장 작은 값이 삭제되는 노드와 가장 가까운 값을 가진 노드이다.

왼쪽 서브트리에서 가장 큰 값이나 오른쪽 서브트리에서 가장 작은 값 중 어느 값을 쓰던 상관은 없다. 다만 현재 삭제하는 노드의 부모와, 대체할 노드의 부모를 모두 알아야 하고 그 연결 관계를 조정해주어야 하므로 코드는 복잡해진다.

이진 탐색 트리의 성능 분석

이진 탐색 트리에서 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때 O(h)가 된다. n개의 노드를 가지는 이진 탐색 트리의 경우, 일반적인 이진트리의 높이는 log2n이므로 이진 탐색 트리 연산의 평균적인 경우의 시간 복잡도는 O(log2n)이다.

물론 이것은 좌우의 서브트리가 균형을 이루고 있는 경우에 해당한다. 만약 한쪽으로 치우치는 완전한 경사 이진트리일 경우 트리의 높이가 n과 같게 되어 탐색, 삭제, 삽입 시간이 선형 탐색과 같은 O(n)이 된다. 결국 이진 탐색 트리의 효율을 높이기 위해서는 가능한 한 트리가 좌우로 균형 잡히게 만들어야 한다.

[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기