균형 트리는 트리 구조에서 모든 리프 노드까지의 깊이 차이가 1을 넘지 않는 트리를 말합니다. 균형 트리는 데이터를 효율적으로 관리하고 탐색 작업을 빠르게 수행할 수 있는 장점을 가지고 있습니다.

AVL 트리 (AVL Tree)

AVL 트리는 균형 트리의 한 종류로서, 각 노드의 두 서브트리의 높이 차이가 1을 넘지 않는 이진 탐색 트리입니다. AVL 트리는 삽입, 삭제 작업 시에도 항상 균형을 유지하여 탐색 시간을 최소화할 수 있습니다.

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

function getHeight(node) {
  if (node === null) return 0;
  return node.height;
}

AVL 트리에서는 각 노드의 높이를 계산하고, 모든 노드가 균형을 유지할 수 있도록 회전 연산을 통해 트리를 재조정합니다.

Red-Black 트리 (Red-Black Tree)

Red-Black 트리는 균형을 유지하기 위한 규칙을 갖는 이진 탐색 트리입니다. 이 트리는 각 노드가 레드 또는 블랙 중 하나의 색을 가지며, 삽입, 삭제 작업 시에도 균형을 유지합니다.

class RBNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.color = "red";
  }
}

// Insert and balance operations

Red-Black 트리는 노드의 색을 조정하고 회전 연산을 수행하여 균형을 유지합니다.

결론

균형 트리는 데이터를 효율적으로 관리하기 위한 중요한 데이터 구조 중 하나입니다. AVL 트리와 Red-Black 트리는 각각 다른 방식으로 균형을 유지하며, 이를 통해 빠른 탐색 작업을 가능하게 합니다.

자료 출처