بائنری تلاش درخت حذف کرنے کا عمل


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے اکٹھا کرنا ایمیزون Qualcomm سیمسنگ
ثنائی تلاش درخت ثنائی درخت درخت

مسئلہ یہ بیان

مسئلہ "بائنری سرچ ٹری ڈیلیٹ آپریشن" ہمیں ڈیلیٹ آپریشن کو لاگو کرنے کے لئے کہتا ہے بائنری تلاش درخت. ڈیلیٹ فنکشن سے مراد کسی دیئے گئے کلید / ڈیٹا والے نوڈ کو ڈیلیٹ کرنے کی فعالیت ہوتی ہے۔

مثال کے طور پر

ان پٹ

بائنری تلاش درخت حذف کرنے کا عمل

حذف ہونے والا نوڈ = 5

آؤٹ پٹ

کے لئے نقطہ نظر بائنری تلاش درخت حذف کرنے کا عمل

لہذا جب ہم بائنری تلاش کے درخت سے نوڈ کو حذف کرنے کی بات کرتے ہیں۔ ایک بات نوٹ کرنے کی بات یہ ہے کہ جب بھی ہم نوڈ کو حذف کرتے ہیں تو ، بی ایس ٹی کی تمام خصوصیات کو مطمئن رکھنا چاہئے۔ اگر ہم داخلی نوڈ کو ہٹا رہے ہیں تو ، ہمیں اس بات کو یقینی بنانا ہوگا کہ نئی جڑ کے ساتھ ساتھ ذیلی درخت BST کی خصوصیات کو پورا کرے۔

اب ، ہمارے ساتھ نمٹنے کے لئے تین معاملات ہیں۔ یہ معاملات نوڈ کے بچوں کی تعداد پر مبنی ہیں۔ اور اس سوال کے جواب کے لئے کہ بچوں کی تعداد کی بنیاد پر نوڈس کی درجہ بندی کیوں کی جارہی ہے؟ لہذا ، سنگل بچے کے ساتھ سیسہ اور نوڈ سے نمٹنا آسان ہے۔ تو آئیے ان تینوں معاملات پر مختصرا discuss گفتگو کریں۔

  1. کوئی بچ withہ والا نوڈ (پتی)
  2. اکیلے بچے کے ساتھ نوڈ
  3. نوڈ دو بچوں کے ساتھ

اگر نوڈ ایک پتی ہے تو ، ہم درخت سے نوڈ کو آسانی سے نکال سکتے ہیں۔ اس کارروائی کے نتیجے میں بی ایس ٹی کی کسی بھی خصوصیات کی خلاف ورزی نہیں ہوسکتی ہے۔ اب اگر ہم ایک ہی بچے کے معاملے پر غور کریں۔ ہم آسانی سے نوڈ کو نکال سکتے ہیں اور اس کے بچے کو اس کی جگہ پر رکھ سکتے ہیں۔ صرف ایک ہی مسئلہ اس وقت پیدا ہوتا ہے جب ہم دو بچوں والے نوڈ کو ہٹانے کی کوشش کریں۔

نوڈ کو دو بچے رکھنے کے ل remove ، پہلے ہمیں اس نوڈ کا باضابطہ جانشین مل جاتا ہے۔ جانشین کو نوڈ کو ہٹائے جانے کی جگہ پر رکھیں۔ اب ہم ضمانت کیسے دے سکتے ہیں کہ جانشین کو ہٹانا BST خصوصیات کی خلاف ورزی نہیں کرے گا؟ ہم اس کی ضمانت دے سکتے ہیں کیونکہ جو نوڈ جو جانشین ہوتا ہے وہ کبھی بھی دو بچے پیدا نہیں کرسکتا۔ یا تو اس کا ایک ہی بچہ ہوگا یا کوئی بچہ نہیں۔ لہذا جانشین کو ہٹانا BST خصوصیات کی خلاف ورزی نہیں کرے گا۔ 

ضابطے

بائنری سرچ ٹری ڈیلیٹ آپریشن کیلئے سی ++ کوڈ

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int data;
    node *left, *right;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->left = tmp->right = NULL;
}

void inorder(node* root){
  if(root){
    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
  }
}

// return the node which is in the most left direction of root
// the smallest node in the entire subtree rooted at current node
node* minNode(node* root)
{
  node* tmp = root;
  while(tmp && tmp->left)
    tmp = tmp->left;
  return tmp;
}

// deleted the node with given data from tree
node* deleteNode(node* root, int data)
{
  // if current node is empty return current node(NULL)
  if(!root) return root;

  	// node to be deleted is in left sub-tree
    if (data < root->data)
        root->left = deleteNode(root->left, data);
  	// node to be deleted in right sub-tree
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    // current node is node to be deleted
    else
    {
        // Case 1 + Case 2
        // if left is null this means that it is either of the two cases
        if (root->left == NULL)
        {
            node* tmp = root->right;
            free(root);
            return tmp;
        }
        // Case 2 node has a left child but not right child
        // thus it has only a single child
        else if (root->right == NULL)
        {
            node* tmp = root->left;
            free(root);
            return tmp;
        }
  		// Case 3
  		// first find the successor
  		// successor is the element which comes next in inorder traversal of BST
  		// so it is the node in most left direction in right sub-tree
        node *successor = minNode(root->right);
        // place successor in place of current node
        root->data = successor->data;
        // now simply delete the successor from root's right child
        root->right = deleteNode(root->right, successor->data);
    }
    return root;
}

int main()
{
  node* root = create(7);
  root->left = create(5);
  root->right = create(8);
  root->left->left = create(3);
  root->left->left->right = create(4);
  root->left->right = create(6);
  cout<<"current inorder traversal of tree"<<endl;
  inorder(root);
  cout<<endl;
  root = deleteNode(root, 5);
  cout<<"inorder traversal after deleting node with value 5"<<endl;
  inorder(root);
  cout<<endl;
    return 0;
}
current inorder traversal of tree
3 4 5 6 7 8
inorder traversal after deleting node with value 5
3 4 6 7 8

بائنری سرچ ٹری ڈیلیٹ آپریشن کیلئے جاوا کوڈ

import java.util.*;
// Class that denotes a node of the tree
class node
{ 
    int data; 
    node left, right, random; 
  
    public node(int data) 
    { 
        this.data = data;
        left = right = random = null; 
    } 
}

class Tree 
{ 
    static node root;
  static node create(int data) {
    node tmp = new node(data);
    return tmp;
  }

  static void inorder(node root){
    if(root != null){
      inorder(root.left);
      System.out.print(root.data + " ");
      inorder(root.right);
    }
  }

  // return the node which is in the most left direction of root
  // the smallest node in the entire subtree rooted at current node
  static node minNode(node root) 
  {
    node tmp = root;
    while(tmp != null && tmp.left != null)
      tmp = tmp.left;
    return tmp;
  }
    
  // deleted the node with given data from tree
  static node deleteNode(node root, int data) 
  {
    // if current node is empty return current node(NULL)
    if(root == null) return root;
    	// node to be deleted is in left sub-tree
      if (data < root.data)
          root.left = deleteNode(root.left, data); 
    	// node to be delted in right sub-tree
      else if (data > root.data) 
          root.right = deleteNode(root.right, data); 
      // current node is node to be deleted
      else
      { 
          // Case 1 + Case 2
          // if left is null this means that it is either of the two cases
          if (root.left == null) 
          { 
              return root.right;
          } 
          // Case 2 node has a left child but not right child
          // thus it has only a single child
          else if (root.right == null)
          { 
              return root.left;
          }
    		// Case 3
    		// first find the successor
    		// successor is the element which comes next in inorder traversal of BST
    		// so it is the node in most left direction in right sub-tree
          node successor = minNode(root.right);
          // place successor in place of current node
          root.data = successor.data;
          // now simply delete the successor from root's right child
          root.right = deleteNode(root.right, successor.data); 
      } 
      return root; 
  }

  public static void main(String[] args) 
  {
    root = create(7);
    root.left = create(5);
    root.right = create(8);
    root.left.left = create(3);
    root.left.left.right = create(4);
    root.left.right = create(6);
    System.out.println("current inorder traversal of tree");
    inorder(root);
    System.out.println();
    root = deleteNode(root, 5);
    System.out.println("inorder traversal after deleting node with value 5");
    inorder(root);
    System.out.println();
  }
}
current inorder traversal of tree
3 4 5 6 7 8 
inorder traversal after deleting node with value 5
3 4 6 7 8 

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) ، حذف کرنے کے لئے۔ غور کریں کہ آپ کو درخت کی جڑ کو حذف کرنے کی ضرورت ہے جس میں دائیں اور دائیں بچے ہیں۔ اور دائیں بچے جڑ کے فوری دائیں بچے کے بعد بائیں سمت ایک اسککی درخت ہیں۔ لہذا یہ لائن کے وقت کی پیچیدگی میں چلانے کے لئے حذف عمل کو بناتا ہے۔

خلائی پیچیدگی

O (1) ، ڈیلیٹ آپریشن کے دوران۔ ہم نے کوئی معلومات ذخیرہ نہیں کی ہیں اور یوں الگ جگہ کو الگ جگہ بنانے کے ل. الگورتھم بنا دیا ہے۔

مندرجہ بالا نقطہ نظر میں ایک اصلاح موجود ہے لیکن اس میں O (N) وقت بھی لگتا ہے۔ ہم ایک انڈر ٹروراسل چلا سکتے ہیں اور ہر نوڈ کے والدین کو بچاسکتے ہیں۔ اس طرح جب ہمیں جانشین حذف کرنے کی ضرورت ہوتی ہے تو ہم صرف اس کے والدین کے بائیں یا دائیں بچے کو اسی کے مطابق ختم کردیتے ہیں۔ لیکن یہ نقطہ نظر O (N) کی جگہ لے جائے گا اور وقت کی بدترین پیچیدگی کو متاثر نہیں کرے گا۔