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

新しいノードインスタンスを作成するために、このクラスをいくつかのデータを使用してこのように呼び出すことができます-

const newNode = new Node(23);

これにより、データセットが23で、左右の参照が両方ともnullである新しいノードインスタンスが作成されます。

ステップ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);