Двоичное дерево поиска (Binary Search Tree (BST))

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

Content

Двоичное дерево поиска - это структура данных, которая позволяет поддерживать отсортированный список чисел.

  • Двоичным (бинарным) деревом называется, потому что каждый узел дерева имеет максимально два дочерних элементов.
  • Деревом поиска, потому что его можно использовать для поиска числа в 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 ->
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
MN
May 25, 2020, 11:33 a.m.
Mitja Nagibin

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:50points,
  • Rating points-4
f
May 25, 2020, 5:05 a.m.
falcon

C++ - Test 001. The first program and data types

  • Result:66points,
  • Rating points-1
jm
May 25, 2020, 3:30 a.m.
just maks

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:80points,
  • Rating points4
Last comments
May 26, 2020, 6:51 a.m.
Evgenij Legotskoj

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

У вас база данных не открылась Исправьте путь к базе данных на свой корректный в следующих методах void DataBase::connectToDataBase() bool DataBase::openDataBase()
T1
T1
May 26, 2020, 6:22 a.m.
Tima 1

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

полностью повторил структору проекта. В форму дабавил tableView. Но при запуске получаю форму только с пустым tableView. Можете подсказать в чем пробелма?
May 26, 2020, 6:02 a.m.
Evgenij Legotskoj

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

Потому что это файл который нужно создать, а не библиотека. В статье есть содержание этого файла. Добавляйте в проект. Копируйте содержимое из статьи.
T1
May 26, 2020, 6 a.m.
Tima 1

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

не удается подключиить библеотеку include "database.h" выдает ошибку. Можете помочь?
Now discuss on the forum
May 26, 2020, 5:16 a.m.
BlinCT

Отсутствие драйвера SQLite в пакете Qt 4 на Linux

Вот честно непонимаю почему до сих пор используют qt4, там же столько всего отсутствует, много фишек и возможностей нету там. То есть используя такое старье приходится много писать самому а не и…
DK
May 26, 2020, 2:24 a.m.
Dzhon Kofi

Disable autoscroll

такие естественные решения все перепробовал. Получилось вчера так: const int maximumScroll = ui->_samples->verticalScrollBar()->maximum();const int sliderPos = ui->_samp…
May 26, 2020, 12:43 a.m.
Ruslan Polupan

Посоветуйте новичку (базы данных и Qt, что учить)

Без БД сейчас практически никуда. Поэтому SQL надо знать. SQLite самы простой вариант, но имхо лучще начать с бд клиент-сервер. Настроить сервер. Подключаться клиентом. Просто это помогает понят…
EJ
May 25, 2020, 2:42 p.m.
Esteban José María

Компиляция пустого проекта Qt Android

qt 5.12.8 BUILD SUCCESSFUL in 42s 28 actionable tasks: 28 executed Android package built successfully in 68.251 ms. Ну, буду разбираться по-тихоньку. :)
s
May 25, 2020, 1:24 p.m.
sander-007

Использование файлов в памяти (memory file mapping)

Добрый вечер, проблемы работы с файлом Exel нет вообще. Весь смысл в том чтобы не создавать на диске физический файл (требования безопасности), дабы потом не чистить. А так вопрос только в этом …
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB