二分探索木-C++での検索および挿入操作

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

• 左の子ノードの値は常に親の注よりも小さくなります
• 右の子ノードの値は親ノードよりも大きくなります。
• すべてのノードが個別に二分探索木を形成します。

二分探索木（BST）の例-

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

BSTでの検索操作

二分探索木で検索を実行する

ツリーでキーを検索する必要があります。このために、キーをツリーのルートノードと比較します。

キーがルートノードと等しい場合、キーが見つかります。

キーの値がルートノードより大きい場合は、右側のサブツリーを取得してキーを検索します。

キーの値がルートノードよりも小さい場合は、左側のサブツリーを取得してキーを検索します。

例

#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 traversetree(struct node *root){
   if (root != NULL){
      traversetree(root->left);
      printf("%d \t", root->key);
      traversetree(root->right);
   }
}
struct node* search(struct node* root, int key){
   if (root == NULL || root->key == key)
      return root;
   if (root->key < key)
      return search(root->right, key);
   return search(root->left, key);
}
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 if (key > node->key)
         node->right = insert(node->right, key);
   return node;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 23);
   insert(root, 15);
   insert(root, 12);
   insert(root, 17);
   insert(root, 32);
   insert(root, 29);
   insert(root, 45);
   printf("The tree is :\n");
   traversetree(root);
   printf("\nSearching for 12 in this tree ");
   if(search(root , 12))
      printf("\nelement found");
   else
      printf("\nelement not found");
   return 0;
}

出力

The tree is :
12 15 17 23 29 32 45
Searching for 12 in this tree
element found

BSTでの挿入操作

BSTでの挿入操作は、挿入のためにツリーのリーフノードで実行されます。ノードとルートノードの比較を開始し、ノードの正しい位置を見つけて配置します。次の例は、より明確になります。

このBSTに12を挿入します。

12をルートノード12>5と比較します。これは、右側のサブツリーに属しています。

12を右の子ノード12>8と比較してください。これは、右のサブ子の右側に属しています。

12を右サブツリー12>10の右サブ子と比較すると、その位置はこのノードの右側です。

形成される新しいツリーは、

例

#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 traversetree(struct node *root){
   if (root != NULL){
      traversetree(root->left);
      printf("%d \t", root->key);
      traversetree(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 if (key > node->key)
         node->right = insert(node->right, key);
   return node;
}
int main(){
   struct node *root = NULL;
   root = insert(root, 23);
   insert(root, 15);
   insert(root, 12);
   insert(root, 17);
   insert(root, 32);
   insert(root, 29);
   printf("The tree is :\n");
   traversetree(root);
   printf("\nInseting 45 to the tree\n");
   insert(root, 45);
   printf("Tree after insertion is :\n");
   traversetree(root);
   return 0;
}

出力

The tree is :
12 15 17 23 29 32
Inserting 45 to the tree
Tree after insertion is :
12 15 17 23 29 32 45