Data-structures-algorithms-binary-search-tree

データ構造-バイナリ検索ツリー

バイナリ検索ツリー（BST）は、すべてのノードが下記のプロパティに従うツリーです-

• ノードの左のサブツリーのキーは、親ノードのキー以下です。
• ノードの右サブツリーには、親ノードのキーよりも大きいキーがあります。

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

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

表現

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

以下は、BSTの図解です-

バイナリ検索ツリー

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

基本操作

以下は、ツリーの基本的な操作です-

• 検索-ツリー内の要素を検索します。
• 挿入-ツリーに要素を挿入します。
• Pre-order Traversal -事前順序でツリーを走査します。
• In-order Traversal -ツリーを順序どおりに走査します。
• Post-order Traversal -ポストオーダー方式でツリーを横断します。

Node

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

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;
            }
         }
      }
   }
}