Javascriptのツリーにキーを挿入する

新しく作成されたバイナリツリーに最初に挿入すると、ルートにノードが作成されます。左の子が親よりも小さく、右の子が親よりも大きいという二分探索木のプロパティに従って、さらに挿入が挿入されます。

このアルゴリズムをコードで実装する方法を見てみましょう-

例

insertIter(data) {
   let node = new this.Node(data);

   // Check if the tree is empty
   if (this.root === null) {
      // Insert as the first element
      this.root = node; return;
   }

   let currNode = this.root;
   while (true) {
      if (data < currNode.data) {
         // Set the value here as we've reached a leaf node
         if (currNode.left === null) {
            currNode.left = node;
            break;
         } else {
            currNode = currNode.left;
         }
      } else {
         // Set the value here as we've reached a leaf node
         if (currNode.right === null) {
            currNode.right = node;
            break;
         } else {
            currNode = currNode.right;
         }
      }
   }
}

この関数がどのように機能するかを理解しましょう。最初に、ルートがnullであるかどうかを確認します。つまり、ツリーが空であるかどうかを確認します。そうであれば、新しいノードをルートとして割り当て、完了です。そうでない場合は、currNode変数を作成し、それをルートにポイントします。次に、データがcurrNodeより小さいかどうかをチェックし、小さい場合は、その左の子がnullであるかどうかをチェックします。その場合は、ここにデータを保持して終了します。それ以外の場合は、葉に到達するまで反復を続け、最終的にデータをそこに配置します。

この関数は、-

例

let BST = new BinarySearchTree();
BST.insertIter(10);
BST.insertIter(15);
BST.insertIter(5);
BST.insertIter(50);
BST.insertIter(3);
BST.insertIter(7);
BST.insertIter(12);

この関数を再帰的にすることもできます。ツリーは本質的に再帰的な構造であり、この再帰的なプロパティをかなり簡単に利用できます。挿入の再帰バージョンを見てみましょう-

例

insertRec(data) {
   let node = new this.Node(data);

   // Check if the tree is empty
   if (this.root === null) {
      // Insert as the first element
      this.root = node;
   } else {
      insertRecHelper(this.root, node);
   }
}

再帰できるヘルパー関数を作成する必要がありますが、それをクラスのプロパティとして公開したくないため、この関数はクラス定義から外れます。

例

function insertRecHelper(root, node) {
   if (node.data < root.data) {
      // Set the value here as we've reached a leaf node

      if (root.left === null) {
         root.left = node;
      } else {
         // Recursively call this function with the left subtree
            insertRecHelper(root.left, node);
      }
   } else {
      // Set the value here as we've reached a leaf node
      if (root.right === null) {
         root.right = node;
      } else {
         // Recursively call this function with the right subtree
         insertRecHelper(root.right, node);
      }
   }
}

-

例

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);