二分探索木-C++での削除操作

二分探索木（BST） は、次のルールに従う特殊なタイプのツリーです-

• 左の子ノードの値は常に親よりも小さくなります注

• 右の子ノードの値は親ノードよりも大きくなります。

• すべてのノードが個別に二分探索木を形成します。

二分探索木（BST）の例 −

バイナリ検索ツリーは、検索、最小値と最大値の検索などの操作の複雑さを軽減するために作成されます。

削除操作二分探索木（BST）

削除操作は、指定されたノードをツリーから削除しています。ノードを削除する場合、3つの可能性があります-

• ツリーからのリーフノードの削除：最も簡単な削除は、バイナリ検索ツリーからのリーフノードの削除です。リーフノードを削除すると、リーフのみが影響を受けます。例、

リーフノード7を削除すると、

• 子ノードが1つあるノードの削除：この削除では、子ノードを削除するノードに置き換えてから削除する必要があります。例、

BSTから2を削除する

• 2つの子ノードを持つノードの削除：ここでは、削除するノードに2つの子ノードがあります。したがって、ツリーの順序形式で使用します。ここでは、要素を削除し、その場所の順序に隣接する要素を選択して、残りを再作成します。例、

BSTから5を削除すると、次のツリーが返されます。

例

#include<stdio.h>
#include<stdlib.h>
struct node{
   int key;
   struct node *left, *right;
};
struct node *newNode(int item){
   struct node *temp = (struct node *)malloc(sizeof(struct node));
   temp->key = item;
   temp->left = temp->right = NULL;
   return temp;
}
void inordertraversal(struct node *root){
   if (root != NULL){
      inordertraversal(root->left);
      printf("%d ", root->key);
      inordertraversal(root->right);
   }
}
struct node* insert(struct node* node, int key){
   if (node == NULL) return newNode(key);
      if (key < node->key)
         node->left = insert(node->left, key);
      else
         node->right = insert(node->right, key);
   return node;
}
struct node * minValueNode(struct node* node){
   struct node* current = node;
   while (current && current->left != NULL)
      current = current->left;
   return current;
}
struct node* deleteNode(struct 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){
         struct node *temp = root->right;
         free(root);
         return temp;
      }
      else if (root->right == NULL){
         struct node *temp = root->left;
         free(root);
         return temp;
      }
      struct node* temp = minValueNode(root->right);
      root->key = temp->key;
      root->right = deleteNode(root->right, temp->key);
   }
   return root;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 50);
   root = insert(root, 30);
   root = insert(root, 20);
   root = insert(root, 40);
   root = insert(root, 70);
   root = insert(root, 60);
   root = insert(root, 80);
   printf("Inorder traversal of the given tree \n");
   inordertraversal(root);
   printf("\nDelete 20\n");
   root = deleteNode(root, 20);
   printf("Inorder traversal of the modified tree \n");
   inordertraversal(root);
   printf("\nDelete 30\n");
   root = deleteNode(root, 30);
   printf("Inorder traversal of the modified tree \n");
   inordertraversal(root);
   printf("\nDelete 50\n");
   root = deleteNode(root, 50);
   printf("Inorder traversal of the modified tree \n");
   inordertraversal(root);
   return 0;
}

出力

Inorder traversal of the given tree
20 30 40 50 60 70 80
Delete 20
Inorder traversal of the modified tree
30 40 50 60 70 80
Delete 30
Inorder traversal of the modified tree
40 50 60 70 80
Delete 50
Inorder traversal of the modified tree
40 60 70 80