Struktura danych - drzewo wyszukiwania binarnego

Drzewo wyszukiwania binarnego (BST) to drzewo, w którym wszystkie węzły mają następujące właściwości -

• Wartość klucza lewego poddrzewa jest mniejsza niż wartość klucza jego węzła nadrzędnego (głównego).

• Wartość klucza prawego poddrzewa jest większa lub równa wartości klucza jego węzła nadrzędnego (głównego).

Zatem BST dzieli wszystkie swoje poddrzewa na dwa segmenty; lewe poddrzewo i prawe poddrzewo i można je zdefiniować jako -

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

Reprezentacja

BST to zbiór węzłów ułożonych w taki sposób, że zachowują właściwości BST. Każdy węzeł ma klucz i skojarzoną z nim wartość. Podczas wyszukiwania żądany klucz jest porównywany z kluczami w BST i jeśli zostanie znaleziony, jest pobierana powiązana wartość.

Poniżej znajduje się obrazowe przedstawienie BST -

Obserwujemy, że klucz węzła głównego (27) ma wszystkie klucze o niższej wartości w lewym poddrzewie, a klucze o wyższej wartości w prawym poddrzewie.

Podstawowe operacje

Oto podstawowe operacje na drzewie -

• Search - Przeszukuje element w drzewie.

• Insert - Wstawia element do drzewa.

• Pre-order Traversal - Przechodzi przez drzewo w sposób zamówiony w przedsprzedaży.

• In-order Traversal - Przechodzi przez drzewo w określonej kolejności.

• Post-order Traversal - Przechodzi przez drzewo po zamówieniu.

Węzeł

Zdefiniuj węzeł mający pewne dane, odniesienia do jego lewego i prawego węzła potomnego.

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

Operacja wyszukiwania

Zawsze, gdy chcesz przeszukać element, rozpocznij wyszukiwanie od węzła głównego. Następnie, jeśli dane są mniejsze niż wartość klucza, wyszukaj element w lewym poddrzewie. W przeciwnym razie wyszukaj element w prawym poddrzewie. Postępuj zgodnie z tym samym algorytmem dla każdego węzła.

Algorytm

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

Operacja wstawiania

Ilekroć chcesz wstawić element, najpierw zlokalizuj jego właściwe położenie. Rozpocznij wyszukiwanie od węzła głównego, a następnie jeśli dane są mniejsze niż wartość klucza, wyszukaj pustą lokalizację w lewym poddrzewie i wstaw dane. W przeciwnym razie wyszukaj pustą lokalizację w prawym poddrzewie i wstaw dane.

Algorytm

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