JS二分探索木の使い方を詳しく解説

今回は、JS バイナリ search ツリーの使用方法について詳しく説明します。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 は現在の オブジェクト のツリーです。

二分探索木の新規追加

左側のサブツリーがノードより小さく、右側のサブツリーがノードより大きいという二分探索木の特性に基づいて、二分探索木の新しいアルゴリズムは次のように簡単に記述できます。 上記のコードは、まず、新しく追加されたキーのサイズと現在のノードのキーを決定し、それが現在のノードよりも大きい場合は、null の左の子ノードを見つけるまで再帰的に調べます。同じ原則が当てはまります。上記のコード {1}{2}{3}{4} が this.root の値を変更できる理由は、

関数が値によって渡され、パラメーターが非基本型である場合に、ここではオブジェクトとして、そのオブジェクトの値はメモリなので、this.rootの内容は毎回直接変更されます。

二分探索ツリーは、preorder、inorder、postorder の 3 つの走査方法に分類されます。

上記は順序どおりの走査です。

ここで理解すべきは再帰です。ご存知のとおり、関数の実行はデータ構造、つまりスタックに抽象化できます。関数の実行では、関数の実行を保存するためにスタックが維持されます。関数が再帰するたびに、現在の実行環境がスタックにプッシュされ、実行場所が記録されます。上記のコードを例にすると、次のようなデータがあります

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です

順序が前、中、後であっても、左のノードが常に最初に再帰され、左のノードが走査されると、スタックがポップされ、すべてのノードが走査されることを見つけるのは難しくありません。それらの唯一の違いは、ノード自体にアクセスするタイミングです。

探索は非常に簡単で、左の子ノードがそのノードより小さく、右の子ノードがそのノードより大きいという原則に基づいてループ判定するだけです。

二分探索木の

削除はより複雑であり、さまざまな状況に応じて判断する必要があります

まず、ノードに左側のサブツリーがあるかどうかを確認します。左側のサブツリーがない場合は、削除されたノードを右側のサブツリーのルート ノードに直接置き換えます。 存在する場合は、削除されたノードを右のサブツリーの最小のノードに置き換えます

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中文网其它相关文章！

推荐阅读：

react-native-fs插件使用案列详解

js实现字符限制中文汉字=两个字符

优化页面加载速度插件InstantClick

以上がJS二分探索木の使い方を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。