Операция удаления двоичного дерева поиска


Сложный уровень Жесткий
Часто спрашивают в Акколит Амазонка Компания 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 

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

Сложность времени

НА), для удаления. Предположим, вам нужно удалить корень дерева, у которого есть левый и правый дочерние элементы. И правые дочерние элементы - это наклонное дерево в левом направлении после непосредственного правого дочернего элемента root. Таким образом, операция удаления выполняется с линейной временной сложностью.

Космическая сложность

О (1), во время операции удаления. Мы не храним никакой информации и, таким образом, заставляем алгоритм занимать постоянное место.

Существует оптимизация вышеупомянутого подхода, но она также требует времени O (N). Мы можем запустить обход по порядку и сохранить родительский элемент каждого узла. Таким образом, когда нам нужно удалить наследника, мы просто заменяем его родительский левый или правый дочерний элемент на null соответственно. Но этот подход займет O (N) пространство и не повлияет на временную сложность наихудшего случая.