JS 이진 검색 트리 사용에 대한 자세한 설명-JS 튜토리얼-php.cn

JS 이진 검색 트리 사용에 대한 자세한 설명

php中世界最好的语言

풀어 주다： 2018-04-18 09:36:37

원래의

1316명이 탐색했습니다.

이번에는 JS 바이너리 검색트리 사용에 대해 자세히 설명하고, JS 바이너리 검색 트리 사용 시 주의사항은 무엇인지 살펴보겠습니다.

이진 트리란 무엇입니까

이진 트리는 트리의 각 노드가 최대 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;
  }
 }
}

로그인 후 복사

여기서 this.root는 현재

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의 값을 변경할 수 있는 이유는

JavaScript 함수가 값으로 전달되고, 매개변수가 기본이 아닌 유형인 경우, 여기의 객체로서 그 객체의 값은 메모리이므로 this.root의 내용은 매번 직접 변경됩니다.

이진 검색 트리 순회

이진 검색 트리는 선순(preorder), 중순(inorder), 후순(postorder)의 세 가지 순회 방법으로 나뉩니다.

rreee

위의 순서는 순회입니다.

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

11부터 시작하여 스택에 대해 {1}을 실행한 다음 7로 이동하고 스택에 {1}을 실행한 다음 5로 이동하고 스택에 {1}을 실행한 다음 3으로 이동하여 {1을 실행합니다. }를 스택에 추가하는데 이때 노드 3의 왼쪽 자식 노드가 null인 것으로 확인되어 스택에서 튀어나오기 시작합니다. 이때 노드 3의 실행 환경이 팝업되어 {2}를 실행합니다. {3}, 3의 오른쪽 하위 노드도 null이고 {3}의 재귀 실행이 완료된 것을 확인한 다음 노드 5를 팝업하고 {2}{3}을 실행한 다음 노드 7을 팝업하고 실행합니다. {2}{3}을 스택에 추가하고 {3}을 실행할 때 노드 7에 올바른 노드가 있는 것으로 확인되었으므로 {1}을 계속 실행하고 노드 8에 대해 {1}을 다시 실행합니다. 8에는 왼쪽 자식이 없습니다. 노드, {1}이 실행되고, {2}{3}이 실행되는 식입니다.

preorder와 midorder의 차이점은 노드 자체를 먼저 방문한다는 것, 즉 코드의 실행 순서가 2 1 3이라는 점입니다.

사후 주문에도 동일하게 적용되며 실행 순서는 1 3 2

입니다. 순서가 이전, 도중, 이후에 관계없이 항상 왼쪽 노드가 먼저 재귀된다는 것을 찾는 것은 어렵지 않습니다. 왼쪽 노드를 순회하면 스택이 팝되고 모든 노드가 순회됩니다. 이들 사이의 유일한 차이점은 노드 자체에 액세스하는 타이밍입니다.

이진 검색 트리 검색

검색은 매우 간단합니다. 왼쪽 자식 노드가 노드보다 작고 오른쪽 자식 노드가 노드보다 크다는 원칙에 따라 루프 판단을 내리면 됩니다.

rreee

이진 검색 트리 삭제

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

먼저 노드에 왼쪽 하위 트리가 있는지 확인합니다. 왼쪽 하위 트리가 없으면 삭제된 노드를 오른쪽 하위 트리의 루트 노드로 직접 바꿉니다. 있는 경우 삭제된 노드를 오른쪽 하위 트리의 가장 작은 노드로 바꿉니다.

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);
  }
 }
}

로그인 후 복사

总结

总的来说，通过这次简单的二叉搜索树的学习，让我重新认识了递归，以前对于递归的理解只是一些简单的理论概念，这次深入实践让我对递归的理解又加深了许多。

这让我想到了数学的学习，数学的理论公式是很容易记住掌握的，如果说对一个知识点的掌握满分是十分，那么直到真正去实践它之前，只看公式的掌握只能是2分，因为公式很简单，就几句话几个原则，但是遇到的问题是千变万化的，只有真正将理论付诸实践，经过各种实践的打磨蹂躏，才能真正理解它其中的奥秘。

相信看了本文案例你已经掌握了方法，更多精彩请关注php中文网其它相关文章！