AVL Tree & Red-Black Tree란?
AVL 트리와 레드-블랙 트리는 모두 이진 탐색 트리의 일종으로, 데이터를 정렬된 순서로 유지하며 효율적인 탐색, 삽입 및 삭제 연산을 제공합니다. 이들 트리는 균형을 유지하기 위해 추가적인 제약을 도입해 높이가 최소한으로 유지되도록 합니다. 이로 인해 이진 탐색 트리에서 최악의 경우 발생할 수 있는 성능 저하를 방지합니다.
- AVL 트리:
AVL 트리는 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1이라는 조건을 만족하는 이진 탐색 트리입니다. 이 균형 조건 덕분에 AVL 트리의 높이는 항상 O(log N)을 유지하게 됩니다. AVL 트리에서 삽입이나 삭제가 일어날 때마다 트리의 균형을 유지하기 위해 회전 연산을 수행합니다. 회전 연산에는 일반적으로 LL, LR, RL, RR 회전이 포함됩니다. - 레드-블랙 트리:
레드-블랙 트리는 각 노드에 색상(레드 또는 블랙)을 부여하여 균형을 유지하는 이진 탐색 트리입니다. 레드-블랙 트리는 다음의 규칙을 만족합니다:
1. 각 노드는 레드 또는 블랙 중 하나의 색상을 가집니다.
2. 루트 노드는 항상 블랙입니다.
3. 모든 리프 노드(NIL 노드)는 블랙입니다.
4. 레드 노드의 자식 노드는 모두 블랙입니다. (레드 노드는 연속되지 않음)
5. 루트 노드에서 각 리프 노드까지의 모든 경로에는 동일한 개수의 블랙 노드가 있습니다.
레드-블랙 트리에서도 삽입과 삭제 시 트리의 균형을 유지하기 위해 회전 및 색상 조정을 수행합니다. 이 균형 조건 덕분에 레드-블랙 트리의 높이도 항상 O(log N)을 유지하게 됩니다.
AVL 트리와 레드-블랙 트리의 주요 차이점은 균형 유지 방식과 연관되어 있습니다. 두 트리 모두 균형을 유지하기 위해 회전 연산을 수행하지만, AVL 트리는 완전히 균형된 트리를 목표로 하여 노드 간 높이 차이를 최대 1로 제한하는 반면, 레드-블랙 트리는 트리 균형을 색상 조정을 통해 유지하며 완전한 균형을 추구하지 않습니다.
이러한 차이점으로 인해 AVL 트리와 레드-블랙 트리는 다음과 같은 특성을 보입니다:
- AVL 트리는 레드-블랙 트리보다 더 엄격한 균형 조건을 갖기 때문에, 일반적으로 더 낮은 높이를 가집니다. 따라서 검색 작업이 빈번한 경우에는 AVL 트리가 더 효율적일 수 있습니다.
- 레드-블랙 트리는 균형 조건이 덜 엄격하여 회전 연산이 상대적으로 적게 발생합니다. 그 결과, 삽입 및 삭제 작업이 빈번한 경우에 레드-블랙 트리가 더 효율적일 수 있습니다.
- 레드-블랙 트리는 색상 조정을 사용하여 균형을 유지하기 때문에, 구현이 상대적으로 간단하고 이해하기 쉽습니다. 이로 인해 실제 애플리케이션에서 레드-블랙 트리를 사용하는 경우가 많습니다.
결론적으로, AVL 트리와 레드-블랙 트리는 서로 다른 균형인 유지 방식을 가지고 있으며, 이에 따라 특성과 성능이 달라집니다. 특정 상황에 따라 두 트리 중 하나가 더 적합한 선택이 될 수 있습니다.
구현
AVL 트리
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
this.height = 1; // 높이 정보를 저장
}
}
class AVLTree {
constructor() {
this.root = null;
}
getHeight(node) {
if (node === null) {
return 0;
}
return node.height;
}
updateHeight(node) {
node.height = Math.max(this.getHeight(node.left), this.getHeight(node.right)) + 1;
}
getBalanceFactor(node) {
return this.getHeight(node.left) - this.getHeight(node.right);
}
// 오른쪽으로 회전
rotateRight(node) {
const newRoot = node.left;
node.left = newRoot.right;
newRoot.right = node;
this.updateHeight(node);
this.updateHeight(newRoot);
return newRoot;
}
// 왼쪽으로 회전
rotateLeft(node) {
const newRoot = node.right;
node.right = newRoot.left;
newRoot.left = node;
this.updateHeight(node);
this.updateHeight(newRoot);
return newRoot;
}
insert(value) {
this.root = this.insertNode(this.root, value);
}
insertNode(node, value) {
// 1. 기본 BST 삽입
if (node === null) {
return new TreeNode(value);
}
if (value < node.value) {
node.left = this.insertNode(node.left, value);
} else if (value > node.value) {
node.right = this.insertNode(node.right, value);
} else {
// 같은 값은 삽입하지 않음
return node;
}
// 2. 높이 갱신
this.updateHeight(node);
// 3. 균형인자 계산 및 회전
const balanceFactor = this.getBalanceFactor(node);
// 왼쪽 자식이 높아서 불균형 발생
if (balanceFactor > 1) {
// 오른쪽 회전 전, 왼쪽 자식의 오른쪽 자식이 더 높다면 왼쪽 자식을 왼쪽으로 회전
if (value > node.left.value) {
node.left = this.rotateLeft(node.left);
}
return this.rotateRight(node);
}
// 오른쪽 자식이 높아서 불균형 발생
if (balanceFactor < -1) {
// 왼쪽 회전 전, 오른쪽 자식의 왼쪽 자식이 더 높다면 오른쪽 자식을 오른쪽으로 회전
if (value < node.right.value) {
node.right = this.rotateRight(node.right);
}
return this.rotateLeft(node);
}
return node;
}
}
// 테스트 코드
const avl = new AVLTree();
avl.insert(10);
avl.insert(20);
avl.insert(30);
avl.insert(40);
avl.insert(50);
console.log(avl.root.value); // 출력: 30Red-Black 트리
class TreeNode {
constructor(value, isRed = true) {
this.value = value;
this.left = null;
this.right = null;
this.isRed = isRed; // 노드의 색상을 저장
}
}
class RedBlackTree {
constructor() {
this.root = null;
}
isRed(node) {
if (node === null) {
return false; // null 노드는 항상 black입니다.
}
return node.isRed;
}
// 왼쪽 회전
rotateLeft(node) {
const newRoot = node.right;
node.right = newRoot.left;
newRoot.left = node;
newRoot.isRed = node.isRed;
node.isRed = true;
return newRoot;
}
// 오른쪽 회전
rotateRight(node) {
const newRoot = node.left;
node.left = newRoot.right;
newRoot.right = node;
newRoot.isRed = node.isRed;
node.isRed = true;
return newRoot;
}
flipColors(node) {
node.isRed = !node.isRed;
node.left.isRed = !node.left.isRed;
node.right.isRed = !node.right.isRed;
}
insert(value) {
this.root = this.insertNode(this.root, value);
this.root.isRed = false;
}
insertNode(node, value) {
if (node === null) {
return new TreeNode(value);
}
if (value < node.value) {
node.left = this.insertNode(node.left, value);
} else if (value > node.value) {
node.right = this.insertNode(node.right, value);
} else {
// 같은 값은 삽입하지 않음
return node;
}
// 회전 및 색상 변경
if (this.isRed(node.right) && !this.isRed(node.left)) {
node = this.rotateLeft(node);
}
if (this.isRed(node.left) && this.isRed(node.left.left)) {
node = this.rotateRight(node);
}
if (this.isRed(node.left) && this.isRed(node.right)) {
this.flipColors(node);
}
return node;
}
}
// 테스트 코드
const rbt = new RedBlackTree();
rbt.insert(10);
rbt.insert(20);
rbt.insert(30);
rbt.insert(40);
rbt.insert(50);
console.log(rbt.root.value); // 출력: 20
Move fast & break things