이진 검색 트리 삭제 작업

난이도 하드
자주 묻는 질문 수행자 아마존 퀄컴 삼성
이진 검색 트리 이진 트리 나무조회수 31

문제 정책

“바이너리 검색 트리 삭제 작업”문제는 우리에게 삭제 작업을 구현하도록 요청합니다. 이진 검색 트리. 삭제 기능은 주어진 키 / 데이터로 노드를 삭제하는 기능을 말합니다.

입력

이진 검색 트리 삭제 작업

삭제할 노드 = 5

산출

에 대한 접근 이진 검색 트리 삭제 작업

이진 검색 트리에서 노드를 삭제하는 것에 대해 이야기 할 때. 한 가지주의 할 점은 노드를 삭제할 때마다 BST의 모든 속성이 충족되어야한다는 것입니다. 내부 노드를 제거하는 경우 새 루트와 함께 하위 트리가 BST의 속성을 충족하는지 확인해야합니다.

이제 처리해야 할 세 가지 사례가 있습니다. 이러한 경우는 노드에있는 자식 수를 기반으로합니다. 그리고 왜 자녀 수를 기준으로 노드를 분류하고 있습니까? 따라서 단일 자식이있는 리드와 노드를 처리하는 것이 더 쉽습니다. 따라서 세 가지 사례를 모두 간략하게 논의하겠습니다.

  1. 자식이없는 노드 (리프)
  2. 단일 자식이있는 노드
  3. 두 자녀가있는 노드

노드가 리프이면 간단히 트리에서 노드를 제거 할 수 있습니다. 이 작업으로 인해 BST 속성이 위반 될 수 없습니다. 이제 우리가 한 아이의 경우를 생각해 보면. 노드를 제거하고 그 자리에 자식을 배치하기 만하면됩니다. 유일한 문제는 자식이 두 개인 노드를 제거하려고 할 때 발생합니다.

두 개의 자식을 가진 노드를 제거하려면 먼저이 노드의 inorder 후속 노드를 찾습니다. 제거 할 노드 위치에 후속 작업을 배치합니다. 이제 후속 작업을 제거해도 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) 시간이 걸립니다. inorder traversal을 실행하고 각 노드의 부모를 저장할 수 있습니다. 이런 식으로 후속 작업을 삭제해야 할 때 부모의 왼쪽 또는 오른쪽 자식을 그에 따라 null로 바꿉니다. 그러나 이러한 접근 방식은 O (N) 공간을 차지하고 최악의 시간 복잡성에 영향을 미치지 않습니다.

Translate »