JavaScript での二分探索ツリーの実装

#ツリー データ構造

ツリーは、いくつかのエッジで接続されたノードの集合です。慣例により、ツリーの各ノードは 一部のデータとその子ノードへの参照を保存します。

二分探索木

二分探索木とは、値が小さいノードが左側に、値が小さいノードが左側に格納される二分木です。より高い値が右側に格納されます。

たとえば、有効な BST の視覚的表現は -

     25
   /   \
  20   36
 / \   / \
10 22 30 40

です。

次に、JavaScript 言語で独自の二分探索ツリーを実装してみましょう。

ステップ 1: ノード クラス

このクラスは、BST の各ポイントに存在する単一のノードを表します。 BST なし むしろ、これはルールに従って配置されたデータとサブ参照を格納するノードのコレクションです。 上記のように。

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

新しい Node インスタンスを作成するには、いくつかのデータを指定してこのクラスを呼び出すことができます -

const newNode = new Node(23);

これにより、データが 23 に設定され、左右の参照が両方とも null の新しい Node インスタンスが作成されます。

ステップ 2: 二分検索ツリー クラス:

class BinarySearchTree{
   constructor(){
      this.root = null;
   };
};

これにより、二分検索ツリー クラスが作成されます。新しいキーワードを使用してこのクラスを呼び出すと、 ツリーインスタンス。

基本的な作業は完了したので、次に進んで、(定義で説明されている BST ルールに従って) 正しい位置に新しいノードを挿入しましょう。

ステップ 3: BST にノードを挿入します

class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};

例

完全なバイナリ検索ツリー コード:

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);

以上がJavaScript での二分探索ツリーの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。