Структура данных - двоичное дерево поиска

Дерево двоичного поиска (BST) - это дерево, в котором все узлы следуют следующим свойствам:

• Значение ключа левого поддерева меньше, чем значение ключа его родительского (корневого) узла.

• Значение ключа правого поддерева больше или равно значению ключа его родительского (корневого) узла.

Таким образом, BST делит все свои поддеревья на два сегмента; левое поддерево и правое поддерево и может быть определено как -

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