Операција брисања бинарног стабла претраживања  


Ниво тешкоће Тежак
Често питани у Аццолите амазонка куалцомм самсунг
Бинарно стабло претраживања Бинарно дрво Дрво

Изјава о проблему  

Проблем „Бинарна операција брисања стабла претраживања“ тражи да применимо операцију брисања за бинарно стабло претраге. Функција брисања односи се на функцију брисања чвора са датим кључем / подацима.

Пример  

Улазни

Операција брисања бинарног стабла претраживањаПин

Чвор за брисање = 5

Излаз

Пин

Приступ за Операција брисања бинарног стабла претраживања  

Дакле, када говоримо о брисању чвора из бинарног стабла претраживања. Имајте на уму да кад год избришемо чвор, сва својства БСТ-а морају бити задовољена. Ако уклањамо интерни чвор, морамо да се уверимо да подстабло заједно са новим кореном задовољава својства БСТ-а.

Сада имамо три случаја. Ови случајеви се заснивају на броју деце коју чвор има. И да одговорим на питање зашто категоризујемо чворове на основу броја деце? Дакле, лакше је изаћи на крај са оловом и чвором са једним дететом. Па хајде да укратко разговарамо о сва три случаја.

  1. Чвор без детета (лист)
  2. Чвор са једним дететом
  3. Чвор са двоје деце

Ако је чвор лист, чвор можемо једноставно уклонити са стабла. Ова операција не може довести до кршења ниједног БСТ својства. Сада ако размотримо случај једног детета. Једноставно можемо уклонити чвор и поставити његово дете на његово место. Једини проблем настаје када покушавамо да уклонимо чвор са двоје деце.

Да бисмо уклонили чвор који има двоје деце, прво проналазимо инордер наследника овог чвора. Поставите наследника на место чвора који се уклања. Како сада можемо гарантовати да уклањање наследника неће кршити БСТ својства? То можемо да гарантујемо јер чвор који је наследник никада не може имати двоје деце. Или ће имати једно дете или га уопште неће имати. Дакле, уклањање наследника неће кршити БСТ својства. 

код  

Ц ++ код за операцију брисања бинарног стабла претраживања

#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 

Анализа сложености  

Сложеност времена

НА), за брисање. Узмите у обзир да треба да избришете корен дрвета који има леву и десну децу. А десна деца су искривљена стабла у левом смеру након непосредног десног детета корена. Дакле, ово чини операцију брисања да ради у линеарној временској сложености.

Види такође
Патх Сум

Сложеност простора

О (1), током операције брисања. Нисмо ускладиштили ниједну информацију и на тај начин алгоритам заузима стални простор.

Постоји оптимизација за горњи приступ, али за то је потребно и О (Н) време. Можемо покренути обилазак реда и спасити родитеља сваког чвора. На овај начин када треба да избришемо наследника, једноставно заменимо лево или десно дете његовог родитеља да би постало нуло. Али тај приступ заузимаће О (Н) простор и неће утицати на најгору временску сложеност.