Деревья бинарного поиска🌳

👋 Всем привет! 🔥🚀

-> Этот пост посвящен бинарным деревьям поиска🌳. Они представлены узлами, связанными между собой для моделирования иерархии, и эти узлы располагаются по правилу.

-> Я проведу вас через реализацию двоичного дерева поиска. Работа с деревьями требует знаний об указателях, расположении памяти в программе на языке Си, распределении памяти и хорошего понимания рекурсии.

-> Мы сосредоточимся на бинарном дереве поиска🌳, потому что это эффективная по времени структура данных. Мы называем его бинарным, потому что каждый узел может иметь не более двух дочерних элементов. Это дерево поиска, потому что в нем соблюдается определенное условие, которое гласит, что каждый узел со значением меньше корневого узла будет размещен слева от корневого узла, а каждый узел со значением больше корневого узла будет размещен справа от корневого узла. Это правило применяется рекурсивно для каждого правого поддерева и левого поддерева.

-> Поиск, доступ, вставка и удаление в бинарном дереве поиска🌳 обычно выполняются за O(log n). Но есть вероятность, что двоичное дерево поиска может иметь структуру, подобную связанному списку, и вышеупомянутые операции будут выполняться за O(n). Эта ситуация является недостатком древовидной структуры данных и возникает, когда каждый новый узел имеет либо меньшее значение, чем предыдущий, либо большее, чем предыдущий. Попробуйте нарисовать дерево двоичного поиска с такими значениями: 10, 9, 8, 7, 6, 5, 4 и с такими значениями: 4, 5, 6, 7, 8, 9, 10 и посмотрите, что получится.

-> К счастью, другая структура данных дерева🌳, AVL, является улучшением классических деревьев. AVL — это самобалансирующееся дерево, и благодаря балансировке мы избегаем ситуации, когда дерево может превратиться в связный список. Но это уже другая тема.

-> Мы можем реализовать деревья с более чем двумя дочерними элементами, но временная сложность не изменится. Изменится только основание логарифма, но это не имеет значения в сложности, поэтому, опять же, временная сложность будет O(log n) в лучшем случае и O(n) в худшем.

1. Первый шаг: создание типа данных Node.

Для работы с древовидной структурой данных нам необходимо создать новый тип данных, тип данных Node. Деревья🌳 используют узлы. Здесь мы определяем наш тип данных Node как имеющий три атрибута: беззнаковую длинную переменную — представляющую информацию для хранения (также это может быть любой примитивный или абстрактный тип данных. Для простоты я использовал примитивный тип данных), ссылка на левый дочерний элемент и ссылка на правый дочерний элемент.

struct Node
{
    unsigned long long data;
    Node* left;
    Node* right;
};

2. Второй шаг: создание переменных Node.

После того, как мы определили, как выглядит тип данных Node, нам нужно уметь создавать переменные этого типа. Мы работаем с кучей памяти, поэтому мы должны динамически выделять память для наших новых узлов — оператор new запрашивает память размером с наш тип данных. Затем мы инициализируем атрибут данных и ссылки. Ключевое слово nullptr было введено в C++, представляя 0 как адрес и только как адрес; nullptr — это ключевое слово с типом указателя. С другой стороны, NULL по умолчанию равен 0 и не всегда является указателем. Я напишу о разнице между nullptr и NULL в будущем. Поскольку мы работаем с указателями и находимся в C++, лучше использовать nullptr.

Node* CreateNode(unsigned long long Data)
{
    Node* newNode = new Node;

    newNode->data = Data;
    newNode->left = nullptr;
    newNode->right = nullptr;

    return newNode;
}

3. Третий шаг: вставка узлов

После того как мы определили, как выглядит наш тип данных Node, и убедились, что можем создавать переменные этого типа, нам нужно уметь размещать эти переменные таким образом, чтобы соблюдалось определение двоичного дерева поиска. Мы создадим функцию для вставки в дерево двоичного поиска. Я предпочитаю рекурсивный метод, так как он короче. Нам нужны два аргумента для этой функции: корневой узел и информация/объект, который нужно сохранить. Если корень равен null, то мы знаем, что пришло время создать новую переменную Node и вставить ее. Если значение информации/объекта больше значения фактического корневого узла, то переходим вправо, если нет, то переходим влево.

void InsertNode(Node*& Root, unsigned long long Data)
{
    if (Root == nullptr) Root = CreateNode(Data);
    else if (Data > Root->data) InsertNode(Root->right, Data);
    else InsertNode(Root->left, Data);
}

4. Четвертый шаг: печать двоичного дерева поиска

Мы создали тип данных Node, убедились, что можем генерировать переменные Node, и убедились, что можем правильно их вставлять. Теперь нам нужно подумать о том, как мы можем просматривать нашу структуру данных. Для этого нам нужно использовать алгоритмы обхода в глубину или обхода в ширину. Существует четыре возможных алгоритма: inorder, preorder, postorder и обход с порядком уровней. В данном примере я использую предварительный порядок.

void Print(Node* Root)
{
    if (Root)
    {
        cout << Root->data << ' ';
        Print(Root->left);
        Print(Root->right);
    }
}

Мы закончили. У нас есть все части для работы с двоичным деревом поиска.
Вот полный код🔥:

#include <iostream>
using namespace std;


struct Node
{
    unsigned long long data;
    Node* left;
    Node* right;
};


Node* CreateNode(unsigned long long Data)
{
    Node* newNode = new Node;

    newNode->data = Data;
    newNode->left = nullptr;
    newNode->right = nullptr;

    return newNode;
}


void InsertNode(Node*& Root, unsigned long long Data)
{
    if (Root == nullptr) Root = CreateNode(Data);
    else if (Data > Root->data) InsertNode(Root->right, Data);
    else InsertNode(Root->left, Data);
}


void Print(Node* Root)
{
    if (Root)
    {
        cout << Root->data << ' ';
        Print(Root->left);
        Print(Root->right);
    }
}


int main()
{
    Node* root = nullptr;
    unsigned long long i = 0, nodesNumber;
    cout << "Number of nodes to be added: "; cin >> nodesNumber; cout << 'n';

    while (i < nodesNumber)
    {
        unsigned long long number; cout << "Value of node: "; cin >> number; cout << 'n';
        InsertNode(root, number);
        ++i;
    }

    cout << "Binary search tree printed: "; Print(root);
    cout << 'n';

    return 0;
}

Это базовая структура. Я хотел дать вам основную идею. Мы также можем создать тип данных Tree🌳 и думать о Tree🌳 как об объекте с атрибутами, а не как о простой переменной с именем root. Но дальше вы можете улучшать/изменять эту реализацию по своему усмотрению. Не стесняйтесь исследовать.🗺️ и будьте любопытными.

❗Обзоры:

• Я сосредоточился на идее, а не на реальном сценарии, где нужно учитывать валидацию и другие вещи.

• Я использовал язык программирования C++.

• Эмануэль Русу👨🎓

• Вы можете посетить мой GitHub

• Или вы можете найти меня на Linkedin

• Следующая тема: Внутренняя репрезентация примитивных типов данных

• Увидимся в следующий раз! 👋