[Data-Structure] Tree (트리)와 Binary Search Tree (이진 탐색 트리) (2)Binary Search Tree (이진 탐색 트리) 란

지난번 글에 이어서 이번에는 Binary Search Tree (BST, 이진 탐색 트리) 에 대해서 알아보았다.

이진 탐색 트리는 최대 2개의 자식만 갖는 트리이다.  트리 구조는 재귀적이므로, 자식 노드 역시 최대 2개의 자식을 갖는다. 이진 탐색 트리에서는 노드의 값이 정렬 방법에 따라 순서가 존재하는데 노드의 왼쪽 서브 트리에는 노드의 값보다 작은 값이, 오른쪽 서브 트리에는 노드의 값보다 같거나 큰 값이 존재하게 된다. 

이진 탐색 트리 (BST) 예시

이진 탐색 트리는 트리 자료구조를 활용한 자료구조로 데이터 탐색 속도를 높일 때 사용한다.

• 이진 탐색 트리가 주어졌을 때, 세가지 방법으로 순회가 가능하다.
  • 전위 순회(Preorder Traversal): 부모 → 좌 → 우
  • 중위 순회(Inorder Traversal): 좌 → 부모 → 우
  • 후위 순회(Postorder Traversal): 좌 → 우 → 부모
• 이진 탐색 트리의 종류
  • 정 이진 트리(Full Binary Tree) : 모든 레벨에서 노드들이 꽉 채워진 이진트리 (leaf 노드 제외)
  • 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨에서 노드들이 꽉 채워진 이진트리
  • 포화 이진 트리(Perfect Binary Tree) : 모든 leaf 노드들의 레벨이 일치하며 leaf노드를 제외한 노드들이 모두 자식을 두 개씩 가지는 트리 (포화 이진 트리는 완전 이진 트리에 속한다.)

 

구현으로 넘어가자면 이번에는 중위 순회를 이용하여 자식 노드들을 순회하였다. (다른 순회 방법도 추후에 다룰 예정이다.)

 

class BinarySearchTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  // 이진 탐색 트리에 노드를 추가
  // 노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재
  insert(value) {
    let binarySearchTreeNode = new BinarySearchTreeNode(value); // 이진 탐색 트리 노드 생성

    if (value < this.value) {
      if (this.left !== null) { // 왼쪽 자식 노드가 비어있지 않다면
        this.left.insert(value); // 왼쪽 자식 노드안에서 insert함수 재귀 실행
        return;
      }
      this.left = binarySearchTreeNode; // 왼쪽 자식 노드가 비어있다면 왼쪽 자식노드에 해당 노드 넣어주기

    }
    else {
      if (this.right !== null) { // 오른쪽 자식 노드가 비어있지 않다면
        this.right.insert(value); // 오른쪽 자식 노드 안에서 insert 함수 재귀 실행
        return;
      }
      this.right = binarySearchTreeNode; // 오른쪽 자식 노드가 비어있다면 오른쪽 자식노드에 해당 노드 넣어주기
    }
  }

  // 이진 탐색 트리에 해당 노드가 존재하는지 여부를 반환
  contains(value) {
    if (this.value === value) { // 해당 노드의 value 값이 일치하다면 true 반환
      return true;
    }
    if (this.left !== null) { // 왼쪽 자식노드가 존재한다면
      let left = this.left.contains(value); // 왼쪽 자식 노드를 재귀적으로 실행
      if (left) { // 재귀로 호출한 값이 true 라면 true 리턴
        return true; 
      }
    }
    if (this.right !== null) { // 오른쪽 자식노드가 존재한다면
      let right = this.right.contains(value); // 오른쪽 자식 노드를 재귀적으로 실행
      if (right) { // 재귀로 호출한 값이 true 라면 true 리턴
        return true;
      }
    }
    return false; // 재귀를 통과할 때까지 일치하는 값이 없다면 false 리턴
  }

  // 이진 탐색 트리를 중위순회 -> 왼쪽 자식, 자기 자신, 오른쪽 자식 순으로 재귀적 실행 
  // -> 해당 노드에서 연결된 정점들을 체크하는데 더이상 체크할 수 없다면 다시 되돌아감
  inorder(callback) {
    // 왼쪽 자식이 있다면
    if (this.left !== null) { 
      this.left.inorder(callback); // 왼쪽 자식을 재귀적 실행
    }

    // 자기 자신 실행
    callback(this.value);

    // 오른쪽 자식이 있다면
    if (this.right !== null) {
      this.right.inorder(callback); // 오른쪽 자식을 재귀적 실행
    }
  }
}

 

사용 예시를 잠깐 살펴보자면

let rootNode = new BinarySearchTreeNode(5);
rootNode.insert(2);
rootNode.insert(3);
rootNode.insert(7);
rootNode.insert(6);

// 구조
/* 
   5
 2   7
- 3 6 -

 - 는 빈 값
*/

console.log(rootNode.left.right.value) // 3
console.log(rootNode.right.left.value) // 6

console.log(rootNode.contains(7)) // true


let array = [];
let func = function(value) {
  array.push(value);
};
rootNode.insert(2);
rootNode.insert(3);
rootNode.insert(8);
rootNode.insert(6);
rootNode.insert(10);
rootNode.inorder(func);
console.log(array); // [2, 3, 5, 6, 8, 10]

 

이런식으로 사용이 가능하다. 

이진 탐색 트리는 아직 공부해야 할 부분이 많이 남은 것 같다. 주말 내로 심화된 내용들을 좀 더 공부해볼 예정이다.