Операція видалення бінарного дерева пошуку  


Рівень складності Жорсткий
Часто запитують у Аколіт Амазонка компанія 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

Код 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 

Аналіз складності  

Складність часу

O (N), для видалення. Подумайте, вам потрібно видалити корінь дерева, що має лівого та правого дітей. А праві діти - це перекошене дерево в лівому напрямку після безпосередньої правої дитини кореня. Отже, це робить операцію видалення запущеною в лінійній часовій складності.

Дивись також
Сума шляху

Складність простору

O (1), під час операції видалення. Ми не зберігали жодної інформації і, таким чином, робимо алгоритм постійним простором.

Існує оптимізація вищевказаного підходу, але це також вимагає часу O (N). Ми можемо виконати обхід inorder та зберегти батьківський елемент кожного вузла. Таким чином, коли нам потрібно видалити наступника, ми просто замінюємо ліву чи праву дочірню особу батьків на нульові значення. Але такий підхід займе O (N) простір і не вплине на найгіршу складність часу.