عملية حذف شجرة البحث الثنائية


مستوى الصعوبة الثابت
كثيرا ما يطلب في Accolite أمازون كوالكوم سامسونج
شجرة البحث الثنائية شجرة ثنائية شجرة

المشكلة بيان

تطلب منا مشكلة "عملية حذف شجرة البحث الثنائي" تنفيذ عملية الحذف الخاصة بها شجرة البحث الثنائية. تشير وظيفة الحذف إلى وظيفة حذف عقدة بمفتاح / بيانات معينة.

مثال

إدخال

عملية حذف شجرة البحث الثنائية

العقدة المراد حذفها = 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) للحذف. ضع في اعتبارك أنك بحاجة إلى حذف جذر الشجرة الذي يحتوي على أطفال يسار ويمين. والأطفال الأيمنون عبارة عن شجرة منحرفة في الاتجاه الأيسر بعد الطفل الأيمن للجذر. هذا يجعل عملية الحذف تعمل في تعقيد زمني خطي.

تعقيد الفضاء

يا (1) ، أثناء عملية الحذف. لم نقم بتخزين أي معلومات وبالتالي جعلنا الخوارزمية تأخذ مساحة ثابتة.

يوجد تحسين للنهج أعلاه ولكن هذا يستغرق أيضًا وقت O (N). يمكننا إجراء اجتياز داخلي وحفظ أصل كل عقدة. بهذه الطريقة عندما نحتاج إلى حذف الوريث ، فإننا ببساطة نستبدل الطفل الأيسر أو الأيمن لوالده ليصبح لاغياً وفقًا لذلك. لكن هذا النهج سيأخذ مساحة O (N) ولن يؤثر على تعقيد الوقت في أسوأ الحالات.