(자료구조) 이진 탐색트리

이진 탐색트리란?

이진 탐색과 연결 리스트(linked list)를 결합한 자료구조의 일종이다. 이진 탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료입력과 삭제를 가능하게끔 고안됐다.

이진 트리의 변형으로 좌측 자식 노드에는 더 작은 값을, 우측 자식 노드에는 더 큰 값을 들고 있다는 차이점이 있다.

연결 리스트와 마찬가지로 노드 간 연결은 포인터로 나타낸다. 이중 연결 리스트는 노드당 2개의 포인터(다음/이전 노드 포인터)가 있다. 트리 역시 포인터가 2개 있는데, 각각 좌측, 우측 자식 노드를 가리킨다.

이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logN)으로 빠르지만 자료입력이나 삭제가 불가능하다.

연결 리스트의 경우 자료입력, 삭제에 필요한 계산 복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 계산 복잡성이 발생한다.

이 두개의 장점을 살려보는 것이 이진 탐색트리의 목적이라고 할 수 있다.

속성

• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색트리이다.
• 이진 탐색트리를 순회할 때에는 중위순회(in order)방식을 사용한다.
  왼쪽 서브트리 → 노드 → 오른쪽 서브트리
  
• 위 그림에서 중위 순회를 사용하면 순서는
  1 → 3 → 5 → 7 → 8 → 10

작동

이진 탐색트리의 핵심 연산은 검색, 삽입, 삭제로 세가지이다. 이밖에 생성, 이진탐색트리 삭제, 해당 이진 탐색트리가 비어있는지 확인, 트리순회의 연산들이 있다.

BinarySearchTree 클래스 만들기

function BinarySearchTree() {
  
  let Nodw = function (key) { // {1}
    this.key = key;
    this.left = null;
    this.right = null;
  };
  
  let root = null; // {2}
}

우선 트리 노드를 표현하는 Node 클래스를 선언한다. 여기서 노드를 원소라 하지 않고 키라고 한 부분을 주목하자. 트리에서는 키로 노드를 식별한다.

자료 구조의 첫 번째 노드를 변수로 선언해서 제어하는 식으로 진행된다. 단, 트리에서는 헤드(연결리스트의)가 아닌 루트라는 점이 다르다.

출처

• 자바스크립트와 알고리즘 (로이아르 그리네르, 이일웅 옮김)