레드-블랙 트리는 자가 균형 이진 검색 트리로, 삽입, 삭제, 검색 연산을 O(log n) 시간에 수행합니다. 이진 검색 트리가 부울 값(true 또는 false)을 이용해 잦은 회전으로 인한 균형을 유지한다면 레드-블랙 트리는 색상 속성으로 균형을 보장합니다.

특징

• 각 노드는 레드(red) 또는 블랙(black) 중 하나의 색상을 갖습니다.
• 루트와 잎 노드는 블랙이며, 레드 노드의 자식은 모두 블랙입니다.
• 어떤 노드로부터 잎 노드까지의 모든 경로에는 동일한 개수의 블랙 노드가 있습니다.

삽입

레드-블랙 트리에 노드를 삽입하는 과정은 다양한 색상 조합의 경우를 고려해야 합니다. 이 과정은 트리를 재균형하는 회전 연산을 수반하며, 새로 삽입된 노드를 레드로 지정한 다음 일정한 규칙에 따라 색상을 조정합니다.

삭제

노드를 삭제할 때도 트리의 균형을 유지하기 위해 회전 연산과 색상 조정이 필요합니다. 삭제된 노드가 레드일 경우, 재균형을 위해 추가적인 처리 과정을 거칩니다.

JavaScript 예시

class Node {
  constructor(data, color) {
    this.data = data;
    this.left = null;
    this.right = null;
    this.color = color; // "red" or "black"
  }
}

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

  // 삽입 연산
  insert(data) {
    // insert logic
  }

  // 삭제 연산
  delete(data) {
    // delete logic
  }

  // 검색 연산
  search(data) {
    // search logic
  }
}

레드-블랙 트리는 데이터베이스 인덱스, 맵, 집합 등의 구현에서 널리 활용됩니다. 이진 검색 트리와 다르게, 트리의 높이가 대략적으로 2log(n+1) 보다 크기 때문에 대량의 데이터를 저장할 때 유용하게 활용될 수 있습니다.

자세한 내용은 GeeksforGeeks - Red-Black Tree를 참고하시기 바랍니다.