二進制搜索樹刪除操作


難度級別
經常問 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)空間,並且不會影響最壞情況下的時間複雜度。