자료구조와 알고리즘, Tree, Binary Search Tree

 

이진 탐색 트리(Binary Search Tree, BST)는 데이터의 효율적인 저장, 검색, 삽입 및 삭제를 위해 사용되는 트리 구조입니다. 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모 노드의 값보다 큽니다. 이러한 특성 덕분에 이진 탐색 트리는 정렬된 데이터를 효율적으로 처리할 수 있습니다.

이진 탐색 트리의 특성

1. 모든 노드의 값은 유일합니다.
2. 왼쪽 서브트리의 모든 노드 값은 부모 노드 값보다 작습니다.
3. 오른쪽 서브트리의 모든 노드 값은 부모 노드 값보다 큽니다.
4. 왼쪽 및 오른쪽 서브트리도 각각 이진 탐색 트리입니다.

주요 연산

1. 삽입 (Insert): 새로운 값을 올바른 위치에 추가합니다.
2. 검색 (Search): 특정 값이 트리에 존재하는지 확인합니다.

이진 탐색 트리의 구현 (자바스크립트 예제)

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    // Create a new node
    // Starting at the root
    // Check if there is a root, if not - the root now becomes that new node
    // If there is a root, check if the value of the new node is greater than or less than the value of the root

    // If it is greater
    // Check to see if there is a node to the right
    // If there is, move to that node and repeat these steps
    // If there is not, add that node as the right property

    // If it is less
    // Check to see if there a node to the left
    // If there is, move to that node and repeat these steps
    // If there is not, add that node as the left property
    let newNode = new Node(value);

    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let current = this.root;

    while (true) {
      if (value === current.value) return undefined;

      if (value < current.value) {
        if (current.left === null) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else if (value > current.value) {
        if (current.right === null) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  search(value) {
    // Starting at the root
    // Check if there is a root, if not - we're done searching!
    // If there is a root, check if the value of the new node is the value we are looking for.
    // If we found it, we're done!
    // If not, check to see if the value is greater than or less than the value of the root
    // If it is greater
    // Check to see if there is a node to the right
    // If there is, move to that node and repeat these steps
    // If there is not, we're done searching
    // If it is less
    // Check to see if there is a node to the left
    // If there is, move to that node and repeat these steps
    // If there is not, we're done searching!

    if (!this.root) return false;

    let current = this.root;
    let found = false;

    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        return true;
      }
    }

    return false;
  }
}

let tree = new BinarySearchTree();

console.log('tree is:', tree);
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(17);
tree.insert(7);
tree.insert(3);
tree.insert(13);
console.log('tree is:', tree);

console.log(tree.search(13));
console.log(tree.search(19));

설명

1. Node 클래스:
   • value: 노드의 값.
   • left: 왼쪽 자식 노드.
   • right: 오른쪽 자식 노드.
2. BinarySearchTree 클래스:
   • root: 트리의 루트 노드.
3. insert(value):
   • 새 노드를 생성하고 올바른 위치에 삽입합니다.
   • 루트 노드가 없으면 새 노드를 루트로 설정합니다.
   • 루트 노드가 있으면 값을 비교하여 왼쪽 또는 오른쪽 자식 노드로 이동하면서 삽입 위치를 찾습니다.
4. search(value):
   • 트리에서 특정 값을 가진 노드를 찾습니다.
   • 루트 노드부터 시작하여 값을 비교하면서 왼쪽 또는 오른쪽으로 이동합니다.

이진 탐색 트리는 삽입, 삭제, 검색 연산이 평균적으로 O(log n) 시간 복잡도를 가지며, 최악의 경우(편향 트리)에는 O(n) 시간 복잡도를 가집니다. 균형 잡힌 트리를 유지하기 위해 AVL 트리, 레드-블랙 트리와 같은 변형 트리를 사용할 수 있습니다.