이진 탐색 트리(Binary Search Tree)

✅ 이진 탐색 트리란

이진 탐색 개념으 트리 구조에 적용한 것

 

✅ 활용

- (균형잡힌 트리인 경우) 효율적인 '검색'을 위해

- 데이터 '삽입', '삭제'가 빈번할 경우

- 우선순위가 필요한 작업 (최소값,최대값 빠르게 탐색)

-  데이터베이스 인덱싱, 정렬, 검색 엔진, 네트워크 라우팅(라우팅 테이블 관리시) 등

 

✅ 시간복잡도

O(log n) : 모든 노드를 탐색하지 않고, 트리의 높이만큼 탐색하게 된다. (왼쪽, 오른쪽 트리의 높이가 비슷할 경우)

O(n) : 그러나 트리가 한쪽으로 치우쳐 세로로 늘어진 경우 성능 저하 

 

✅ 특징

1. 각 노드의 왼쪽 가지의 값들은 본인보다 작다
: 10을 예로들면, 10 아래의 3,8은 10보다 작다

 

2. 각 노드의 오른쪽 가지 값들은 본인보다 크다.

: 16을 예로들면, 23,17,28은 16 보다 크다.

 

✅ 조회

1. 최소값 조회 : 왼쪽 트리만 탐색하면 됨 (16 → 10 → 3) 

2. 최대값 조회 : 오른쪽 트리만 탐색하면 됨 (16 → 23 → 28)

 

✅ 삽입

1. 루트노드 보다 작은 값을 넣는 경우

- 5를 넣는 경우 : 16보다 작음(왼쪽으로) -> 10보다 작음(왼쪽으로) -> 3보다 큼(오른쪽으로) -> 8보다 작음(왼쪽으로)

 

2. 루트노드 보다 큰 값을 넣는 경우

- 25를 넣는 경우 : 16보다 큼(오른쪽으로) -> 23보다 큼(오른쪽으로) -> 28보다 작음(왼쪽으로)

삽입 결과

 

✅ 삭제

1. 자식노드가 없는 경우

- 25 삭제하는 경우 : 그냥 25 본인만 제거된다.

 

2. 자식노드가 하나 딸린 노드 삭제시

- 8을 삭제하는 경우 : 8제거 후 4는 3보다 크므로 3의 오른쪽으로 이동

 

3.자식노드가 두개 딸린 노드 삭제시

- 10을 삭제하는 경우
: 10제거 후 삭제한 노드 기준 "왼쪽 가지의 최대 노드" OR  "오른쪽 가지의 최소 노드"를 삭제된 위치로 이동한다. 

: 왼쪽 가지의 최대 노드를 이동하면 (10의 왼쪽 가지(3) -> 3 자식 중 제일 큰 값(4) -> 4를 이동)

삭제 결과

 

✅  javascript 로 구현한 BST

class Node {
  constructor(value) {
    this.value = value;

    this.left = null;

    this.right = null;
  }
}

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

  // 새로운 값을 트리에 삽입하는 메서드
  insert(value) {
    const newNode = new Node(value);

    if (this.root === null) {
      this.root = newNode;
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  // 재귀적으로 노드를 삽입하는 메서드
  insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

  // 트리에서 특정 값을 검색하는 메서드
  search(value) {
    return this.searchNode(this.root, value);
  }

  // 재귀적으로 노드를 검색하는 메서드
  searchNode(node, value) {
    if (node === null) {
      return false;
    }

    if (value < node.value) {
      return this.searchNode(node.left, value);
    } else if (value > node.value) {
      return this.searchNode(node.right, value);
    } else {
      return true;
    }
  }

  // 트리에서 특정 값을 삭제하는 메서드
  delete(value) {
    this.root = this.deleteNode(this.root, value);
  }

  // 재귀적으로 노드를 삭제하는 메서드
  deleteNode(node, value) {
    if (node === null) {
      return null;
    }

    if (value < node.value) {
      node.left = this.deleteNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.deleteNode(node.right, value);
    } else {
      // 노드를 찾았을 때

      if (node.left === null && node.right === null) {
        // 리프 노드: 단순히 삭제
        return null;
      }

      if (node.left === null) {
        // 오른쪽 자식만 있는 경우
        return node.right;
      }

      if (node.right === null) {
        // 왼쪽 자식만 있는 경우
        return node.left;
      }

      // 두 개의 자식 노드가 있는 경우
      const maxValue = this.findMaxValue(node.left);
      node.value = maxValue;
      node.left = this.deleteNode(node.left, maxValue);
    }

    return node;
  }

  // 삭제시, 왼쪽 서브트리에서 최대 값을 찾는 메서드
  findMaxValue(node) {
    let current = node;

    while (current.right !== null) {
      current = current.right;
    }

    return current.value;
  }
}

// 사용 예제
const bst = new BinarySearchTree();

// <삽입>
bst.insert(15);
bst.insert(9);
bst.insert(23);
bst.insert(3);
bst.insert(12);
bst.insert(17);
bst.insert(1);
bst.insert(8);
bst.insert(4);

/*
         15
       /    \
      9      23
     / \     / 
    3  12   17
   / \
  1   8
     /
    4
*/

// <조회>
console.log(bst.search(4)); // true
console.log(bst.search(99)); // false

// <삭제>
bst.delete(8); // 삭제할 노드: 8
bst.delete(9); // 삭제할 노드: 9

/*
         15
       /    \
      4      23
     / \     / 
    3  12   17
   /
  1
*/