Λειτουργία Διαγραφής Δυαδικού Δέντρου Αναζήτησης


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις Απολύτως αμαζόνα Qualcomm Samsung
Δυαδικό δέντρο αναζήτησης Δυαδικό δέντρο Δέντρο

Δήλωση προβλήματος

Το πρόβλημα "Binary Search Tree Delete Operation" μας ζητά να εφαρμόσουμε τη λειτουργία διαγραφής για δυαδικό δέντρο αναζήτησης. Η λειτουργία διαγραφής αναφέρεται στη λειτουργικότητα διαγραφής ενός κόμβου με δεδομένο κλειδί / δεδομένα.

Παράδειγμα

Εισαγωγή

Λειτουργία Διαγραφής Δυαδικού Δέντρου Αναζήτησης

Κόμβος προς διαγραφή = 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

Κωδικός Java για λειτουργία δυαδικής αναζήτησης δέντρου διαγραφής

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), κατά τη λειτουργία διαγραφής. Δεν έχουμε αποθηκεύσει καμία πληροφορία και, κατά συνέπεια, ο αλγόριθμος παίρνει σταθερό χώρο.

Υπάρχει μια βελτιστοποίηση στην παραπάνω προσέγγιση, αλλά αυτό απαιτεί επίσης χρόνο Ο (Ν). Μπορούμε να εκτελέσουμε ένα inorder traversal και να σώσουμε τον γονέα κάθε κόμβου. Με αυτόν τον τρόπο, όταν πρέπει να διαγράψουμε τον διάδοχο, απλά αντικαθιστούμε το αριστερό ή το δεξί παιδί του γονέα του για να ακυρώσει ανάλογα. Αλλά αυτή η προσέγγιση θα πάρει το διάστημα O (N) και δεν θα επηρεάσει τη χειρότερη περίπτωση πολυπλοκότητας.