JavaScript의 이진 트리(이진 힙) 소개(코드 예제)

이 글은 JavaScript의 바이너리 트리(바이너리 힙)에 대한 소개(코드 예제)를 제공합니다. 이는 특정 참조 가치가 있으므로 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

이진 트리

이진 트리(Binary Tree)는 트리 구조의 특징은 각 노드가 최대 2개의 가지 노드만 갖는다는 것입니다. 이진 트리는 일반적으로 루트 노드, 가지 노드, 리프 노드로 구성됩니다. 각 분기 노드를 종종 하위 트리라고 합니다.

• 루트 노드: 이진 트리의 최상위 노드

• 분기 노드: 루트 노드를 제외하고 리프 노드가 있음

• 리프 노드: 자신만 제외하고 다른 자식 노드 없음

자주 사용되는 용어

이진 트리에서는 이를 설명하기 위해 부모 노드와 자식 노드를 사용하는 경우가 많습니다. 예를 들어 그림의 2는 6과 3의 부모 노드이고, 반대로 6과 3은 자식 노드입니다. 2

3개의 이진 트리 속성

1. 이진 트리의 i번째 수준에는 최대 2^i-1개의 노드

• i=1이 있습니다. =1, 단 하나의 루트 노드가 있습니다. 2^(i-1) = 2^0 = 1

깊이 k인 이진 트리에는 최대 2^k-1개의 노드가 있습니다

• i= 2, 2^k-1 = 2^2 - 1 = 3개 노드

임의의 이진 트리 T에 대해 요약 포인트 개수가 n0이고 차수가 2인 노드 개수(하위 트리 개수는 2)인 경우 n2이면 n0=n2+1

트리와 이진 트리의 세 가지 주요 차이점

• 트리의 노드 수는 최소 1개이지만 이진 트리의 노드 수는 0이 될 수 있습니다

• 트리의 노드 최대 차수(노드 수)는 제한이 없지만 이진 트리의 노드 최대 차수는 2

• 트리 이진 트리의 노드는 왼쪽으로 나누어지지 않습니다. 그리고 오른쪽, 이진 트리의 노드는 왼쪽과 오른쪽으로 나뉘어져 있는데

이진 트리 분류

이진 트리는 완전 이진 트리(완전 이진 트리)와 완전 이진 트리(완전 이진 트리)

• 로 구분됩니다.

  완전 이진 트리: 1 깊이 k이고 2^k - 1개의 노드를 갖는 이진 트리를 완전 이진 트리라고 합니다

• 완전 이진 트리: 완전 이진 트리는 마지막 레이어의 왼쪽이 가득 차 있음을 의미합니다. 오른쪽이 가득 차 있을 수도 있고 아닐 수도 있고 나머지 레이어도 가득 차게 됩니다. 이진 트리를 완전 이진 트리라고 합니다(완전 이진 트리도 완전 이진 트리입니다)

이진의 배열 표현 tree

배열을 사용하여 이진 트리의 구조를 루트 노드부터 시작하여 위에서 위로 배열합니다. 그런 다음 아래 그림과 같이 왼쪽에서 오른쪽으로 완전한 이진 트리를 채웁니다.

위 그림을 통해 배열로 표현된 완전한 이진 트리가 다음 속성을 갖는다는 것을 분석할 수 있습니다.

left = index * 2 + 1, 예: 루트 노드의 첨자는 0이고, 왼쪽 노드의 값은 첨자 배열[0*2+1]=1

• right = index * 2 + 2입니다. 예: root 노드의 첨자가 0이면 오른쪽 노드의 값 아래 첨자 배열[0*2+2]=2

• ordinal>=floor(N/2)은 모든 리프 노드입니다. 예: Floor(9/ 2) = 4, 그런 다음 값은 다음에서 시작합니다. 첨자 4는 모두 리프 노드입니다

• 바이너리 힙

바이너리 힙은 완전한 이진 트리로 표현되고 그 구조는 배열로 표현되지만 이진 힙은 다음 속성을 충족해야 합니다.

The 바이너리 힙의 상위 노드의 키 값은 항상 모든 하위 노드의 키 값보다 크거나 같습니다(작거나 같음)

• 상위 노드의 키 값이 ( 이하) 각 하위 노드의 키 값을
max 힙(최소 힙)

• 

  이라고 합니다. 위 그림에서 볼 수 있듯이:

왼쪽 그림: 부모 노드는 항상 자식 노드보다 크거나 같으므로 바이너리 힙의 속성인

• 오른쪽 그림: 분기 노드 7, 2와 12의 부모 노드 , 해당 속성(하위 노드보다 크거나 같음)을 충족하지 않습니다.

• 바이너리 힙의 주요 작업

insert: 노드 삽입

• delete: 노드 삭제

• max-hepify: 분기 노드 힙 속성 조정

• rebuildHeap: 전체 다시 빌드 바이너리 힙

• sort: Sort

• 바이너리 힙 초기화

위의 간략한 소개에서 바이너리 힙의 초기화가 매우 간단하다는 것을 알 수 있습니다. 이는 배열입니다

배열 구조 초기화

• 배열 길이 저장

    class Heap{
        constructor(arr){
            this.data = [...arr];
            this.size = this.data.length;
        }
    }

max-heapify 최대 힙 연산

max-heapify는 최대 힙 속성을 충족하지 못하는 각 분기 노드를 조정하는 연산입니다.

위 그림과 같이:

1. 분기 노드 2 조정(분기 노드 2는 최대 힙의 속성을 충족하지 않음)

• 기본 분기 노드는 최대값입니다

2를 Branch 비교로 변경하고 2, 12, 5에서 최대값을 찾은 다음 2와 위치를 교환합니다.

• 위에서 언급한 바이너리 힙 속성에 따라 의 왼쪽 노드와 오른쪽 노드를 가져옵니다. Branch node 2 각각

• 3개의 노드를 비교하여 최대값의 첨자 max를 구합니다

• 노드 자체가 최대값이면 연산을 중지합니다

• max 노드를 상위 노드로 교환

2, 4, 7 중 최대값을 찾아 2

• Recursion

    maxHeapify(i) {
        let max = i;
        
        if(i >= this.size){
            return;
        }
        // 当前序号的左节点
        const l = i * 2 + 1;
        // 当前需要的右节点
        const r = i * 2 + 2;
        
        // 求当前节点与其左右节点三者中的最大值
        if(l  this.data[max]){
            max = l;
        }
        if(r  this.data[max]){
            max = r;
        }
        
        // 最终max节点是其本身,则已经满足最大堆性质，停止操作
        if(max === i) {
            return;
        }
        
        // 父节点与最大值节点做交换
        const t = this.data[i];
        this.data[i] = this.data[max];
        this.data[max] = t;
        
        // 递归向下继续执行
        return this.maxHeapify(max);
    }

Reconstruct the heap

에서 2단계의 작업을 반복합니다. 초기화된 힙은 배열로 표현되는데, 이때 최대 힙 또는 최소 힙의 속성을 만족시키기 위해서는 전체 힙을 원하는 대로 구축해야 할 수도 있습니다.
위에서 max-heapify 작업을 수행했으며, max-heapify는 특정 분기 노드만 조정합니다. 전체 힙을 최대 힙으로 구축하려면 아래와 같이 모든 분기 노드에서 max-heapify 작업을 수행해야 합니다. 4개의 분기 노드 12, 3, 2, 15에서 순서대로 max-hepify 작업을 수행해야 합니다. 시퀀스 번호 >=Math.floor(n/2)이므로 Math.floor(n/2)보다 작은 시퀀스 번호는 조정해야 하는 노드입니다.

예를 들어 길에 보이는 배열은 [15,2,3,12,5,2,8,4,7] => Math.floor(9/2)=4 => 인덱스는 4보다 작음 15, 2, 3, 12(조정이 필요한 노드)이고, 5, 2, 8, 4, 7은 리프 노드입니다.

• 발견된 모든 노드에 대해 maxHeapify 작업을 수행합니다.

    rebuildHeap(){
        // 叶子节点
        const L = Math.floor(this.size / 2);
        for(let i = L - 1; i>=0; i--){
            this,maxHeapify(i);
        }
    }

최대 힙 정렬

위 그림과 같이 최대 힙 정렬:

헤드 및 테일 위치 교환

will 힙에서 마지막 요소를 가져옵니다. 이는 힙의 크기인 1

그런 다음 힙의 루트 노드에서 max-heapify 작업이 수행됩니다.

• 위를 반복합니다. 크기가 0이 될 때까지 세 단계(이 경계 조건은 max-heapify 함수에서 이미 완료했습니다)

•     sort() {
          for(let i = this.size - 1; i > 0; i--){
              swap(this.data, 0, i);
              this.size--;
              this.maxHeapify(0);
          }
      }

  삽입 및 삭제
• 이 삽입 및 삭제는 상대적으로 간단합니다. 배열을 삽입하고 삭제하는 것입니다

• 끝까지 삽입

힙 길이 +1

삽입 후에도 여전히 최대 힙인지 확인

• 그렇지 않으면 힙을 재구성

•   insert(key) {
      this.data[this.size] = key;
      this.size++
      if (this.isHeap()) {
        return;
      }
      this.rebuildHeap();
    }

• 배열의 요소 삭제

• 힙 길이 -1

힙인지 확인

• 그렇지 않으면 힙을 재구성하세요

•   delete(index) {
      if (index >= this.size) {
        return;
      }
      this.data.splice(index, 1);
      this.size--;
      if (this.isHeap()) {
        return;
      }
      this.rebuildHeap();
    }

  완전한 코드

/**
 * 最大堆
 */

function left(i) {
  return i * 2 + 1;
}

function right(i) {
  return i * 2 + 2;
}

function swap(A, i, j) {
  const t = A[i];
  A[i] = A[j];
  A[j] = t;
}

class Heap {
  constructor(arr) {
    this.data = [...arr];
    this.size = this.data.length;
  }

  /**
   * 重构堆
   */
  rebuildHeap() {
    const L = Math.floor(this.size / 2);
    for (let i = L - 1; i >= 0; i--) {
      this.maxHeapify(i);
    }
  }

  isHeap() {
    const L = Math.floor(this.size / 2);
    for (let i = L - 1; i >= 0; i++) {
      const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
      const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;

      const max = Math.max(this.data[i], l, r);

      if (max !== this.data[i]) {
        return false;
      }
      return true;
    }
  }

  sort() {
    for (let i = this.size - 1; i > 0; i--) {
      swap(this.data, 0, i);
      this.size--;
      this.maxHeapify(0);
    }
  }

  insert(key) {
    this.data[this.size++] = key;
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

  delete(index) {
    if (index >= this.size) {
      return;
    }
    this.data.splice(index, 1);
    this.size--;
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

  /**
   * 堆的其他地方都满足性质
   * 唯独跟节点，重构堆性质
   * @param {*} i
   */
  maxHeapify(i) {
    let max = i;

    if (i >= this.size) {
      return;
    }

    // 求左右节点中较大的序号
    const l = left(i);
    const r = right(i);
    if (l  this.data[max]) {
      max = l;
    }

    if (r  this.data[max]) {
      max = r;
    }

    // 如果当前节点最大，已经是最大堆
    if (max === i) {
      return;
    }

    swap(this.data, i, max);

    // 递归向下继续执行
    return this.maxHeapify(max);
  }
}

module.exports = Heap;

요약

이것이 힙의 끝입니다 . 이진 트리는 상대적으로 간단하며 정렬 및 우선 순위 대기열 등에 자주 사용됩니다. 힙의 핵심은 max-heapify 작업과 힙의 세 가지 속성입니다.

위 내용은 JavaScript의 이진 트리(이진 힙) 소개(코드 예제)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!