二进制搜索树删除操作


难度级别
经常问 ol石 亚马逊 高通公司 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(1), 在删除操作期间。 我们没有存储任何信息,因此使算法占用恒定空间。

虽然存在对上述方法的优化,但也需要O(N)时间。 我们可以进行有序遍历并保存每个节点的父级。 这样,当我们需要删除后继者时,我们只需将其父代的左或右子代替换为空即可。 但是该方法将占用O(N)空间,并且不会影响最坏情况下的时间复杂度。