Упражнения: Бинарни Дървета за Търсене

Напредък

✅ Завършени: 0 / 0📊 Напредък: 0%

💡 Напредъкът се записва локално в браузъра

Този прогресивен набор от упражнения започва от основни концепции и постепенно достига до сложен анализ и дизайн. Студентите ще могат да:

Идентифицират и верифицират BST свойства (Упражнения 1-5)
Проследяват и предсказват дървовидни операции (Упражнения 6-10)
Имплементират основни функции (Упражнения 11-15)
Обработват сложни сценарии като изтриване (Упражнения 16-18)
Анализират сложност и проектират решения (Упражнения 19-25)

Лесни Упражнения - Фундаментални Концепции

Упражнение

10 minЛЕСНО

Задача 1: BST свойство

Кое от следните твърдения описва правилно свойството на Binary Search Tree (BST)?

A) Всички леви деца трябва да бъдат листа

B) За всеки възел, всички стойности в лявото му поддърво са по-малки от стойността на възела, а всички стойности в дясното поддърво са по-големи

C) Дървото трябва да бъде перфектно балансирано

D) Родителските възли винаги имат точно две деца

Отговор: B

BST свойството изисква всички стойности в лявото поддърво да са по-малки от корена, а всички в дясното - по-големи. Това е рекурсивно вярно за всяко поддърво.

Защо другите отговори са грешни:

A) Лявите деца не трябва да бъдат листа, те могат да имат свои деца
C) BST не изискват перфектно балансиране (макар че балансираните са по-ефективни)
D) Възлите могат да имат 0, 1 или 2 деца

Упражнение

10 minЛЕСНО

Задача 2: Валидиране на BST

Дадено е следното дърво, определете дали е валидно BST:

    10
   /  \
  5    15
 / \   / \
3  7  12 20

Отговорете с "Да" или "Не" и обяснете защо.

Отговор: Да

Това е валидно BST, защото:

За корена 10: лявото поддърво (3, 5, 7) < 10 < дясното поддърво (12, 15, 20)
За възел 5: 3 < 5 < 7
За възел 15: 12 < 15 < 20

Всяко поддърво удовлетворява BST свойството рекурсивно.

Упражнение

10 minЛЕСНО

Задача 3: Inorder обхождане

Какъв е изходът от inorder обхождане на BST от Упражнение 2? Напишете последователността от стойности.

Отговор: 3 5 7 10 12 15 20

Inorder обхождането следва реда: ляво–корен–дясно

Стъпки:

Посети лявото поддърво на 10: обходи 5 и неговите деца (3, 5, 7)
Посети корена: 10
Посети дясното поддърво на 10: обходи 15 и неговите деца (12, 15, 20)

Важно: Inorder обхождането на BST винаги произвежда сортирана последователност!

Упражнение

10 minЛЕСНО

Задача 4: TreeNode структура

В следната C++ TreeNode структура, идентифицирайте какво представлява всеки член:

class TreeNode {
public:
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

Отговор:

int value: Данните, съхранявани във възела (в този случай цяло число)
TreeNode* left: Указател към лявото дете на възела
TreeNode* right: Указател към дясното дете на възела
Конструкторът TreeNode(int val): Инициализира value със стойността val и задава left и right на nullptr

Защо nullptr? Когато създаваме нов възел, той първоначално няма деца, затова указателите са nullptr (нулеви указатели).

Упражнение

10 minЛЕСНО

Задача 5: Обхождания на BST

Кой метод за обхождане (inorder, preorder или postorder) би произвел сортирана последователност от стойности от BST?

Отговор: Inorder (ляво–корен–дясно)

Обяснение: Поради BST свойството (ляво < корен < дясно), когато обхождаме в ред ляво–корен–дясно, посещаваме възлите в нарастващ ред на техните стойности.

Сравнение с другите обхождания:

Preorder (корен–ляво–дясно): Полезно за копиране на структурата на дървото
Postorder (ляво–дясно–корен): Полезно за изтриване на дървото (изтриваме децата преди родителя)

Упражнение

10 minЛЕСНО

Задача 6: Вмъкване в BST

Ако вмъкнете стойностите 5, 3, 7, 1, 9 в този ред в първоначално празно BST, нарисувайте получената структура на дървото.

Отговор:

Стъпки на вмъкване:

Вмъкване 5: става корен
Вмъкване 3: 3 < 5, отива наляво от 5
Вмъкване 7: 7 > 5, отива надясно от 5
Вмъкване 1: 1 < 5, отива наляво; 1 < 3, отива наляво от 3
Вмъкване 9: 9 > 5, отива надясно; 9 > 7, отива надясно от 7

Средно-Лесни Упражнения - Основни Операции

Упражнение

10 minЛЕСНО

Задача 7: Упражнение 7

Попълнете липсващия базов случай в тази функция за търсене:

node* search(node* root, int key) {
    // Попълнете базовия случай тук
    if (key < root->key)
        return search(root->left, key);
    else
        return search(root->right, key);
}

Отговор:

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);
}

Обяснение на базовия случай:

!root: Ако корена е nullptr, стигнали сме до края на дървото без да намерим ключа
root->key == key: Намерихме възела с търсения ключ

Връщаме root във всеки случай - nullptr ако не сме намерили, или указател към възела ако сме намерили.

Упражнение

10 minЛЕСНО

Задача 8: Упражнение 8

Каква е времевата сложност на търсене на стойност в балансирано BST с n възли? А в напълно изродено (небалансирано) BST?

Отговор:

Балансирано BST: O(log n)

При балансирано дърво, височината е приблизително log₂(n)
На всяка стъпка елиминираме половината от дървото
Подобно на бинарно търсене в масив

Изродено BST: O(n)

Изроденото дърво е всъщност свързан списък
Трябва да проверим всеки възел в най-лошия случай
Губим предимството на дървовидната структура

Пример за изродено дърво:

Упражнение

15 minСРЕДНО

Задача 9: Упражнение 9

Дадено е това BST, проследете пътя, който се взема при търсене на стойността 12:

    15
   /  \
  10   20
 / \   / \
5  12 18 25

Отговор:

Път: 15 → 10 → 12

Стъпки:

Започваме от корена (15): 12 < 15, отиваме наляво
Стигаме до 10: 12 > 10, отиваме надясно
Стигаме до 12: 12 == 12, намерихме го!

Брой сравнения: 3

Обяснение: Използваме BST свойството на всяка стъпка, за да решим да отидем наляво или надясно, което ни води директно към търсената стойност.

Упражнение

15 minСРЕДНО

Задача 10: Упражнение 10

Идентифицирайте коя от следните последователности би създала изродено BST, ако се вмъкне в реда:

A) 5, 3, 7, 2, 8

B) 1, 2, 3, 4, 5

C) 4, 2, 6, 1, 3

D) 10, 5, 15, 3, 7

Отговор: B) 1, 2, 3, 4, 5

Обяснение: Когато вмъкваме елементи в сортиран ред (нарастващ или намаляващ), BST деградира до свързан списък.

Получена структура за B:

Защо другите не са изродени:

A, C, D: Имат елементи в случаен/полусортиран ред, което създава по-балансирана структура

Важно: Това е основният проблем с наивни BST и причината да са необходими самобалансиращи се дървета!

Средни Упражнения - Имплементация и Анализ

Упражнение

15 minСРЕДНО

Задача 11: Упражнение 11

Напишете итеративната версия на функцията за търсене в BST (лекцията показа рекурсивна). Функцията трябва да връща указател към възела, ако е намерен, или nullptr, ако не е.

Отговор:

node* searchIterative(node* root, int key) {
    // Обхождаме дървото докато не стигнем края или намерим ключа
    while (root != nullptr && root->key != key) {
        if (key < root->key)
            root = root->left;
        else
            root = root->right;
    }

    return root; // nullptr ако не е намерен, указател към възела ако е намерен
}

Обяснение:

Използваме while цикъл вместо рекурсия
Продължаваме докато не стигнем nullptr (края на дървото) или намерим ключа
На всяка итерация се движим наляво или надясно според BST свойството

Предимства на итеративната версия:

Избягва overhead от рекурсивни извиквания
Няма риск от препълване на стека при дълбоки дървета

Упражнение

15 minСРЕДНО

Задача 12: Упражнение 12

Разгледайте тази последователност от вмъквания в празно BST: 50, 30, 70, 20, 40, 60, 80

a) Нарисувайте получената структура на дървото

b) Каква е височината на това дърво?

c) Колко листа има?

Отговор:

a) Структура на дървото:

        50
       /  \
     30    70
    / \    / \
  20  40  60  80

b) Височина: 2

Височината се измерва от корена до най-далечното листо
Път от корена: 50 → 30 → 20 (2 ребра = височина 2)
Алтернативно, броим нивата: ниво 0 (50), ниво 1 (30, 70), ниво 2 (20, 40, 60, 80)

c) Брой листа: 4

Листата са възлите без деца: 20, 40, 60, 80

Забележка: Това е перфектно балансирано BST - всички възли имат две деца, освен листата!

Упражнение

15 minСРЕДНО

Задача 13: Упражнение 13

Обяснете какво би се случило, ако се опитате да изтриете възел със стойност 30 от това BST. Кой случай (лист, едно дете, две деца) се прилага?

Отговор:

Случай: Възел с две деца

Обяснение: Възел 30 има две деца (20 и 40), така че трябва да използваме най-сложния случай на изтриване.

Стъпки за изтриване:

Намерете inorder наследника на 30 (минималната стойност в дясното поддърво)
- Дясното поддърво на 30 е само 40
- Минималната стойност е 40
Заменете стойността на 30 със 40:

    50
   /  \
  40   70
 / \
20 40  (този 40 трябва да се изтрие)

Изтрийте оригиналния възел със стойност 40 (който сега е дублиран)
- Този възел е лист, лесно се изтрива

Краен резултат:

Алтернатива: Можехме да използваме inorder предшественика (максимума в лявото поддърво, т.е. 20).

Упражнение

15 minСРЕДНО

Задача 14: Упражнение 14

Имплементирайте функция findMax(), която връща максималната стойност в BST:

node* findMax(node* root) {
    // Вашата имплементация тук
}

Отговор:

node* findMax(node* root) {
    // Празно дърво
    if (root == nullptr)
        return nullptr;

    // Максималната стойност е в най-дясното листо
    while (root->right != nullptr) {
        root = root->right;
    }

    return root;
}

Обяснение:

В BST максималната стойност винаги е в най-дясното листо
Следваме дясните указатели докато не стигнем възел без дясно дете
Симетрично, минималната стойност е в най-лявото листо

Рекурсивна версия:

node* findMaxRecursive(node* root) {
    if (root == nullptr || root->right == nullptr)
        return root;

    return findMaxRecursive(root->right);
}

Сложност: O(h), където h е височината на дървото

O(log n) за балансирано дърво
O(n) за изродено дърво

Упражнение

15 minСРЕДНО

Задача 15: Упражнение 15

Дебъгнете тази дефектна функция за вмъкване. Идентифицирайте и коригирайте грешката:

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;
}

Отговор:

Проблем: Функцията не присвоява резултата от рекурсивното извикване обратно към указателите 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;
}

Защо е необходимо присвояването:

Когато вмъкваме в празно поддърво, insert връща указател към новия възел
Трябва да запазим този указател в root->left или root->right
Без присвояването, новият възел се създава, но никога не се свързва с дървото!

Последствие от грешката: Всички вмъквания след първото ще се "загубят" - новите възли ще се създадат, но няма да са част от дървото (изтичане на памет!).

Средно-Трудни Упражнения - Сложни Операции

Упражнение

15 minСРЕДНО

Задача 16: Упражнение 16

Имплементирайте функция за броене на общия брой възли в BST:

int countNodes(node* root) {
    // Вашата имплементация тук
}

Отговор:

int countNodes(node* root) {
    // Базов случай: празно дърво има 0 възела
    if (root == nullptr)
        return 0;

    // Броим: текущия възел (1) + възлите в лявото + възлите в дясното поддърво
    return 1 + countNodes(root->left) + countNodes(root->right);
}

Обяснение:

Използваме рекурсия за обхождане на цялото дърво
За всеки възел: 1 (текущ) + брой в ляво + брой в дясно
Базовият случай: nullptr връща 0

Проследяване на пример:

    5
   / \
  3   7
 /
2

countNodes(5) = 1 + countNodes(3) + countNodes(7)
              = 1 + (1 + countNodes(2) + countNodes(null)) + (1 + 0 + 0)
              = 1 + (1 + (1 + 0 + 0) + 0) + 1
              = 1 + (1 + 1) + 1
              = 4

Сложност:

Време: O(n) - посещаваме всеки възел веднъж
Пространство: O(h) - дълбочина на рекурсията = височина на дървото

Упражнение

20 minТРУДНО

Задача 17: Упражнение 17

Дадено е следното BST, ръчно извършете изтриването на възел 50 (който има две деца), използвайки метода с inorder наследник. Покажете всяка стъпка:

      50
     /  \
   30    70
  / \   / \
20 40 60 80
       \
       65

Отговор:

Стъпка 1: Идентифицираме, че 50 има две деца (30 и 70)

Стъпка 2: Намираме inorder наследника на 50

Inorder наследникът е минималната стойност в дясното поддърво
Отиваме надясно към 70, после винаги наляво: 70 → 60
60 няма ляво дете, затова 60 е inorder наследникът

Стъпка 3: Заменяме стойността на 50 със 60:

      60  ← заменено
     /  \
   30    70
  / \   / \
20 40 60 80  ← този 60 трябва да се изтрие
       \
       65

Стъпка 4: Изтриваме оригиналния възел 60 от дясното поддърво

Възел 60 има едно дете (65)
Свързваме родителя на 60 (възел 70) с детето на 60 (възел 65)

Краен резултат:

      60
     /  \
   30    70
  / \   / \
20 40 65 80

Обяснение: Този метод запазва BST свойството, защото inorder наследникът винаги е по-голям от всички възли в лявото поддърво и по-малък или равен на всички възли в дясното поддърво.

Упражнение

20 minТРУДНО

Задача 18: Упражнение 18

Напишете функция, която определя дали дадено бинарно дърво е валидно BST. Имайте предвид, че трябва да проверите BST свойството за ВСИЧКИ възли, не само за непосредствените деца:

bool isValidBST(node* root, int minVal, int maxVal) {
    // Вашата имплементация тук
}

Отговор:

#include <limits> // за INT_MIN и INT_MAX

bool isValidBST(node* root, int minVal, int maxVal) {
    // Базов случай: празното дърво е валидно BST
    if (root == nullptr)
        return true;

    // Текущият възел трябва да е в диапазона (minVal, maxVal)
    if (root->key <= minVal || root->key >= maxVal)
        return false;

    // Рекурсивно проверяваме лявото и дясното поддърво
    // Ляво поддърво: всички стойности трябва да са < root->key
    // Дясно поддърво: всички стойности трябва да са > root->key
    return isValidBST(root->left, minVal, root->key) &&
           isValidBST(root->right, root->key, maxVal);
}

// Помощна функция за извикване с начални стойности
bool isValidBST(node* root) {
    return isValidBST(root, INT_MIN, INT_MAX);
}

Защо е необходим диапазонът (minVal, maxVal)?

Погледнете този невалиден пример:

Ако проверим само непосредствените деца:

5 < 10 < 15 ✓
12 < 15 < 20 ✓

Но 12 > 10, което нарушава BST свойството! Възел 12 е в дясното поддърво на 10, затова трябва да е > 10.

Проследяване:

isValidBST(10, -∞, +∞)
  → 10 е в диапазона (-∞, +∞) ✓
  → isValidBST(5, -∞, 10) ∧ isValidBST(15, 10, +∞)
    → 5 в (-∞, 10) ✓
    → 15 в (10, +∞) ✓
    → isValidBST(12, 10, 15)
      → 12 в (10, 15) ✓

Сложност:

Време: O(n) - посещаваме всеки възел веднъж
Пространство: O(h) - стек на рекурсията

Трудни Упражнения - Напреднали Приложения и Анализ

Упражнение

20 minТРУДНО

Задача 19: Упражнение 19

Анализирайте пространствената сложност на рекурсивната функция за вмъкване. Ако вмъкнете n елемента в BST:

a) Каква е пространствената сложност в най-добрия случай (балансирано дърво)?

b) Каква е пространствената сложност в най-лошия случай (изродено дърво)?

c) Обяснете защо пространствената сложност се различава между тези случаи.

Отговор:

a) Най-добър случай (балансирано дърво): O(log n)

При балансирано дърво, височината h ≈ log₂(n). Всяко рекурсивно извикване на insert() добавя рамка към стека на извикванията. Максималната дълбочина на рекурсията е равна на височината на дървото.

b) Най-лош случай (изродено дърво): O(n)

При изродено дърво (по същество свързан списък), височината h = n. Ако вмъкваме елемент, който отива в най-дълбокия лист, рекурсията ще достигне дълбочина n.

c) Обяснение на разликата:

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

Балансирано:           Изродено:
      4                   1
     / \                   \
    2   6                   2
   / \ / \                   \
  1  3 5  7                   3
                               \
Височина: 2 (≈log₂7)            4
O(log n) пространство            \
                                  5
                               Височина: 4 (= n-1)
                               O(n) пространство

Важно: Това е пространството за стека на извикванията, не за съхранение на възлите. Самите възли заемат O(n) памет и в двата случая.

Итеративната имплементация: Изисква само O(1) допълнително пространство (без стек на извикванията), но е по-сложна за писане.

Упражнение

20 minТРУДНО

Задача 20: Упражнение 20

Имплементирайте функция за намиране на k-тия най-малък елемент в BST без използване на допълнително пространство за съхранение (подсказка: използвайте inorder обхождане с брояч):

void kthSmallestHelper(node* root, int k, int& count, int& result) {
    // Вашата имплементация тук
}

int kthSmallest(node* root, int k) {
    int count = 0;
    int result = -1;
    kthSmallestHelper(root, k, count, result);
    return result;
}

Отговор:

void kthSmallestHelper(node* root, int k, int& count, int& result) {
    // Базов случай или ако вече сме намерили резултата
    if (root == nullptr || count >= k)
        return;

    // Обхождаме лявото поддърво (по-малките елементи)
    kthSmallestHelper(root->left, k, count, result);

    // Посещаваме текущия възел
    count++;
    if (count == k) {
        result = root->key;
        return;
    }

    // Обхождаме дясното поддърво (по-големите елементи)
    kthSmallestHelper(root->right, k, count, result);
}

int kthSmallest(node* root, int k) {
    int count = 0;
    int result = -1;
    kthSmallestHelper(root, k, count, result);
    return result;
}

Обяснение:

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

Пример:

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

k = 3

Inorder: 2, 3, 4, 5, 6, 7, 8
count:   1  2  3  4  5  6  7
                ↑
         k-тият най-малък е 4

Проследяване за k=3:

Обхождаме наляво до 2: count=1
Обхождаме до 3: count=2
Обхождаме надясно до 4: count=3, намерихме го!

Защо използваме референция (&):

count и result са референции, за да могат да се променят във всички рекурсивни извиквания
Без референции, всяко извикване ще има собствено копие

Оптимизация: Проверката count >= k в началото спира излишното обхождане след намирането на резултата.

Сложност:

Време: O(k) - спираме след k-тия елемент
Пространство: O(h) - дълбочина на рекурсията

Упражнение

20 minТРУДНО

Задача 21: Упражнение 21

Дадени са BST и две стойности k1 и k2 (където k1 < k2), напишете функция, която извежда всички ключове в диапазона [k1, k2] в сортиран ред. Оптимизирайте решението си, за да избегнете посещаване на възли извън диапазона:

void printRange(node* root, int k1, int k2) {
    // Вашата имплементация тук
}

Отговор:

void printRange(node* root, int k1, int k2) {
    // Базов случай: празно дърво
    if (root == nullptr)
        return;

    // Ако текущата стойност е > k1, може да има елементи в лявото поддърво
    if (root->key > k1)
        printRange(root->left, k1, k2);

    // Ако текущата стойност е в диапазона, извеждаме я
    if (root->key >= k1 && root->key <= k2)
        cout << root->key << " ";

    // Ако текущата стойност е < k2, може да има елементи в дясното поддърво
    if (root->key < k2)
        printRange(root->right, k1, k2);
}

Обяснение на оптимизацията:

Вместо да обхождаме цялото дърво (O(n)), използваме BST свойството за подрязване (pruning):

Не отиваме наляво ако root->key <= k1 (всички елементи наляво ще са < k1)
Не отиваме надясно ако root->key >= k2 (всички елементи надясно ще са > k2)

Пример:

       10
      /  \
     5    20
    / \   / \
   3  7  15 25

printRange(root, 7, 20):

Проследяване:

Започваме от 10: 7 <= 10 <= 20, извеждаме 10
- Отиваме наляво (защото 10 > 7)
  - Възел 5: не извеждаме (5 < 7)
    - Отиваме надясно към 7 (защото 5 < 20)
      - Възел 7: извеждаме 7
- Отиваме надясно (защото 10 < 20)
  - Възел 20: извеждаме 20
    - Отиваме наляво към 15 (защото 20 > 7)
      - Възел 15: извеждаме 15

Изход: 7 10 15 20 (в сортиран ред!)

Сложност:

Време: O(m + h), където m е броят елементи в диапазона, h е височината
Пространство: O(h) - стек на рекурсията

Упражнение

20 minТРУДНО

Задача 22: Упражнение 22

Предизвикателство за управление на паметта: Напишете функция за изтриване на цялото BST и освобождаване на цялата заделена памет. Използвайте postorder обхождане, за да осигурите изтриване на децата преди родителя:

void deleteBST(node*& root) {
    // Вашата имплементация тук
}

Отговор:

void deleteBST(node*& root) {
    // Базов случай: празно дърво
    if (root == nullptr)
        return;

    // Postorder обхождане: ляво - дясно - корен
    deleteBST(root->left);   // Изтриваме лявото поддърво
    deleteBST(root->right);  // Изтриваме дясното поддърво

    // Сега изтриваме текущия възел
    delete root;
    root = nullptr;  // Добра практика: занулявам указателя
}

Защо Postorder?

Трябва да изтрием децата преди родителя, за да избегнем изтичане на памет и висящи указатели.

Грешен подход (Preorder):

// ГРЕШНО!
delete root;         // Изтриваме корена първо
deleteBST(root->left);  // УПС! root вече е изтрит, root->left е невалиден!
deleteBST(root->right); // УПС! root->right също е невалиден!

Правилен подход (Postorder):

       5
      / \
     3   7
    / \
   2   4

Ред на изтриване: 2, 4, 3, 7, 5
(първо листата, накрая корена)

Защо използваме референция (node*&)?

Променяме самия указател root, не само стойността
root = nullptr актуализира оригиналния указател, не само локално копие
Полезно за външен код, който може да провери дали дървото е изтрито

Употреба:

node* myTree = buildTree();
deleteBST(myTree);
// myTree е сега nullptr

Сложност:

Време: O(n) - посещаваме всеки възел веднъж
Пространство: O(h) - дълбочина на рекурсията

Упражнение

20 minТРУДНО

Задача 23: Упражнение 23

Разгледайте сценарий, в който трябва да построите балансирано BST от сортиран масив от n елемента. Напишете функция, която конструира балансирано по височина BST от сортирания масив в O(n) време:

node* sortedArrayToBST(int arr[], int start, int end) {
    // Вашата имплементация тук
}

Отговор:

node* sortedArrayToBST(int arr[], int start, int end) {
    // Базов случай: невалиден диапазон
    if (start > end)
        return nullptr;

    // Средният елемент става корен (за балансиране)
    int mid = start + (end - start) / 2;

    // Създаваме корен с средния елемент
    node* root = new node{arr[mid], nullptr, nullptr};

    // Рекурсивно строим лявото и дясното поддърво
    root->left = sortedArrayToBST(arr, start, mid - 1);
    root->right = sortedArrayToBST(arr, mid + 1, end);

    return root;
}

// Помощна функция за извикване
node* sortedArrayToBST(int arr[], int n) {
    return sortedArrayToBST(arr, 0, n - 1);
}

Идея: Избираме средния елемент като корен, така че лявото и дясното поддърво са приблизително равни по размер.

Пример:

Масив: [1, 2, 3, 4, 5, 6, 7]
                 ↑
               mid=3 (стойност 4)

Създаваме:
        4
       / \
  [1,2,3] [5,6,7]

Рекурсивно:
        4
       / \
      2   6
     / \ / \
    1  3 5  7

Проследяване:

sortedArrayToBST([1,2,3,4,5,6,7], 0, 6)
  mid = 3, създаваме възел 4
  left = sortedArrayToBST([1,2,3,4,5,6,7], 0, 2)
    mid = 1, създаваме възел 2
    left = sortedArrayToBST([1,2,3,4,5,6,7], 0, 0)
      създаваме възел 1
    right = sortedArrayToBST([1,2,3,4,5,6,7], 2, 2)
      създаваме възел 3
  right = sortedArrayToBST([1,2,3,4,5,6,7], 4, 6)
    mid = 5, създаваме възел 6
    ...

Защо е балансирано:

На всяка стъпка разделяме масива на две приблизително равни части
Гарантира височина O(log n)
Всички пътища от корена до листата са с дължина log₂(n) ± 1

Сложност:

Време: O(n) - посещаваме всеки елемент веднъж
Пространство: O(log n) - дълбочина на рекурсията (балансирано дърво)

Приложение: Бърз начин за конвертиране на сортиран масив в ефективно търсещо дърво!

Упражнение

20 minТРУДНО

Задача 24: Упражнение 24

Задача за анализ на сложността: Имате три структури от данни, съдържащи n сортирани елемента:

Сортиран масив
Сортиран свързан списък
Балансирано BST

За всяка структура, определете времевата сложност за:

a) Търсене на конкретен елемент

b) Вмъкване на нов елемент, като се запазва сортираният ред

c) Изтриване на елемент, като се запазва сортираният ред

Създайте сравнителна таблица и обяснете коя структура е най-добра за кои сценарии.

Отговор:

Задача 25: Таблица на Сложността

Операция	Сортиран Масив	Сортиран Списък	Балансирано BST
Търсене	O(log n)*	O(n)	O(log n)
Вмъкване	O(n)	O(n)	O(log n)
Изтриване	O(n)	O(n)	O(log n)
Пространство	O(1) overhead	O(1) per node	O(1) per node

* Бинарно търсене

Задача 26: Подробно Обяснение

1. Сортиран Масив:

Търсене: O(log n) - Бинарно търсене благодарение на произволния достъп
Вмъкване: O(n) - Трябва да намерим позицията O(log n), после да преместим елементи O(n)
Изтриване: O(n) - Намираме елемента O(log n), после преместваме елементи O(n)

2. Сортиран Свързан Списък:

Търсене: O(n) - Линейно търсене (няма произволен достъп)
Вмъкване: O(n) - Трябва да обходим до правилната позиция O(n), после O(1) вмъкване
Изтриване: O(n) - Обхождане до елемента O(n), после O(1) изтриване

3. Балансирано BST:

Търсене: O(log n) - Двоично търсене по дървото
Вмъкване: O(log n) - Намираме позицията и вмъкваме
Изтриване: O(log n) - Намираме и изтриваме

Задача 27: Кога Да Използваме Коя Структура

Сортиран Масив:

✅ Само за четене или рядко променяне на данни
✅ Чести търсения
✅ Ограничена памет (няма overhead от указатели)
❌ Чести вмъквания/изтривания
Примери: Статични справочници, константни конфигурации

Сортиран Свързан Списък:

✅ Редки търсения
✅ Вмъкване/изтриване в началото
❌ Чести търсения
❌ Произволен достъп
Примери: Опашки с приоритет (наивна имплементация), undo/redo стекове

Балансирано BST:

✅ Чести търсения, вмъквания и изтривания
✅ Нужда от динамични данни
✅ Поддържане на сортиран ред
❌ Ограничена памет
Примери: Бази данни индекси, динамични речници, символни таблици в компилатори

Задача 28: Заключение

Балансираното BST е "златната среда" - предлага O(log n) за всички операции. Това го прави идеален за динамични приложения с чести операции за търсене, вмъкване и изтриване.

Упражнение

20 minТРУДНО

Задача 29: Упражнение 25

Дизайнерско предизвикателство: Създавате система за автокомплийт за търсачка, която трябва да:

Съхранява милиони думи ефективно
Поддържа бързи префиксни търсения (намиране на всички думи, започващи с "abc")
Обработва чести вмъквания на нови думи
Минимизира използването на памет

Би ли бил подходящ стандартен BST? Ако не, какви модификации или алтернативни дървовидни структури бихте предложили и защо? Обмислете дискусия за Tries, Ternary Search Trees или самобалансиращи се BST в отговора си.

Отговор:

Задача 30: Анализ на Стандартния BST

Стандартният BST НЕ е подходящ за система за автокомплийт. Ето защо:

Проблеми:

Префиксно търсене: O(n) - трябва да проверим всички думи
Няма споделяне на префикси: "cat", "car", "card" съхраняват "ca" три пъти
Деградация: Сортиран вход създава изродено дърво

Пример на неефективност:

Думи: "cat", "car", "card", "dog"

BST съхранява цели думи:
       "car"
       /   \
    "cat"  "dog"
           /
        "card"

Търсене на думи с префикс "ca": O(n) - трябва да проверим всички

Задача 31: Препоръчани Структури

1. Trie (Префиксно Дърво) - НАЙ-ДОБЪР ИЗБОР

Структура:

Предимства:

✅ O(k) търсене, където k е дължината на думата/префикса
✅ Префиксно търсене: O(k + m), където m е броят думи с този префикс
✅ Споделяне на префикси: "cat", "car", "card" споделят "ca"
✅ Автокомплийт: Намерете възела на префикса, после обходете поддървото

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

❌ Памет: Може да използва много памет за големи азбуки (26 указателя на възел за английски)

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

struct TrieNode {
    unordered_map<char, TrieNode*> children; // Оптимизирано с map
    bool isEndOfWord;
    string word; // Опционално: за бърз достъп до цялата дума
};

Префиксно търсене:

vector<string> autocomplete(TrieNode* root, string prefix) {
    // Намираме възела на префикса
    TrieNode* node = root;
    for (char c : prefix) {
        if (node->children.find(c) == node->children.end())
            return {}; // Префиксът не съществува
        node = node->children[c];
    }

    // DFS за намиране на всички думи с този префикс
    vector<string> results;
    dfs(node, prefix, results);
    return results;
}

2. Ternary Search Tree (TST) - ДОБРА АЛТЕРНАТИВА

Структура: Комбинация от BST и Trie

      c
     /|\
    a  d
   /|\ |
  t r  o
      g

Всеки възел има три указателя:

left: символи < текущия
equal: следващ символ в думата
right: символи > текущия

Предимства:

✅ По-малко памет от Trie (3 указателя вместо 26)
✅ Все още поддържа бързо префиксно търсене
✅ Добър компромис между памет и скорост

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

❌ Малко по-бавно от Trie за много дълги префикси

3. Самобалансиращ се BST (Red-Black Tree, AVL) - РЕЗЕРВЕН ИЗБОР

Подход: Съхраняваме думите като ключове

Предимства:

✅ O(log n) за основни операции
✅ Гарантирано балансиран
✅ По-малко памет от Trie

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

❌ Префиксно търсене: O(k * log n + m) - трябва да търсим всяка дума с префикса
❌ Няма споделяне на префикси

Оптимизация: Комбинирайте със стринг сравнение:

vector<string> prefixSearch(RedBlackTree& tree, string prefix) {
    vector<string> results;
    // Намираме първата дума >= prefix
    auto it = tree.lower_bound(prefix);
    // Итерираме докато намираме думи с префикса
    while (it != tree.end() && it->substr(0, prefix.length()) == prefix) {
        results.push_back(*it);
        ++it;
    }
    return results;
}

Задача 32: Препоръка за Система за Автокомплийт

Използвайте Trie с оптимизации:

Compressed Trie (Patricia Trie):
- Комбинирайте вериги от единични деца в един възел
- Намалява пространството
Кеширане на популярни префикси:
- Съхранявайте топ-k резултати за популярни префикси
- Значително намалява времето за отговор
Lazy Loading:
- Не зареждайте всички думи в паметта
- Използвайте дисково базирано Trie за много големи набори от данни
Хибриден подход:
- Trie за префиксно търсене
- BST за поддържане на честота/популярност на думите

Финална архитектура:

Trie (за префиксно търсене)
  +
Priority Queue (за ранкиране по популярност)
  +
Cache (за често търсени префикси)

Реални примери:

Google Search: Използва сложна комбинация от Tries, кеширане и машинно обучение
VSCode Autocomplete: Използва TST за балансиране на памет и скорост
Redis: Предлага Sorted Sets (BST подобни) за autocomplete функции

Обобщение

Тези упражнения прогресират от базова идентификация на концепции до сложен анализ и проектиране на решения. Студентите трябва да могат да:

✅ Идентифицират и верифицират BST свойства
✅ Проследяват и предсказват дървовидни операции
✅ Имплементират основни функции (търсене, вмъкване, изтриване)
✅ Обработват сложни сценарии като изтриване с две деца
✅ Анализират сложност и взимат дизайнерски решения
✅ Разпознават кога да използват BST и кога да изберат алтернативи

Прогресията на трудността гарантира, че студентите изграждат увереност, докато се предизвикват да прилагат концепциите по все по-сложни начини.

Напредък

Лесни Упражнения - Фундаментални Концепции​

Задача 1: BST свойство​

Задача 2: Валидиране на BST​

Задача 3: Inorder обхождане​

Задача 4: TreeNode структура​

Задача 5: Обхождания на BST​

Задача 6: Вмъкване в BST​

Средно-Лесни Упражнения - Основни Операции​

Задача 7: Упражнение 7​

Задача 8: Упражнение 8​

Задача 9: Упражнение 9​

Задача 10: Упражнение 10​

Средни Упражнения - Имплементация и Анализ​

Задача 11: Упражнение 11​

Задача 12: Упражнение 12​

Задача 13: Упражнение 13​

Задача 14: Упражнение 14​

Задача 15: Упражнение 15​

Средно-Трудни Упражнения - Сложни Операции​

Задача 16: Упражнение 16​

Задача 17: Упражнение 17​

Задача 18: Упражнение 18​

Трудни Упражнения - Напреднали Приложения и Анализ​

Задача 19: Упражнение 19​

Задача 20: Упражнение 20​

Задача 21: Упражнение 21​

Задача 22: Упражнение 22​

Задача 23: Упражнение 23​

Задача 24: Упражнение 24​

Задача 25: Таблица на Сложността​

Задача 26: Подробно Обяснение​

Задача 27: Кога Да Използваме Коя Структура​

Задача 28: Заключение​

Задача 29: Упражнение 25​

Задача 30: Анализ на Стандартния BST​

Задача 31: Препоръчани Структури​

1. Trie (Префиксно Дърво) - НАЙ-ДОБЪР ИЗБОР​

2. Ternary Search Tree (TST) - ДОБРА АЛТЕРНАТИВА​

3. Самобалансиращ се BST (Red-Black Tree, AVL) - РЕЗЕРВЕН ИЗБОР​

Задача 32: Препоръка за Система за Автокомплийт​

Обобщение​

Лесни Упражнения - Фундаментални Концепции

Задача 1: BST свойство

Задача 2: Валидиране на BST

Задача 3: Inorder обхождане

Задача 4: TreeNode структура

Задача 5: Обхождания на BST

Задача 6: Вмъкване в BST

Средно-Лесни Упражнения - Основни Операции

Задача 7: Упражнение 7

Задача 8: Упражнение 8

Задача 9: Упражнение 9

Задача 10: Упражнение 10

Средни Упражнения - Имплементация и Анализ

Задача 11: Упражнение 11

Задача 12: Упражнение 12

Задача 13: Упражнение 13

Задача 14: Упражнение 14

Задача 15: Упражнение 15

Средно-Трудни Упражнения - Сложни Операции

Задача 16: Упражнение 16

Задача 17: Упражнение 17

Задача 18: Упражнение 18

Трудни Упражнения - Напреднали Приложения и Анализ

Задача 19: Упражнение 19

Задача 20: Упражнение 20

Задача 21: Упражнение 21

Задача 22: Упражнение 22

Задача 23: Упражнение 23

Задача 24: Упражнение 24

Задача 25: Таблица на Сложността

Задача 26: Подробно Обяснение

Задача 27: Кога Да Използваме Коя Структура

Задача 28: Заключение

Задача 29: Упражнение 25

Задача 30: Анализ на Стандартния BST

Задача 31: Препоръчани Структури

1. Trie (Префиксно Дърво) - НАЙ-ДОБЪР ИЗБОР

2. Ternary Search Tree (TST) - ДОБРА АЛТЕРНАТИВА

3. Самобалансиращ се BST (Red-Black Tree, AVL) - РЕЗЕРВЕН ИЗБОР

Задача 32: Препоръка за Система за Автокомплийт

Обобщение