データ構造-二分探索木

二分探索木（BST）は、すべてのノードが以下のプロパティに従うツリーです。

左側のサブツリーのキーの値は、その親（ルート）ノードのキーの値よりも小さくなっています。
右側のサブツリーのキーの値は、その親（ルート）ノードのキーの値以上です。

したがって、BSTはすべてのサブツリーを2つのセグメントに分割します。左側のサブツリーと右側のサブツリーであり、次のように定義できます。

left_subtree (keys) < node (key) ≤ right_subtree (keys)

表現

BSTは、BSTプロパティを維持するように配置されたノードのコレクションです。各ノードには、キーと関連する値があります。検索中に、目的のキーがBSTのキーと比較され、見つかった場合は、関連付けられた値が取得されます。

以下はBSTの図解です-

ルートノードキー（27）には、左側のサブツリーに値の小さいキーがすべてあり、右側のサブツリーに値の大きいキーがあることがわかります。

基本操作

ツリーの基本的な操作は次のとおりです-

Search −ツリー内の要素を検索します。
Insert −ツリーに要素を挿入します。
Pre-order Traversal −事前注文方式でツリーをトラバースします。
In-order Traversal −ツリーを順番にトラバースします。
Post-order Traversal −ポストオーダー方式でツリーをトラバースします。

ノード

いくつかのデータ、その左右の子ノードへの参照を持つノードを定義します。

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

検索操作

要素を検索する場合は常に、ルートノードから検索を開始してください。次に、データがキー値よりも小さい場合は、左側のサブツリーで要素を検索します。それ以外の場合は、右側のサブツリーで要素を検索します。各ノードで同じアルゴリズムに従います。

アルゴリズム

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   
   return current;
}

挿入操作

要素を挿入するときは常に、最初にその適切な場所を見つけます。ルートノードから検索を開始し、データがキー値よりも小さい場合は、左側のサブツリーで空の場所を検索し、データを挿入します。それ以外の場合は、右側のサブツリーで空の場所を検索し、データを挿入します。

アルゴリズム

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}