بائنري وڻ ۾ هڪ نوڊ جو ڪامياب جانشين


تڪليف جي سطح سخت
بار بار پڇڻ ۾ Amazon Expedia مارگن Stanley OYO ڪمرا Snapchat
ثنائي ڳولا وارو وڻ وڻن

مسئلي جو بيان

مسئلو ”بائنري وڻ ۾ هڪ نوڊ جي انڊرڊ سيڊور کي ڳولڻ“ لاءِ پڇي ٿو. هڪ جوڙيندڙ جاندار جي هڪ بيڊ بائنري وڻ ۾ هڪ جوڙ آهي جيڪو ڏنل بائنري وڻ جي انڊرر ٽراسل ۾ ڏنل نوڊ کان پوءِ ايندو آهي.

مثال

Inorder successor of 6 is 4

وضاحت

وڻ جو اندرينڊر ٽراسل 9 7 1 6 4 5 3. تنهن ڪري 1 جو انڊرڊر جانشير 6 هوندو آهي

چرچو

عام طور تي ، اسان کي ٻڌايو ويندو آهي ته ايندڙ نوڊ کي بائنري ڳولا وارو وڻ. پر اھو بئن جو وڻ کان مختلف آھي. تنهنڪري هڪ شيءِ جيڪا اسان کي ياد رکڻ گهرجي ته هڪ عام بائنري وڻ جي انڊرورس ڪرايل چڙهڻ جي حڪم ۾ ناهي. هاڻي اچون ٿا اڳتي اڳتي. جيڪڏهن اسان وٽ هڪ نوڊ آهي ته پوء 3 ڪيس آهن جيڪي اسان کي ڏسڻ گهرجي.

3 ڪيس جنهن کي اسان نوٽ ڪرڻ گھرجي اها ان جي صحيح ٻار سان تعلق رکي ٿي يا جيڪڏهن موجوده جوڙ پنهنجو پاڻ تي صحيح ٻار آهي. تنهن ڪري جيڪڏهن جوڙ جو صحيح ٻار آهي. پوءِ انڊرورڊ جانشين فقط ان جي صحيح سبجيڪٽ ۾ کاٻي ڌر آهي. پر جيڪڏهن اهو صحيح ٻار نٿي ٿئي. پوءِ وراڻيو نوڊ جي تمام نن ancestا اباھٽ ڳوليو جيئن ڏنل نوڊ انڊرڊر جي کاٻي سبٽي ۾ رکيل آھي اھو ڪرڻ لاءِ ، recursively نوڊ ڳولھيو ، ۽ جڏھن اسين recursion کان واپس وٺي وڃي والدين کي جتي اسان کاٻي طرف چونڊيو آھي

هاڻ آخري معاملو اهو آهي ته جيڪڏهن نوڊ تمام صحيح ٻار آهي. جيڪڏھن اھو ٿئي ، اتي نوڊ لاءِ ڪنھن آرڊر جي جانشين موجود نه ھجي.

ڪوڊ

بائنري وڻ ۾ هڪ نوڊ جو انڊرڊر جانشين ڳولڻ لاءِ C ++ ڪوڊ

#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;
  return tmp;
}

node* findLeftMostNode(node* root){
  while(root && root->left) root = root->left;
  return root;
}

node* findRightMostNode(node* root){
  while(root && root->right) root = root->right;
  return root;
}

node* findAncestorSuccessor(node* root, node* given)
{
  if(root){
    if(root == given)
      return root;
    node* tmp = findAncestorSuccessor(root->left, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
    tmp = findAncestorSuccessor(root->right, given);
    if(tmp){
      if(root->left == tmp){
        cout<<"Inorder Successor of "<<given->data<<" is "<<root->data;
        return NULL;
      }
      return root;
    }
  }
    return NULL;
}

void findInorderSuccesor(node* root, node* given)
{
    // if right child exists
    if(given->right)
    {
    	node* leftmost = findLeftMostNode(given);
    	cout<<"Inorder Succesor of "<<given->data<<" is "<<leftmost->data;
    	return;
    }
    // if right child does not exists
    if(given->right == NULL)
    {
        node* rightmost = findRightMostNode(root);
        if(rightmost == given)
            cout<<"Inorder Successor does not exists";
        else
        	findAncestorSuccessor(root, given);
    }
}

int main()
{
  node* root = create(5);
  root->left = create(7);
  root->right = create(3);
  root->left->left = create(9);
  root->left->right = create(6);
  root->left->right->left = create(1);
  root->left->right->right = create(4);
  findInorderSuccesor(root, root->left->right->left);
}
Inorder Successor of 1 is 6

جاوا ڪوڊ بائنري وڻ ۾ هڪ نوڊ جي انڊرڊر جانشين ڳولڻ لاءِ

import java.util.*;

class node{
  int data;
  node left, right;
}

class Main{
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = tmp.right = null;
    return tmp;
  }

  static node findLeftMostNode(node root){
    while(root != null && root.left != null) root = root.left;
    return root;
  }

  static node findRightMostNode(node root){
    while(root != null && root.right != null) root = root.right;
    return root;
  }

  static node findAncestorSuccessor(node root, node given)
  {
    if(root != null){
      if(root == given)
        return root;
      node tmp = findAncestorSuccessor(root.left, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
      tmp = findAncestorSuccessor(root.right, given);
      if(tmp != null){
        if(root.left == tmp){
          System.out.print("Inorder Successor of "+given.data+" is "+root.data);
          return null;
        }
        return root;
      }
    }
      return null;
  }

  static void findInorderSuccesor(node root, node given)
  {
      // if right child exists
      if(given.right != null)
      {
      	node leftmost = findLeftMostNode(given);
      	System.out.print("Inorder Successor of "+given.data+" is "+leftmost.data);
      	return;
      }
      // if right child does not exists
      else
      {
          node rightmost = findRightMostNode(root);
          if(rightmost == given)
              System.out.print("Inorder Successor does not exists");
          else
          	findAncestorSuccessor(root, given);
      }
  }

  public static void main(String[] args)
  {
    node root = create(5);
    root.left = create(7);
    root.right = create(3);
    root.left.left = create(9);
    root.left.right = create(6);
    root.left.right.left = create(1);
    root.left.right.right = create(4);
    findInorderSuccesor(root, root.left.right.left);
  }
}
Inorder Successor of 1 is 6

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، ڇاڪاڻ ته بدترين حالتن ۾ اسان کي شايد سڀني نوڊن مان پار ڪرڻو پوندو.

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

اي (ايڇ) ، ڇاڪاڻ ته اسان recursion استعمال ڪيو آهي. اهڙيءَ طرح جيڪڏهن اسان ڪمپائلر اسٽيڪ طرفان کڻندڙ جڳهه تي غور ڪريون. خلائي پيچيدگي انحصار آهي وڻ جي قد تي.