Двійкове дерево пошуку (Binary Search Tree (BST))

Дерево, Tree, Алгоритм

Двійкове дерево пошуку - це структура даних, яка дозволяє підтримувати відсортований список чисел.

• Двійковим (бінарним) деревом називається, тому що кожен вузол дерева має максимально два дочірні елементи.
• Дерево пошуку, тому що його можна використовувати для пошуку числа в O(log(n)) time (алгоритм з тимчасовою складністю T(n) = O(log(n))(прим.ред.)).

Властивості, що відрізняють двійкове дерево пошуку від звичайного двійкового дерева:

1. Всі вузли лівого піддерева менше кореневого вузла.
2. Всі вузли правого піддерева більше кореневого вузла.
3. Обидва поддерева кожного вузла також є BST, тобто. вони мають дві вищезгадані властивості.

Двійкове дерево праворуч не є двійковим деревом пошуку, тому що праве піддерево вузла "3" містить значення, яке менше його.

Є дві основні операції, які ви можете виконувати у двійковому дереві пошуку:

1. Перевірка, чи є число у двійковому дереві пошуку.

Алгоритм залежить від властивості BST так, що, якщо кожне ліве поддерево має значення нижче кореневого, то кожне праве поддерево має значення вище кореневого.

Якщо значення нижче кореневого, ми можемо з упевненістю сказати, що значення знаходиться не в правому піддереві, а значить, нам варто шукати його в лівому піддереві.
І навпаки, якщо значення вище за кореневе, напевно, що значення знаходиться не в лівому піддереві, а отже потрібно шукати в правому.

Алгоритм:

If root == NULL 
    return NULL;
If number == root->data 
    return root->data;
If number < root->data 
    return search(root->left)
If number > root->data 
    return search(root->right)

Спробуймо візуалізувати алгоритм за допомогою діаграми.

Якщо значення знайдено, ми повертаємо значення, щоб воно поширювалося кожному кроці рекурсії, як показано нижче.

Ви могли помітити, що ми викликали функцію return search (struct node) чотири рази. Коли ми повертаємо або новий вузол, або NULL, значення повертається знову і знову, доки search (root) не поверне остаточний результат.

Якщо значення не знайдено, ми зрештою досягаємо лівого або правого нащадка кінцевого вузла, який дорівнює NULL, і він поширюється та повертається.

2. Вставка значення у двійкове дерево пошуку (BST)

Вставка значення в правильну позицію аналогічна пошуку, тому що ми намагаємося відповідати правилу, згідно з яким ліве піддерево менше кореневого, а праве піддерево більше кореневого.

Ми продовжуємо йти або до правого піддерева, або до лівого в залежності від значення, а коли ми досягаємо точки, де ліве або праве піддерево дорівнює нулю, ми поміщаємо туди новий вузол.

Алгоритм:

If node == NULL 
    return createNode(data)
if (data < node->data)
    node->left  = insert(node->left, data);
else if (data > node->data)
    node->right = insert(node->right, data);  
return node;

Алгоритм не такий простий, як здається. Спробуймо візуалізувати, як ми додаємо число до існуючого BST.

Ми приєднали вузол, але нам все ще потрібно вийти з функції, не завдаючи шкоди решті дерева. Ось де return node (поворотний вузол) наприкінці знадобиться. У цьому випадку NULL, новостворений вузол повертається і приєднується до батьківського вузла, в іншому випадку той самий вузол повертається без будь-яких змін, поки ми не повернемося до кореневого вузла.

Це гарантує, що коли ми повернемося вгору деревом, з'єднання з іншими вузлами не зміняться.

Повний код для вставки та пошуку в BST мовою програмування C наведено нижче:

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node* left;
    struct node* right;
};

struct node* createNode(value){
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}


struct node* insert(struct node* root, int data)
{
    if (root == NULL) return createNode(data);

    if (data < root->data)
        root->left  = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);   

    return root;
}

void inorder(struct node* root){
    if(root == NULL) return;
    inorder(root->left);
    printf("%d ->", root->data);
    inorder(root->right);
}


int main(){
    struct node *root = NULL;
    root = insert(root, 8);
    insert(root, 3);
    insert(root, 1);
    insert(root, 6);
    insert(root, 7);
    insert(root, 10);
    insert(root, 14);
    insert(root, 4);

    inorder(root);
}

Виведення програми

1 ->3 ->4 ->6 ->7 ->8 ->10 ->14 ->