ორობითი ხის კვანძის მეორეხარისხოვანი რიგი


Რთული ტური Hard
ხშირად ეკითხებიან Amazon Expedia Morgan Stanley OYO ოთახები Snapchat
ორობითი ძებნა ხე ხე

პრობლემის განცხადება

პრობლემა ითხოვს ”ორობითი ხის კვანძის მეორეხარისხოვანი წესის” მოძიებას. კვანძის რიგითი მემკვიდრე არის ორობითი ხის კვანძი, რომელიც მოდის მოცემული ორობითი ხის ინორდურის გადაკვეთის მოცემული კვანძის შემდეგ.

მაგალითი

Inorder successor of 6 is 4

განმარტება

ხის გადაკვეთის შეკვეთა არის 9 7 1 6 4 5 3. ამრიგად, 1-ის შემოვლითი რიცხვი არის 6.

მიდგომა

საერთოდ, გვეუბნებიან, რომ შემდეგი კვანძი უნდა იპოვოთ a ორობითი ძებნის ხე. მაგრამ ეს განსხვავდება ორობითი ხისგან. ასე რომ, ერთი რამ, რაც უნდა გავითვალისწინოთ არის ის, რომ ზოგადი ორობითი ხის უგულებელყოფა არ არის ზრდადი თანმიმდევრობით. ახლა კი წინ წავიდეთ. ასე რომ, თუ კვანძი გვაქვს, არის 3 შემთხვევა, რომლებიც უნდა გამოვიკვლიოთ.

3 შემთხვევა, რომელიც უნდა აღვნიშნოთ, უკავშირდება მის სწორ შვილს, ან თუ ამჟამინდელი კვანძი თავად არის ყველაზე სწორი ბავშვი. ასე რომ, თუ კვანძს სწორი შვილი ჰყავს. შემდეგ მეორეხარისხოვანი მემკვიდრე უბრალოდ ყველაზე მარცხენა შვილია მის ქვედა ქვეტყეში. მაგრამ თუ მას არ ჰყავს სწორი შვილი. შემდეგ იპოვნეთ მოცემული კვანძის ყველაზე დაბალი წინაპარი ისეთი, რომ მოცემული კვანძი იყოს წინაპრის მარცხენა ქვეტყეში. ამისათვის, რეკურსიულად იპოვნეთ კვანძი, ხოლო როდესაც უკან ვბრუნდებით, შევინახეთ მშობელი, საიდანაც ავირჩიეთ მარცხენა მიმართულება.

ახლა ბოლო შემთხვევაა, თუ კვანძი ყველაზე სწორი შვილია. თუ ეს მოხდება, არ არსებობს კვანძის რაიმე შემცვლელი მიმდევრობა.

კოდი

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

სირთულის ანალიზი

დროის სირთულე

O (N), რადგან უარეს შემთხვევაში შეიძლება მოგვიწიოს ყველა კვანძის გადაკვეთა.

სივრცის სირთულე

O (H), რადგან ჩვენ გამოვიყენეთ რეკურსია. ამრიგად, თუ გავითვალისწინებთ შემდგენლის სტეკის მიერ გატარებულ ადგილს. სივრცის სირთულე დამოკიდებულია ხის სიმაღლეზე.