Двоичное дерево поиска (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 ->
Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Поддержать автора Donate

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Как стать автором?

Внесите вклад в развитие сообщества EVILEG.

Узнайте, как стать автором сайта.

Изучить
Donate

Добрый день, Дорогие Пользователи !!!

Я Евгений Легоцкой, разработчик EVILEG. И это мой хобби-проект, который помогает учиться программированию другим программистам и разработчикам

Если сайт помог вам, и вы хотите также поддержать развитие сайта, то вы можете сделать пожертвование следующими способами

PayPalYandex.Money
Timeweb

Позвольте мне порекомендовать вам отличный хостинг, на котором расположен EVILEG.

В течение многих лет Timeweb доказывает свою стабильность.

Для проектов на Django рекомендую VDS хостинг

Посмотреть Хостинг Timeweb
g
29 мая 2020 г. 14:32
glushchenkoin

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:40баллов,
  • Очки рейтинга-8
АС
26 мая 2020 г. 11:29
Артём Сун-Дун-Чан

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:50баллов,
  • Очки рейтинга-4
МН
25 мая 2020 г. 11:33
Митя Нагибин

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:50баллов,
  • Очки рейтинга-4
Последние комментарии
31 мая 2020 г. 8:15
IscanderChe

Как установить OpenCV на Qt под Windows

Добавлю от себя: на Windows 10 x64 с MinGW 7.3.0 в CMake надо установить флаг OPENCV_ENABLE_ALLOCATOR_STATS=OFF, тогда всё скомпилится нормально.
29 мая 2020 г. 13:00
Евгений Легоцкой

Django - Урок 023. Like Dislike система с помощью GenericForeignKey

Думал так, но похоже что нет. {{ post.votes.likes.user.username }} Это же QuerySet будет, а не отдельный единственный объект {% for vote in post.votes %} {{ vote.user.username …
29 мая 2020 г. 11:43
Владислав Меленчук

Django - Урок 023. Like Dislike система с помощью GenericForeignKey

А как получить имя пользователя, который поставил лайк? Думал так, но похоже что нет. {{ post.votes.likes.user.username }}
29 мая 2020 г. 6:30
Евгений Легоцкой

Qt/C++ - Урок 039. Как закрасить строку в QSqlTableModel по значению в столбце

У меня работает. Исправлял в проекте, который приложен к статье. А что происходит в вашем коде, с учётом места вызова этого кода, я знать не могу ;) Дебажьте и добавляйте условия, кото…
Сейчас обсуждают на форуме
31 мая 2020 г. 6:57
Алексей Внуков

Минимальный размер Item

считайте по размеру включенных элементов, чтоб все помещалась. например у вас всего 2 кнопки, тогда минимальный размер итема будет ширина 1-й кнопки + ширина 2-й кнопки + отступы, и точно также …
f
31 мая 2020 г. 2:24
fryn3

Можно ли сделать в QML таблицу как в Excel?

Можно ли сделать в QML таблицу как в Excel или как сделано в QTableView? Что бы можно было выделять диапазон ячеек, переключатся по таб, изменять размеры строк и столбцов. В QT 5.14 по…
S
РС
30 мая 2020 г. 11:49
Руслан Склюев

QML Как при нажатии на кнопку изменить название окна?

У меня три файла: 1. QML - это Loader и Window 2. QML вход в программу - страница Loader (там есть Switch) 3. QML - MainMenu. Мне нужно в (1), чтобы если на (2) Switch.enable, то …
ДК
29 мая 2020 г. 13:27
Джон Кофи

QMap<> какой ключ лучше

это ясно. Вопрос в том, как быстро мапа будет отрабатывать, если ключом будет QModelIndex. Какой параметр индекса возьмет за ключ. И вот насколько это будет медленнее или быстрее, чем QString пр…
О нас
Услуги
© EVILEG 2015-2020
Рекомендует хостинг TIMEWEB