একটি জাভাস্ক্রিপ্ট AVL গাছে একটি নোড ঢোকানো

আমরা শিখতে পারি কিভাবে আমরা একটি AVL গাছে একটি নোড সন্নিবেশ করতে পারি। AVL গাছে সন্নিবেশগুলি BST-এর মতোই, যখনই আমরা গাছ থেকে নিচে নামব তখন সন্নিবেশের সময় আমাদের কেবল একটি অতিরিক্ত পদক্ষেপ করতে হবে যাকে ব্যালেন্স ট্রি বলা হয়৷

এর জন্য ব্যালেন্স ফ্যাক্টর গণনা করা প্রয়োজন যা আমরা আগে দেখেছি। এবং কনফিগারেশন অনুযায়ী, আমাদের উপযুক্ত ঘূর্ণন পদ্ধতি কল করতে হবে। উপরের ব্যাখ্যার সাহায্যে এগুলি বেশ স্বজ্ঞাত।

আমরা আবার একটি ক্লাস পদ্ধতি এবং রিকার্সিভ কলের জন্য একটি সহায়ক ফাংশন তৈরি করি -

উদাহরণ

insert(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 {
      insertHelper(this, this.root, node);
   }
}

হেল্পার পদ্ধতি

function insertHelper(self, root, node) {
   if (root === null) {
      root = node;
   } else if (node.data < root.data) {
      // Go left!
      root.left = insertHelper(self, root.left, node);
      // Check for balance factor and perform appropriate rotation
      if (root.left !== null && self.getBalanceFactor(root) > 1) {
         if (node.data > root.left.data) {
            root = rotationLL(root);
         } else {
            root = rotationLR(root);
         }
      }
   } else if (node.data > root.data) {
      // Go Right! root.
      right = insertHelper(self, root.right, node);
      // Check for balance factor and perform appropriate rotation
      if (root.right !== null && self.getBalanceFactor(root) < -1) {
         if (node.data > root.right.data) {
            root = rotationRR(root);
         } else {
            root = rotationRL(root);
         }
      }
   }
   return root;
}

আপনি −

উদাহরণ

let AVL = new AVLTree();

AVL.insert(10);
AVL.insert(15);
AVL.insert(5);
AVL.insert(50);
AVL.insert(3);
AVL.insert(7);
AVL.insert(12);

AVL.inOrder();

আউটপুট

এটি আউটপুট দেবে −

3
5
7
10
12
15
50