이진 검색 트리 삭제

Harshit Jindal 2023년10월12일
  1. 이진 검색 트리에서 작업 삭제
  2. 이진 검색 트리 그림 삭제
  3. BST 삭제 알고리즘
  4. 이진 검색 트리 삭제 구현
  5. 이진 검색 트리 삭제 알고리즘 복잡성
이진 검색 트리 삭제

이진 탐색 트리: 검색 및 삽입 기사에서 BST에 요소를 삽입하는 방법과 방법에 대해 논의했습니다. BST에서 값을 검색합니다. 이 기사에서는 이진 검색 트리에서 노드를 삭제하는 방법에 대해 설명합니다.

이진 검색 트리에서 작업 삭제

BST에 노드를 삽입하는 것은 비교적 간단합니다. 그러나 노드를 삭제하는 동안 여러 가능성을 고려해야합니다. 다음 3 가지 경우가 발생할 수 있습니다.

  • 삭제할 노드에 자식이 없습니다-리프입니다.

이것은 가장 간단한 경우입니다. 리프 노드에는 자식이 없기 때문에 아무것도 돌볼 필요가 없습니다. 리프 노드를NULL로 바꾸고이 노드에 할당 된 공간을 해제 할 수 있습니다.

  • 삭제할 노드에는 자식이 하나만 있습니다 (왼쪽 또는 오른쪽 자식).

이 경우 노드의 자식을 저장하고 원래 위치에서 노드를 제거합니다. 그러면 자식 노드가 삭제 된 노드의 원래 위치에 삽입됩니다.

  • 삭제할 노드에는 왼쪽과 오른쪽 자식이 모두 있습니다.

여기서는 노드를 단순히 삭제하거나 하위 노드로 바꿀 수 없기 때문에 가장 까다로운 경우입니다. 이 경우minnode노드의 오른쪽 하위 트리에서 가장 작은 노드를 찾습니다. 삭제할 노드의 값을minnode의 값으로 바꾸고이 노드에서 삭제를 재귀 적으로 호출합니다.

이진 검색 트리 그림 삭제

  • 삭제할 노드에 자식이 없습니다-리프입니다.

    이진 검색 트리 삭제 작업
    노드7에는 하위가 없습니다. 단순히 트리에서 삭제하면 BST 속성이 위반되지 않습니다.

  • 삭제할 노드에는 자식이 하나만 있습니다.

    이진 검색 트리 삭제 작업
    노드15에는 1 개의 하위7이 있습니다. 15를 삭제하기 전에 처리해야합니다. 따라서 먼저 복사 한 다음15로 바꿉니다.

  • 삭제할 노드에는 두 하위 항목이 있습니다.

    이진 검색 트리 삭제 작업
    노드21에는1527이라는 두 개의 하위가 있습니다. 오른쪽 하위 트리23에서 가장 작은 요소를 찾아21으로 바꾼 다음 재귀를 호출하여 오른쪽 하위 트리에서23을 삭제합니다.

BST 삭제 알고리즘

  • root==NULL이면NULL을 반환합니다.
  • root->key<X이면 왼쪽 하위 트리를 버리고 오른쪽 하위 트리에서 삭제할 요소를 찾습니다.

    root->right =deleteNode(root->right, X)

  • root->key>X이면 오른쪽 하위 트리를 버리고 왼쪽 하위 트리에서 삭제할 요소를 찾습니다.

    root->left =deleteNode(root->left, X)

  • root->key==X인 경우 다음 3 가지 경우에 따라 조치를 취하십시오.
    • If (root->left==NULL&&root->right==NULL) 다음root를 삭제하고NULL을 반환합니다.
    • 그렇지 않으면 if (root->right==NULL) 왼쪽 하위 트리를 복사하고 삭제할 노드로 바꿉니다.
    • 그렇지 않으면 if (root->left==NULL) 오른쪽 하위 트리를 복사하고 삭제할 노드로 바꿉니다.
    • 그렇지 않으면 if (root->left&&root->right) 오른쪽 하위 트리minnode에서 최소 노드를 찾아 삭제할 노드로 바꿉니다. 오른쪽 하위 트리에서minnode를 재귀 적으로 삭제합니다.
  • 원래root에 대한 포인터를 반환합니다.

이진 검색 트리 삭제 구현

#include <iostream>
using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
};

Node* newNode(int item) {
  Node* temp = new Node;
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

void inorder(Node* root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}

void insert(Node*& root, int key) {
  Node* toinsert = newNode(key);
  Node* curr = root;
  Node* prev = NULL;

  while (curr != NULL) {
    prev = curr;
    if (key < curr->key)
      curr = curr->left;
    else
      curr = curr->right;
  }
  if (prev == NULL) {
    prev = toinsert;
    root = prev;
  }

  else if (key < prev->key) {
    prev->left = toinsert;
  }

  else {
    prev->right = toinsert;
  }
}

Node* getmin(Node* root) {
  Node* curr = root;

  while (curr && curr->left) {
    curr = curr->left;
  }

  return curr;
}

Node* deleteNode(Node* root, int key) {
  if (root == NULL) return root;

  if (key < root->key)
    root->left = deleteNode(root->left, key);

  else if (key > root->key)
    root->right = deleteNode(root->right, key);
  else {
    if (root->left == NULL) {
      Node* temp = root->right;
      delete (root);
      return temp;
    } else if (root->right == NULL) {
      Node* temp = root->left;
      delete (root);
      return temp;
    }

    Node* temp = getmin(root->right);

    root->key = temp->key;
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

int main() {
  Node* root = NULL;
  insert(root, 5);
  insert(root, 3);
  insert(root, 8);
  insert(root, 6);
  insert(root, 4);
  insert(root, 2);
  insert(root, 1);
  insert(root, 7);
  inorder(root);
  cout << "\n";
  deleteNode(root, 5);
  inorder(root);
}

이진 검색 트리 삭제 알고리즘 복잡성

시간 복잡성

  • 평균 사례

평균적으로 BST에서 노드를 삭제하는 시간 복잡도는 이진 검색 트리의 높이 순서입니다. 평균적으로 BST의 높이는O(logn)입니다. 형성된 BST가 균형 BST 일 때 발생합니다. 따라서 시간 복잡도는 [Big Theta] :O(logn)의 순서입니다.

  • 베스트 케이스

최상의 경우는 트리가 균형 잡힌 BST 일 때 발생합니다. 삭제의 가장 좋은 경우 시간 복잡도는O(logn)순서입니다. 평균 케이스 시간 복잡성과 동일합니다.

  • 최악의 경우

최악의 경우 루트에서 가장 깊은 리프 노드, 즉 트리의 전체 높이h로 이동해야 할 수 있습니다. 트리의 균형이 맞지 않는 경우 (예 : 치우친 경우) 트리의 높이가n이 될 수 있으므로 삽입 및 검색 작업의 최악의 경우 시간 복잡성은O(n)입니다.

공간 복잡성

알고리즘의 공간 복잡도는 재귀 호출에 필요한 추가 공간으로 인해O(n)입니다.

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

관련 문장 - Data Structure

관련 문장 - Binary Tree

관련 문장 - Binary Search Tree