ორობითი ძიების ხის წაშლის ოპერაცია


Რთული ტური Hard
ხშირად ეკითხებიან თანამოსაყრელი Amazon Qualcomm Samsung
ორობითი ძებნა ხე ორობითი ხე ხე

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

პრობლემა ”ორობითი ძიების ხის წაშლის ოპერაცია” გვთხოვს განვახორციელოთ წაშლის ოპერაცია ორობითი ძებნის ხე. ფუნქციის წაშლა გულისხმობს მოცემული გასაღებით / მონაცემებით კვანძის წაშლის ფუნქციონირებას.

მაგალითი

შეყვანის

ორობითი ძიების ხის წაშლის ოპერაცია

გასასვლელი კვანძი = 5

გამოყვანის

მიდგომა ორობითი ძიების ხის წაშლის ოპერაცია

ასე რომ, როდესაც ვსაუბრობთ ორობითი ძიების ხისგან კვანძის წაშლაზე. ერთი რამ უნდა აღინიშნოს, როდესაც კვანძს ვშლით, BST– ის ყველა თვისება დაკმაყოფილებული უნდა იყოს. თუ ჩვენ ვაღებთ შიდა კვანძს, უნდა დავრწმუნდეთ, რომ ქვედა ხე ახალ ფესვთან ერთად აკმაყოფილებს BST თვისებებს.

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

  1. კვანძი, რომელსაც არ აქვს შვილი (ფოთოლი)
  2. კვანძი მარტოხელა შვილთან ერთად
  3. კვანძი ორი შვილით

თუ კვანძი ფოთოლია, ჩვენ შეგვიძლია უბრალოდ მოვაცილოთ კვანძი ხიდან. ამ ოპერაციას არ შეუძლია გამოიწვიოს BST– ის რომელიმე თვისების დარღვევა. ახლა თუ გავითვალისწინებთ მარტოხელა შვილის საქმეს. ჩვენ შეგვიძლია უბრალოდ ამოვიღოთ კვანძი და მოვათავსოთ იგი მის ადგილას. ერთადერთი პრობლემა წარმოიქმნება, როდესაც ვცდილობთ ორ ბავშვთან ერთად კვანძი ამოვიღოთ.

ორი შვილის ყოლის კვანძის მოსაცილებლად, პირველ რიგში, ამ კვანძის მემკვიდრედ ვხვდებით. განათავსეთ მემკვიდრე კვანძის ამოღების ადგილას. ახლა როგორ შეგვიძლია გარანტიას ვიყოთ, რომ მემკვიდრის მოხსნა არ დაარღვევს BST თვისებებს? ამის გარანტია შეგვიძლია, რადგან კვანძს, რომელიც მემკვიდრეა, არასოდეს შეიძლება ორი შვილი ჰყავდეს. ან მას ერთი შვილი ეყოლება, ან საერთოდ არ ეყოლება შვილი. ასე რომ, მემკვიდრის მოხსნა არ დაარღვევს BST თვისებებს. 

კოდი

ორობითი ძიების ხის წაშლის ოპერაციისთვის 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;
}

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) სივრცეს და გავლენას არ მოახდენს უარესი დროის სირთულეზე.