Skip to main content

Бинарни Дървета за Търсене: Концепции, Имплементация и Операции в C++

▶⚡ Накратко

За Изпита

🎯Учебни Цели

След края на тази лекция вие ще можете да:

  • ✓Разберете свойствата и структурата на бинарното дърво за търсене (BST)
  • ✓Имплементирайте BST възлова структура и основни операции в C++
  • ✓Извършвайте обхождане на дърво и търсене ефективно
  • ✓Обработвайте изтриване на възел в различни сценарии
  • ✓Анализирайте и сравнявайте сложността на BST операциите

1. Въведение и Мотивация за Бинарни Дървета за Търсене​

💡Защо дърветата са важни в компютърните науки?

Дърветата са фундаментална структура от данни, която поддържа йерархична организация на данните и ефективен достъп. Те са много повече от теоретични конструкции:

  • Файлови системи: Йерархии от папки и файлове
  • Бази данни: Индексиране (напр. B-trees, BST) позволява логаритмично търсене в огромни множества от данни
  • Парсване на изрази: Компилаторите използват дървета за представяне и оценка на синтаксиса на кода
  • Автокомплийт системи: Дърветата позволяват моментално търсене и предложения

Ограничения на масивите и свързаните списъци за сортирани данни​

Масиви

Предимства:

  • O(1) произволен достъп
  • Добра кеш локалност

Недостатъци:

  • O(n) вмъкване/изтриване (поради преместване)
  • Фиксиран размер

Свързани Списъци

Предимства:

  • O(1) вмъкване/изтриване на позната позиция
  • Динамичен размер

Недостатъци:

  • O(n) търсене
  • Не могат да използват бинарно търсене

BST (Бинарни Дървета за Търсене)

Предимства:

  • O(log n) операции (когато са балансирани)
  • Динамично управление на паметта

Недостатъци:

  • O(n) в най-лош случай (изродени дървета)
  • По-сложна имплементация
ℹ️Самобалансиращи се BST

Самобалансиращите се BST (напр. AVL, Red-Black) са от критично значение за поддържането на тази ефективност дори когато множеството от данни се променя.

Приложения на BST​

Алгоритми за Сортиране

Tree sort използва BST за сортиране на елементи

Таблици на Символи

Използват се в компилатори за съхраняване на променливи

Динамично Поддържане на Данни

Ефективно добавяне и премахване на сортирани данни

Основа за Напреднали Структури

Red-Black дървета, AVL дървета и др.

2. Преговор на Предпоставките за Бинарни Дървета за Търсене​

2.1. Указатели и динамична памет в C++​

BST изискват динамично заделяне на памет за възлите.

// Заделяне на памет за int
int* ptr = new int(45);
// Изтриване и зануляване на указателя
delete ptr;
ptr = nullptr;
⚠️Важно за Паметта
  • Използвайте new за заделяне, delete за освобождаване
  • За масиви: new[] и delete[]
  • Винаги избягвайте изтичане на памет и висящи указатели

2.2. Рекурсия и рекурсивни функции​

Рекурсията е естествена за дървета, тъй като всяко поддърво е само по себе си дърво.

Пример за рекурсивна структура:

void visit(node* n) {
    if (n == nullptr) return;
    visit(n->left);
    // Направете нещо с n
    visit(n->right);
}

2.3. Основни концепции за бинарни дървета​

ℹ️Терминология на Дърветата
  • Възел (Node): Основен елемент на дървото
  • Корен (Root): Най-горният възел
  • Родител (Parent), Дете (Child): Връзките между възлите
  • Лист (Leaf): Възел без деца
  • Поддърво (Subtree): Дърво, съставено от възел и неговите деца
  • Височина (Height): Най-дългият път от корена до листо
  • Дълбочина (Depth): Разстоянието от корена до даден възел

Бинарно дърво: Всеки възел има най-много две деца (ляво, дясно).

BST свойство: За всеки възел, стойностите в лявото поддърво < стойност на възела < стойности в дясното поддърво.

3. Свойства и Структура на BST: Основа за Ефективна Организация на Данните​

3.1. BST свойството за подредба​

✅BST Свойство

За всеки възел:

  • Ляво поддърво: всички стойности < стойност на възела
  • Дясно поддърво: всички стойности > стойност на възела

Това свойство е рекурсивно вярно за всяко поддърво.

Визуален пример:

    5
   / \
  3   7
 / \ / \
2  4 6  8

В това дърво:

  • Всички стойности в лявото поддърво на 5 (2, 3, 4) са < 5
  • Всички стойности в дясното поддърво на 5 (6, 7, 8) са > 5

3.2. C++ структура на възела​

class TreeNode {
public:
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};
ℹ️Характеристики на Структурата
  • Всеки възел съхранява указатели към своите деца
  • Расте динамично
  • Позволява ефективно рекурсивно обхождане

3.3. Визуално представяне​

💡Ментален Модел

BST може да се обходи inorder (ляво-корен-дясно) за да произведе сортиран изход.

Мислете за него: Като сортиран масив, но структуриран йерархично за ефективно вмъкване/търсене/изтриване.

4. Операция Вмъкване в BST​

4.1. Алгоритъм за вмъкване (Рекурсивен подход)​

  1. Сравнете стойността за вмъкване с текущия възел
  2. Ако е по-малка, рекурсия наляво; ако е по-голяма, рекурсия надясно
  3. Когато достигнете nullptr, вмъкнете новия възел

C++ Пример:

struct node {
    int key;
    node *left, *right;
};

node* insert(node* root, int key) {
    if (!root) return new node{key, nullptr, nullptr};

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

    return root;
}

4.2. Обработка на дублирани стойности​

ℹ️Дизайнерски Избор
  • Опция 1: Отхвърляйте дубликати
  • Опция 2: Поставяйте дубликатите последователно наляво или надясно

Изборът влияе на кода, но не на фундаменталния алгоритъм.

4.3. Сложност​

Балансирано Дърво

Характеристики:

  • Време: O(log n)
  • Пространство: O(h) където h ≈ log n

Изродено Дърво

Характеристики:

  • Време: O(n)
  • Пространство: O(h) където h = n

Проблем:

  • Деградира до свързан списък

5. Търсене и Обхождане в BST​

5.1. Операция Търсене​

Рекурсивна логика:

  1. Ако възелът е nullptr или съвпада с ключа, готово
  2. Ако ключ < възел, търсете наляво
  3. Ако ключ > възел, търсете надясно

C++ Пример:

node* search(node* root, int key) {
    if (!root || root->key == key) return root;

    if (key < root->key)
        return search(root->left, key);
    else
        return search(root->right, key);
}
✅Сложност по Време
  • Балансирано: O(log n)
  • Изродено: O(n)

5.2. Inorder обхождане​

Посещава възлите в ред ляво–корен–дясно ⇒ произвежда сортиран изход.

C++ Пример:

void inorder(node* root) {
    if (!root) return;

    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
}

Пример: За дървото по-горе, inorder обхождането ще изведе: 2 3 4 5 6 7 8

5.3. Други обхождания​

Preorder (Префиксно)

Ред: корен–ляво–дясно

Добро за копиране на дърво

Inorder (Инфиксно)

Ред: ляво–корен–дясно

Произвежда сортирана последователност

Postorder (Постфиксно)

Ред: ляво–дясно–корен

Добро за изтриване на дърво

6. Операция Изтриване в BST​

Изтриването е най-сложната операция в BST. Има три случая:

6.1. Случай 1: Изтриване на лист (без деца)​

Най-простият случай - просто изтрийте и актуализирайте указателя към nullptr.

Преди:     5           След:      5
          / \                    /
         3   7                  3
            / \                    \
           6   8                    8
ℹ️BST Свойството

BST свойството автоматично се запазва.

6.2. Случай 2: Изтриване на възел с едно дете​

Заобиколете възела, като свържете родителя с детето.

Преди:     5           След:      5
          / \                    / \
         3   7                  3   8
              \
               8

6.3. Случай 3: Изтриване на възел с две деца​

Заменете възела с неговия inorder наследник (минималната стойност в дясното поддърво), след това изтрийте наследника.

C++ Пример:

node* findMin(node* n) {
    while (n->left) n = n->left;
    return n;
}

node* deleteNode(node* root, int key) {
    if (!root) return nullptr;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        // Едно или нула деца
        if (!root->left) {
            node* temp = root->right;
            delete root;
            return temp;
        }
        if (!root->right) {
            node* temp = root->left;
            delete root;
            return temp;
        }

        // Две деца
        node* temp = findMin(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }

    return root;
}
⚠️Управление на Паметта

Винаги изтривайте премахнатите възли в C++, за да избегнете изтичане на памет и висящи указатели.

7. Анализ на Сложността: Най-добър, Среден и Най-лош Случай​

Таблица на Сложността​

ОперацияНай-добър/Среден (Балансирано)Най-лош (Небалансирано)
ТърсенеO(log n)O(n)
ВмъкванеO(log n)O(n)
ИзтриванеO(log n)O(n)
ПространствоO(n)O(n)
ℹ️Ключови Наблюдения
  • Височината на дървото определя ефективността
  • Изродени дървета (от сортиран вход) деградират BST до свързан списък
  • Пространствената сложност е O(n) за всички операции

Визуализация на Балансирано vs Изродено Дърво​

Балансирано (O(log n)):      Изродено (O(n)):
        4                            1
       / \                            \
      2   6                            2
     / \ / \                            \
    1  3 5  7                            3
                                          \
                                           4
                                            \
                                             5

8. Наивни Алгоритми и Детайли на Имплементацията​

8.1. Итеративна vs Рекурсивна имплементация​

Рекурсивна

Предимства:

  • По-ясен и елегантен код
  • Естествено следва структурата на дървото

Недостатъци:

  • Риск от препълване на стека при дълбоки дървета
  • Overhead от извикванията на функции

Итеративна

Предимства:

  • Избягва препълване на стека
  • Потенциално по-бърза

Недостатъци:

  • По-сложен код
  • По-труден за разбиране и поддръжка

8.2. Често срещани капани при имплементацията​

⚠️Внимавайте за Тези Грешки
  • Неправилни актуализации на указатели (причиняват счупени връзки)
  • Препълване на стека чрез рекурсия в дълбоки дървета
  • Изтичане на памет (неизтриване на възли)
  • Неправилна обработка на null указатели
  • Неуспех при обработка на гранични случаи: празно дърво, единичен възел, дубликати и др.
  • Наивният код лесно може да създаде изродени дървета; осведомеността и тестването са жизненоважни

8.3. Гранични случаи за обработка​

ℹ️Важни Гранични Случаи
  • Празно дърво (root == nullptr)
  • Единичен възел
  • Дублирани стойности
  • Търсене на несъществуваща стойност
  • Изтриване на корена
  • Сортиран входен ред (създава изродено дърво)

9. Приложения в Реалния Свят​

Индексиране в Бази Данни

B-Trees и B+ Trees използват BST концепции за масивни, дисково базирани данни

Оценка на Изрази

Йерархични дървовидни представяния на код в компилатори

Автокомплийт Системи

Бързи търсения в големи множества от думи и речници

Динамично Поддържане на Данни

Системи, където данните често се вмъкват/изтриват, като остават сортирани

10. Балансирани BST: Въведение и Мотивация​

Проблемът: Деградация до свързани списъци​

⚠️Най-лош Случай

Когато вмъкваме елементи в сортиран ред, BST деградира до свързан списък:

// Вмъкване на 1, 2, 3, 4, 5 в този ред
insert(root, 1);  // root
insert(root, 2);  //   \
insert(root, 3);  //    2
insert(root, 4);  //     \
insert(root, 5);  //      3
                  //       \
                  //        4
                  //         \
                  //          5

Резултат: O(n) производителност за всички операции!

Решение: Самобалансиращи се BST​

✅Напреднали BST Структури

Самобалансиращите се BST гарантират O(log n) време за операции, независимо от реда на вход, чрез автоматични ротации на дървото и инварианти.

Популярни самобалансиращи се дървета:

  • AVL дървета: Строго балансирани (разлика във височините ≤ 1)
  • Red-Black дървета: По-релаксирано балансирани, използвани в STL
  • Splay дървета: Адаптивни, често използваните елементи са близо до корена
  • Treaps: Комбинация от BST и heap
ℹ️За Бъдещи Лекции

Подробностите за самобалансиращите се дървета ще бъдат разгледани в следващи лекции. Засега, разберете защо са необходими!

11. Интерактивни Дейности и Упражнения​

Think–Pair–Share​

Задача: Проектирайте BST за специфичен сценарий от приложение (напр. телефонен указател, система за управление на инвентар).

Обсъдете:

  • Какви предимства предлага BST?
  • Какви са компромисите?
  • Кога BST би бил най-добрият избор?

Live Coding Trace​

Преподавателят демонстрира поредица от вмъквания и изтривания на живо, като нарисува трансформациите на дървото на дъската.

Студентите:

  • Предсказват резултата
  • Идентифицират BST свойството на всяка стъпка
  • Обсъждат сложността

Групова Дейност​

В малки групи имплементирайте липсваща BST операция (напр. изтриване) в C++. Тествайте и интегрирайте решението си.

Дискусия за Най-лош Случай​

Проследете създаването на изродено дърво и анализирайте сложността. Обсъдете необходимостта от балансиране.

12. Формативна Оценка и Exit Ticket​

Бърз Тест​

Въпрос 1: Кое от следните е валидно BST?

A)    5          B)    5          C)    5
     / \              / \              / \
    3   7            7   3            3   7
   / \              / \              / \ / \
  2   4            6   8            2  4 6  9

Въпрос 2: Каква е времевата сложност на търсене в балансирано BST с n възли?

  • A) O(1)
  • B) O(log n)
  • C) O(n)
  • D) O(n²)

Отговор 1: A и C са валидни BST. B не е, защото 7 > 5, но е в лявото поддърво.

Отговор 2: B) O(log n)

Exit Ticket​

Задача: Предвидете и обяснете структурата на BST след следната поредица от вмъквания:

insert(root, 5);
insert(root, 3);
insert(root, 7);
insert(root, 1);
insert(root, 9);

Обяснете как формата на дървото влияе на времевата сложност на операциите.

Debugging Challenge (Разширение)​

Намерете и коригирайте грешката в предоставения BST код:

node* insert(node* root, int key) {
    if (!root) return new node{key, nullptr, nullptr};
    if (key < root->key)
        insert(root->left, key);  // Грешка: не присвоява резултата!
    else
        insert(root->right, key); // Грешка: не присвоява резултата!
    return root;
}

Проблем: Рекурсивните извиквания не актуализират указателите.

Коригиран код:

node* insert(node* root, int key) {
    if (!root) return new node{key, nullptr, nullptr};
    if (key < root->key)
        root->left = insert(root->left, key);  // Коригирано
    else
        root->right = insert(root->right, key); // Коригирано
    return root;
}

13. Обобщение и Ключови Изводи​

✅Основни Точки за Запомняне
  1. BST свойството за подредба е от съществено значение за ефективно търсене, вмъкване и изтриване
  2. Рекурсивните алгоритми за търсене, вмъкване и изтриване са елегантни и следват структурата на дървото
  3. Най-лошата производителност може да бъде O(n); следователно балансираните BST са от решаващо значение за винаги ефективни операции
  4. BST са основа: овладяването им ви подготвя за напреднали структури от данни и приложения в реалния свят

Следващи Стъпки​

ℹ️Какво да Практикувате
  • Имплементирайте и манипулирайте BST в C++ - особено изтриване на възли и обхождания
  • Експериментирайте с различни редове на вмъкване и наблюдавайте формата на дървото
  • Изследвайте самобалансиращи се дървета (AVL, Red-Black) за гарантиране на производителност във всички случаи

Препратки за Допълнително Изучаване​

Допълнителни Ресурси​

Binary Search Tree Туториали​

Имплементация​

Визуализация​

Практика​

Приложения​

Въпроси?​

Нека обсъдим сценарии, кодови фрагменти или отстраним често срещани BST грешки заедно!