データ構造とアルゴリズム-ツリー

ツリーは、エッジで接続されたノードを表します。具体的には、二分木または二分探索木について説明します。

バイナリツリーは、データストレージの目的で使用される特別なデータ構造です。二分木には、各ノードが最大2つの子を持つことができるという特別な条件があります。バイナリツリーには、検索が並べ替えられた配列と同じくらい速く、挿入または削除操作がリンクされたリストと同じくらい速いので、順序付けられた配列とリンクされたリストの両方の利点があります。

重要な用語

以下は、ツリーに関する重要な用語です。

Path −パスは、ツリーのエッジに沿ったノードのシーケンスを指します。
Root−ツリーの最上部にあるノードはルートと呼ばれます。ツリーごとに1つのルートと、ルートノードから任意のノードへのパスが1つだけあります。
Parent −ルートノードを除くすべてのノードには、親と呼ばれるノードの上方に1つのエッジがあります。
Child −エッジで下向きに接続された特定のノードの下のノードは、子ノードと呼ばれます。
Leaf −子ノードを持たないノードをリーフノードと呼びます。
Subtree −サブツリーはノードの子孫を表します。
Visiting −訪問とは、制御がノード上にあるときにノードの値をチェックすることを指します。
Traversing −トラバースとは、特定の順序でノードを通過することを意味します。
Levels−ノードのレベルは、ノードの生成を表します。ルートノードがレベル0の場合、次の子ノードはレベル1にあり、孫はレベル2にあり、以下同様に続きます。
keys −キーは、ノードに対して検索操作を実行するための基準となるノードの値を表します。

二分探索木表現

二分探索木は特別な振る舞いを示します。ノードの左の子はその親の値よりも小さい値である必要があり、ノードの右の子はその親の値よりも大きい値である必要があります。

ノードオブジェクトを使用してツリーを実装し、参照を介してそれらを接続します。

ツリーノード

ツリーノードを作成するコードは、以下のコードのようになります。データ部分と、その左右の子ノードへの参照があります。

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

ツリーでは、すべてのノードが共通の構成を共有します。

BSTの基本操作

二分探索木データ構造で実行できる基本的な操作は次のとおりです。

Insert −ツリーに要素を挿入/ツリーを作成します。
Search −ツリー内の要素を検索します。
Preorder Traversal −事前注文方式でツリーをトラバースします。
Inorder Traversal −ツリーを順番にトラバースします。
Postorder Traversal −ポストオーダー方式でツリーをトラバースします。

この章では、ツリー構造の作成（挿入）とツリー内のデータ項目の検索について学習します。次の章では、ツリー走査方法について学習します。

挿入操作

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

アルゴリズム

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

実装

挿入関数の実装は次のようになります-

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, create root node
   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;
            }
         }
      }            
   }
}

検索操作

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

アルゴリズム

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

このアルゴリズムの実装は次のようになります。

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

二分探索木のデータ構造の実装については、ここをクリックしてください。