JavaScriptアルゴリズム二分探索木のサンプルコード-jsチュートリアル-php.cn

JavaScriptアルゴリズム二分探索木のサンプルコード

韦小宝

リリース： 2018-01-23 11:12:41

オリジナル

1133 人が閲覧しました

この記事では主に javascript アルゴリズムの二分探索木のサンプルコードを紹介します。JavaScript に興味がある友人は、この記事を参照してください

二分木とは何ですか

二分木とは、ツリーの各ノードが最大 2 つの子ノードしか持てないことを意味します

二分探索木とは何ですか

二分木に基づいて、追加の条件があります。 value を挿入します。挿入された値が現在のノードより小さい場合は、その値を左のノードに挿入します。そうでない場合は、挿入プロセス中に左のノードまたは右のノードがすでに存在する場合は、右のノードに挿入します。新しいノードが見つかるまで、上記のルールが適用されます。

二分探索木の特徴

その独特なデータ構造により、二分探索木の時間計算量は追加、削除、検索のいずれであっても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;
  }
 }
}

ログイン後にコピー

を構築します。 root は現在のオブジェクトのツリーです。

二分探索木への新規追加

二分探索木の左側のサブツリーはノードより小さく、右側のサブツリーの他のノードは大きいという特性により、新しいアルゴリズムを書くのが簡単です二分探索ツリーについては、次のようになります。

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 の内容は毎回直接変更されます。

二分探索ツリーの走査

二分探索ツリーは、前順、中順、後順の 3 つの走査方法に分かれています。

rreee

上記は順番通りの走査です。

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

11から始まり、スタックに対して{1}を実行し、次に7を入力し、次にスタックに対して{1}を実行し、次に5に進み、{1を実行しますこのとき、ノード 3 の左側の子ノードが null であることがわかり、実行が開始されます。ノード 3 の環境が表示されます。{2}、{3} を実行し、3 の正しい子ノードを見つけます。ノード 3 の再帰実行が完了すると、ノード 5 が表示され、{2} になります。 {3} が実行され、7 がポップアップされ、{2}{3} がスタックにプッシュされます。{3} が実行されると、ノード 7 に正しいノードがあることがわかり、{1} の実行を続けます。ノード 8 に移動し、次に {1} を実行します。8 には左側の子ノードがありません。{1} が実行された後、{2}{3} が実行されます。

preorder と inorder の違いは、最初にノード自体にアクセスすること、つまりコードの実行順序が 2 1 3 であることです。

同じことがポストオーダーにも当てはまり、実行順序は 1 3 2 です

フロント、ミドル、ポストオーダーに関係なく、左のノードが常に最初に再帰されることを見つけるのは難しくありません。左側のノードが走査され、スタックがポップされ、すべてのノードが走査されます。それらの唯一の違いは、ノード自体にアクセスするタイミングです。

二分探索木探索

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

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

ログイン後にコピー

二分探索木の削除

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

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

存在する場合は、削除されたノードを右側のサブツリーの最小のノードと置き換えます

一般に、この単純な二分探索木の学習を通じて、これまでの再帰についての理解は単純な理論的概念に過ぎませんでしたが、この徹底的な実践により、再帰についての理解がさらに深まりました。

これは数学の勉強を思い出させます。知識ポイントを習得するための満点が 10 点である場合、実際にそれを習得するまでは、覚えておくのが簡単です。公式は非常に単純で、数文といくつかの原則だけであるため、公式は 2 点で済みますが、理論を真に実践し、さまざまな実践を経ることによってのみ、直面する問題は常に変化します。その謎を理解してください。