जावास्क्रिप्ट में बाइनरी सर्च ट्री लागू करना

वृक्ष डेटा संरचना

एक पेड़ कुछ किनारों से जुड़े नोड्स का एक संग्रह है। परंपरागत रूप से, पेड़ के प्रत्येक नोड में कुछ डेटा और उसके बच्चों के संदर्भ होते हैं।

बाइनरी सर्च ट्री

बाइनरी सर्च ट्री एक बाइनरी ट्री है जिसमें कम मान वाले नोड्स को बाईं ओर संग्रहीत किया जाता है जबकि उच्च मान वाले नोड्स को दाईं ओर संग्रहीत किया जाता है।

उदाहरण के लिए, एक वैध बीएसटी का दृश्य प्रतिनिधित्व है -

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

आइए अब अपने स्वयं के बाइनरी सर्च ट्री को जावास्क्रिप्ट भाषा में लागू करें।

चरण 1:नोड क्लास

यह वर्ग बीएसटी में विभिन्न बिंदुओं पर मौजूद एकल नोड का प्रतिनिधित्व करेगा। एक बीएसटी कुछ और नहीं बल्कि ऊपर वर्णित नियमों के अनुसार रखे गए डेटा और चाइल्ड संदर्भों को संग्रहीत करने वाले नोड्स का एक संग्रह है।

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

एक नया नोड उदाहरण बनाने के लिए, हम इस वर्ग को कुछ डेटा के साथ इस तरह से कॉल कर सकते हैं -

const newNode = new Node(23);

यह 23 पर सेट डेटा के साथ एक नया नोड इंस्टेंस बनाएगा और बाएं और दाएं संदर्भ दोनों शून्य होंगे।

चरण 2:बाइनरी सर्च ट्री क्लास:

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

यह बाइनरी सर्च ट्री क्लास बनाएगा जिसे हम एट्री इंस्टेंस बनाने के लिए नए कीवर्ड के साथ कॉल कर सकते हैं।

अब जैसा कि हमने मूल सामग्री के साथ किया है, चलो सही जगह पर एक नया नोड डालने के लिए आगे बढ़ते हैं (परिभाषा में वर्णित बीएसटी के नियमों के अनुसार)।

चरण 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);