[javascript] 순위 트리 (Rank Tree) 데이터 구조

08 Dec 2023

javascript

순위 트리는 데이터 구조 중 일반적으로 우선순위 큐 (priority queue)를 구현하는 데 사용되는 자료 구조입니다. 이 구조는 삽입 및 삭제 시간복잡도 O(log n)을 제공하여 원소를 우선순위에 따라 유지하는 데 유용합니다.

순위 트리의 구조

순위 트리는 일반적으로 이진 힙 (binary heap)으로 구현됩니다. 힙은 부모 노드가 자식 노드보다 작은 (또는 큰) 값을 가지는 조건을 충족하는 이진 트리입니다. 최소 힙은 부모 노드가 항상 자식 노드보다 작은 값을 가지며, 최대 힙은 그 반대입니다. 이 특성을 활용하여 순위 트리는 각 원소에 우선순위를 부여하고, 삽입 및 삭제 연산 시에 우선순위에 따라 노드를 재정렬합니다.

아래는 JavaScript를 사용하여 최소 힙을 구현하는 간단한 예제 코드입니다.

class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp(this.heap.length - 1);
  }

  heapifyUp(index) {
    let parent = Math.floor((index - 1) / 2);
    if (parent >= 0 && this.heap[parent] > this.heap[index]) {
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
      this.heapifyUp(parent);
    }
  }

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }
    if (this.heap.length === 1) {
      return this.heap.pop();
    }
    const minValue = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.heapifyDown(0);
    return minValue;
  }

  heapifyDown(index) {
    let left = 2 * index + 1;
    let right = 2 * index + 2;
    let smallest = index;
    if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
      smallest = left;
    }
    if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
      smallest = right;
    }
    if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      this.heapifyDown(smallest);
    }
  }
}

위 코드는 최소 힙을 구현한 것으로, 순위 트리의 핵심 구조와 동작 방식을 보여줍니다.

결론

순위 트리는 우선순위 큐를 구현하는 데 유용한 데이터 구조로, 힙을 기반으로 구현됩니다. 이를 통해 데이터를 우선순위에 따라 관리하고 필요에 따라 삽입 및 삭제 연산을 수행할 수 있습니다.

순위 트리의 구조

결론

참고 자료