자바스크립트 알고리즘 이진 검색 트리의 샘플 코드-JS 튜토리얼-php.cn

자바스크립트 알고리즘 이진 검색 트리의 샘플 코드

韦小宝

풀어 주다： 2018-01-23 11:12:41

원래의

1125명이 탐색했습니다.

이 글에서는 자바스크립트 학습을 위한 확실한 참고자료와 가치가 있는 javascript 알고리즘의 이진 검색 트리 샘플 코드를 주로 소개합니다. 자바스크립트에 관심 있는 친구들은 이 글을 참고해보세요.

이진 트리란 무엇인가요?

이진 트리는 트리의 각 노드가 최대 2개의 자식 노드만 가질 수 있다는 것을 의미합니다.

이진 검색 트리란 무엇입니까

이진 트리를 기반으로 추가 조건이 있습니다. 즉, 이진 트리가 값을 삽입합니다. 삽입된 값이 현재 노드보다 작으면 왼쪽 노드에 삽입하고, 그렇지 않으면 삽입 프로세스 중에 왼쪽 노드 또는 오른쪽 노드가 이미 존재하는 경우 오른쪽 노드에 삽입한 다음 다음에 따라 계속 비교합니다. 새 노드를 만날 때까지 위의 규칙을 따릅니다.

이진 검색 트리의 특성

독특한 데이터 구조로 인해 이진 검색 트리의 시간 복잡도는 추가, 삭제 또는 검색 여부에 관계없이 O(h)입니다. h는 이진 트리의 높이입니다. 따라서 이진 트리는 최대한 짧아야 합니다. 즉, 왼쪽 노드와 오른쪽 노드의 균형이 최대한 맞아야 합니다.

이진 검색 트리 구축

이진 검색 트리를 구축하려면 먼저 이진 트리의 노드 클래스를 구축해야 합니다. 이진 트리의 특성을 보면 각 노드 클래스에는 왼쪽 노드, 오른쪽 노드와 값 자체가 있으므로 노드 클래스는 다음과 같습니다.

class Node {
 constructor(key) {
  this.key = key;
  this.left = null;
  this.right = null;
 }
}

로그인 후 복사

그런 다음 이진 검색 트리를 구성합니다

class Tree{
 constructor(param = null) {
  if (param) {
   this.root = new Node(param);
  } else {
   this.root = null;
  }
 }
}

로그인 후 복사

여기서. 루트는 현재 object의 트리입니다.

이진 검색 트리에 대한 새로운 추가

이진 검색 트리의 왼쪽 하위 트리가 노드보다 작고 오른쪽 하위 트리의 다른 노드가 더 큰 특성으로 인해 새로운 알고리즘을 작성하기 쉽습니다. 이진 검색 트리의 경우 다음과 같습니다.

insert(key) {
 if (this.root === null) {
  this.root = new Node(key);
 } else {
  this._insertNode(this.root, key);
 }
}
_insertNode(node, key) {
 if (key < node.key) {
  if (node.left === null) {
   node.left = new Node(key);{1}
  } else {
   this._insertNode(node.left, key);{2}
  }
 } else if (key > node.key) {
  if (node.right === null) {
   node.right = new Node(key);{3}
  } else {
   this._insertNode(node.right, key);{4}
  }
 }
}

로그인 후 복사

위 코드는 먼저 새 키와 현재 노드의 키 크기를 결정합니다. 크기가 작으면 null 왼쪽 하위 노드를 찾을 때까지 왼쪽 하위 노드를 재귀적으로 탐색합니다. 현재 노드보다 크면 동일한 원칙이 적용됩니다. 위의 코드 {1}{2}{3}{4}가 this.root의 값을 변경할 수 있는 이유는 자바스크립트 함수가 값으로 전달되고, 매개변수가 기본이 아닌 유형(예: 여기서 객체의 값은 메모리이므로 this.root의 내용은 매번 직접 변경됩니다.

이진 검색 트리 순회

이진 검색 트리는 사전 주문, 중간 주문, 사후 주문의 세 가지 순회 방법으로 나뉩니다.

inOrderTraverse(callback) {
 this._inOrderTraverse(this.root, callback);
}
_inOrderTraverse(node, callback) {
 if (node) {
  this._inOrderTraverse(node.left, callback);
  callback(node.key);
  this._inOrderTraverse(node.right, callback);
 }
}

로그인 후 복사

위는 순서대로 순회하는 것입니다.

여기서 이해해야 할 것은 재귀입니다. 아시다시피 함수 실행은 데이터 구조, 즉 스택으로 추상화될 수 있습니다. 함수 실행을 위해 함수 실행을 저장하기 위해 스택이 유지됩니다. 함수가 반복될 때마다 현재 실행 환경을 스택에 푸시하고 실행 위치를 기록합니다. 위 코드를 예로 들면 다음과 같은 데이터가 있습니다

11부터 시작하여 스택에 {1}을 실행한 다음 7을 입력하고 스택에 {1}을 실행한 다음 5로 이동하여 {1을 실행합니다. }를 스택에 추가한 후 3. {1}을 실행하여 스택에 푸시합니다. 이때 노드 3의 왼쪽 자식 노드가 null인 것으로 확인되어 이때 실행이 시작됩니다. 노드 3의 환경이 팝업됩니다. {2}, {3}을 실행하고 3의 올바른 하위 노드를 찾습니다. 노드도 null입니다. 그런 다음 노드 5가 팝업되고 {2. {3}이 실행되고 7이 팝업되고 {2}{3}이 스택에 푸시됩니다. {3}이 실행되면 노드 7에 오른쪽 노드가 있음을 확인하므로 계속해서 {1}을 실행합니다. 노드 8로 이동한 다음 {1}을 실행합니다. 8에는 왼쪽 하위 노드가 없습니다. {1}이 실행된 후 {2}{3}이 실행됩니다.

preorder와 inorder의 차이점은 노드 자체에 먼저 액세스한다는 것입니다. 즉, 코드의 실행 순서는 2 1 3입니다.

Post-order의 경우에도 마찬가지이며 실행 순서는 1 3 2입니다. 왼쪽 노드가 순회되고, 스택이 팝되고, 모든 노드가 순회됩니다. 이들 사이의 유일한 차이점은 노드 자체에 액세스하는 타이밍입니다.

이진 검색 트리 검색

검색은 매우 간단합니다. 왼쪽 자식 노드가 노드보다 작고 오른쪽 자식 노드가 노드보다 크다는 원리를 기반으로 루프 판단을 하면 됩니다.

search(value) {
 if (this.root) {
  if (value === this.root.key) {
   return true;
  } else {
   return this._searchNode(value, this.root);
  }
 }
 throw new Error(&#39;this.root 不存在&#39;);
}
_searchNode(value, node) {
 if (!node) {
  return false;
 }
 if (value === node.key) {
  return true;
 }
 if (value > node.key) {
  return this._searchNode(value, node.right);
 } else if (value < node.key) {
  return this._searchNode(value, node.left);
 }
}

로그인 후 복사

이진 검색 트리 삭제

삭제는 더 복잡하며 상황에 따라 판단해야 합니다.

먼저 노드에 왼쪽 하위 트리가 있는지 확인하고 왼쪽 하위 트리가 없으면 루트를 직접 제거합니다. 오른쪽 하위 트리 노드는 삭제된 노드를 대체합니다.

삭제된 노드가 있으면 오른쪽 하위 트리의 가장 작은 노드로 대체합니다.

remove(key) {
 this._removeNode(this.root, key);
}
_removeNode(node, value) {
 if (!node) {
  return null;
 }
 if (value > node.key) {
  node.right = this._removeNode(node.right, value);
 } else if (value < node.key) {
  node.left = this._removeNode(node.left, value);
 } else {
  // 如果没有左子树，那么将右子树根节点作为替换节点
  if (!node.left) {
   return node.right;
   // 如果存在左子树，那么取右子树最小节点作为替换节点
  } else if (node.left) {
   return this._minNode(node.right);
  }
 }
}

로그인 후 복사

Summary

일반적으로 이 간단한 이진 검색 트리 학습을 통해, 재귀에 대한 나의 이전 이해는 단순한 이론적 개념에 불과했습니다. 이 심층적인 연습을 통해 재귀에 대한 이해가 많이 깊어졌습니다.

수학 공부가 생각나네요. 수학의 이론적 공식은 기억하기 쉽고 마스터하기 쉽습니다. 지식 포인트를 마스터하는 데 필요한 전체 점수가 10점이라면 실제로 연습하기 전까지는 마스터하는 정도만 보면 됩니다. 공식은 단지 몇 개의 문장과 몇 가지 원리로 매우 간단하기 때문에 2점이 될 수 있지만, 직면하는 문제는 이론을 진정으로 실천하고 다양한 실천을 거쳐야만 진정으로 변화할 수 있습니다. 그 신비를 이해하십시오.