Trees, Binary Trees, BSTs и Balanced Trees: Представяне и Основни Операции

▶⚡ Накратко

За Изпита

🎯Учебни Цели

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

✓Разберете tree структурите и техните класификации
✓Представете trees в паметта използвайки linked structures
✓Имплементирайте core BST операции
✓Анализирайте time и space complexity на BST операциите
✓Приложете BSTs за решаване на практически проблеми

1. Въведение и Мотивация

💡Защо дърветата са важни?

Когато datasets растат в size и complexity, традиционните linear структури като arrays и linked lists разкриват своите ограничения:

Arrays: Бърз random access, но insertions/deletions включват shifting на елементи
Linked Lists: Ефективни insertions/deletions, но бавен element access

Trees преодоляват тези ограничения! Като йерархични, nonlinear структури, дърветата свързват nodes по начини, които позволяват ефективен достъп, insertion и deletion—без memory shifts.

1.1. Performance Comparison

ℹ️Logarithmic vs Linear Performance

Ключова идея: Милион-елементно linear search: до 1 милион проверки Balanced tree search: само около 20 проверки!

Dataset Size	Linear Search	Balanced Tree Search
1,000	1,000 операции	10 операции
1,000,000	1,000,000 операции	20 операции
1,000,000,000	1,000,000,000 операции	30 операции

✅Предимства на Balanced Trees

В balanced trees, search, insertion и deletion могат да се извършат в O(log n) време!

Това е драматично подобрение спрямо O(n) на linear structures.

1.2. Real-World Applications

File Systems

Директорни структури са tree-shaped

Навигацията е бърза благодарение на йерархичната организация

Database Indices

B-trees и B+ trees за бързи lookups в огромни datasets

Използвани в MySQL, PostgreSQL, MongoDB

Document Object Model

HTML страници като дървета

Позволява ефективна манипулация на елементи

Machine Learning

Decision trees за classification

Random forests комбинират множество дървета

2. Преговор: Pointers, Dynamic Memory и Recursion

2.1. Pointers и Dynamic Memory

ℹ️Основи на Pointer

Pointers позволяват на nodes да референцират други nodes.

Dynamic memory (new, delete) позволява на trees да растат/свиват at runtime.

Null pointers маркират празни children (leaves).

// Заделяне на памет за node
Node* newNode = new Node(42);

// Използване
std::cout << newNode->data << std::endl;

// Освобождаване
delete newNode;
newNode = nullptr;  // Важно!

2.2. Structs и Node Representation

struct TreeNode {
    int data;
    TreeNode *left, *right;

    // Constructor
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

✅Използване на -> Operator

Използвайте -> за достъп до members чрез pointer
node->data е equivalent на (*node).data

2.3. Recursion Fundamentals

💡Защо Recursion е естествена за Trees?

Trees са рекурсивни по природа: всяко subtree е само по себе си tree!

Почти всички tree операции (traversal, insertion, deletion) са изразени рекурсивно.

// Пример: Compute tree height рекурсивно
int height(TreeNode* node) {
    // Base case: празно дърво
    if (node == nullptr) return 0;

    // Recursive case
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);

    return 1 + std::max(leftHeight, rightHeight);
}

3. Tree Structures и Терминология

3.1. Основни Дефиниции

ℹ️Tree Terminology

Основни концепции:

Tree: Колекция от nodes, свързани в йерархия (no cycles, един root)
Root: Най-горният node (без parent)
Parent/Child: Parent се свързва към child чрез edge
Siblings: Nodes със същия parent
Leaf: Node без children
Internal node: Нито root, нито leaf
Subtree: Всеки node плюс всички негови descendants
Height: Най-дългият път от node до leaf
Depth: Разстоянието от root до конкретен node

3.2. Binary Trees

ℹ️Какво е Binary Tree?

Binary tree: Всеки node има най-много два children (left/right).

Видове Binary Trees:

Full Binary Tree

Всеки node има 0 или 2 children

Няма nodes с точно 1 child

Complete Binary Tree

Всички levels са пълни освен възможно най-долното

Запълнено отляво надясно

Balanced Binary Tree

Left и right subtree heights се различават с най-много 1

Важно за performance!

3.3. Binary Search Tree (BST) Invariant

ℹ️BST Property - Най-важното правило!

За всеки node:

Всички стойности в left subtree са < node value
Всички стойности в right subtree са > node value

Това свойство е рекурсивно вярно за всички descendants!

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

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

✅ Valid BST:

Node 50: left (20, 30, 40) < 50 < right (60, 70, 80)
Node 30: left (20) < 30 < right (40)
Node 70: left (60) < 70 < right (80)

⚠️Често Срещана Грешка!

Не е достатъчно да проверите само immediate children!

BST invariant важи рекурсивно за всички descendants.

Пример за невалиден BST:

    10
   /  \
  5    15
      /  \
     6   20

Грешка: 6 < 10, но е в right subtree на 10!

4. Memory Representation на Trees

4.1. Linked Structure (Pointers)

ℹ️Най-често използвана в C++

Flexible и dynamic - най-популярният подход за BST implementation.

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Създаване на nodes
Node* root = new Node(50);
root->left = new Node(30);
root->right = new Node(70);
root->left->left = new Node(20);
root->left->right = new Node(40);

✅Предимства

Flexible shape - може да бъде всякаква форма
Nodes са dynamically created
Subtrees могат да растат/свиват independently
Естествено за recursive operations

4.2. Array Representation

ℹ️Подходящ за Complete Trees

Root на index 0:

Left child: 2i + 1
Right child: 2i + 2
Parent: (i - 1) / 2

// Array representation на binary tree
int tree[100];

// Root
tree[0] = 50;

// Children на root
tree[1] = 30;  // Left child:  2*0+1 = 1
tree[2] = 70;  // Right child: 2*0+2 = 2

// Children на node 1 (30)
tree[3] = 20;  // Left child:  2*1+1 = 3
tree[4] = 40;  // Right child: 2*1+2 = 4

Linked Structure

✅ Flexible shape ✅ Dynamic size ❌ Pointers needed ❌ Memory overhead

Array Representation

✅ No pointers needed ✅ Direct indexing ❌ Fixed size ❌ Wastes space in sparse trees

5. Tree Traversal: Foundation за BST Operations

Traversal е посещението на всеки node в specific order. Критично за searching, printing, copying и др.

5.1. Inorder Traversal (Left → Root → Right)

ℹ️Най-важен за BST!

BSTs: Inorder traversal произвежда nodes в ascending order!

Това е уникално свойство на BST.

void inorder(TreeNode* root) {
    if (root == nullptr) return;  // Base case

    inorder(root->left);              // Visit left subtree
    std::cout << root->data << " ";   // Visit root
    inorder(root->right);             // Visit right subtree
}

Пример:

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

Inorder output: 20 30 40 50 60 70 80  (sorted! ✓)

5.2. Други Traversals

Preorder

Root → Left → Right

void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

Използване: Copy tree structure

Inorder

Left → Root → Right

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

Използване: Sorted output за BST

Postorder

Left → Right → Root

void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

Използване: Delete tree (deallocate)

6. Core BST Operations

6.1. Insertion Operation

ℹ️Алгоритъм за Insertion

Принцип: Navigate downward от root, comparing на всяка стъпка.

Go left за по-малки стойности
Go right за по-големи стойности
Insert на NULL позицията

Node* insert(Node* root, int key) {
    // Base case: празно дърво или намерена позиция
    if (root == nullptr) {
        return new Node(key);
    }

    // Recursive insertion
    if (key < root->data) {
        root->left = insert(root->left, key);
    } else if (key > root->data) {
        root->right = insert(root->right, key);
    }
    // Ако key == root->data, можем да игнорираме (no duplicates)

    return root;
}

✅BST Invariant

Винаги е запазен, тъй като всеки descendant е constrained от recursive comparisons!

6.2. Search Operation

ℹ️Подобно на Binary Search в Arrays

Complexity:

Balanced tree: O(log n)
Worst case (skewed): O(n)

bool search(Node* root, int key) {
    // Base case: празно дърво или намерен key
    if (root == nullptr) return false;
    if (root->data == key) return true;

    // Recursive search
    if (key < root->data) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

// Итеративна версия (по-ефективна за stack)
bool searchIterative(Node* root, int key) {
    while (root != nullptr) {
        if (root->data == key) return true;
        if (key < root->data) root = root->left;
        else root = root->right;
    }
    return false;
}

6.3. Deletion Operation

ℹ️Най-сложната операция - Три случая

Node is a leaf (no children)
Node has one child
Node has two children (най-сложен!)

Най-прост случай: Просто delete и update pointer към nullptr.

// В deletion функцията
if (root->left == nullptr && root->right == nullptr) {
    delete root;
    return nullptr;
}

Replace node с неговия child.

// Ако няма left child
if (root->left == nullptr) {
    Node* temp = root->right;
    delete root;
    return temp;
}

// Ако няма right child
if (root->right == nullptr) {
    Node* temp = root->left;
    delete root;
    return temp;
}

Стъпки:

Намерете inorder successor (smallest в right subtree)
Replace node със successor
Recursively delete successor

Защо inorder successor? Защото е следващата по-голяма стойност, което запазва BST property!

Node* minValue(Node* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

Node* deleteNode(Node* root, int key) {
    if (root == nullptr) return root;

    // Find the node
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        // Node found!

        // Case 1 & 2: Leaf or one child
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        }
        if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }

        // Case 3: Two children
        Node* temp = minValue(root->right);  // Inorder successor
        root->data = temp->data;             // Copy value
        root->right = deleteNode(root->right, temp->data);  // Delete successor
    }

    return root;
}

⚠️Memory Management

Винаги delete removed nodes в C++!

Внимавайте за:

Memory leaks (забравени delete)
Dangling pointers (използване след delete)

7. Complexity Analysis

ℹ️BST Operations Time Complexity

Operation	Best/Average (Balanced)	Worst (Skewed)
Search	O(log n)	O(n)
Insertion	O(log n)	O(n)
Deletion	O(log n)	O(n)
Traversal	O(n)	O(n)
Space	O(n)	O(n)

Ключов фактор: Tree height определя performance!

❌

❌ Degenerate BST (Skewed)

Sorted insertion: 1, 2, 3, 4, 5 1 \ 2 \ 3 \ 4 \ 5 Height = n All operations: O(n)

Деградира до linked list!

✅

✅ Balanced BST

Balanced insertion: 3, 1, 5, 2, 4 3 / \ 1 5 \ / 2 4 Height = log n All operations: O(log n)

Optimal performance!

8. Защо Balanced Trees са Важни

8.1. The Degeneracy Problem

⚠️Проблемът с Degeneration

Ако данните пристигат в sorted или almost-sorted ред, BST може да стане linked list.

Това води до:

Драматично по-бавни операции - O(n) instead of O(log n)
Губене на всички предимства на tree structure

8.2. Self-Balancing Trees

ℹ️Решението

Production системите изискват predictably бързи операции дори на unpredictable данни.

Self-balancing trees (AVL, Red-Black):

Извършват rotations или "tree surgery" след updates
Запазват tree height на O(log n)
Гарантират O(log n) operations независимо от input order

8.3. Популярни Self-Balancing Trees

AVL Trees

Strict balancing:

Height difference ≤ 1 за всеки node
Faster searches (more balanced)
Slower insertions (more rotations)

Използване: Когато search е critical

Red-Black Trees

Relaxed balancing:

Nodes са червени или черни
По-малко rotations
Faster insertions

Използване: C++ STL (std::map, std::set)

AVL Balance Factor: height(left) - height(right)

Allowed values: -1, 0, 1

     Balanced (AVL):          Unbalanced:
          10                       10
         / \                      /
        5   15                   5
       / \                      /
      2   7                    2
                              /
     Balance factors:        1
     10: 0                 (violation!)
     5:  0
     15: 0

Rotations restore balance when violations occur.

Properties:

Every node е червен или черен
Root е черен
All leaves (NULL) са черни
Червен node има черни children
All paths от node до leaves имат същия брой черни nodes

       10(B)
      /     \
    5(R)   15(B)
   /  \    /
  2(B) 7(B) 12(R)

Гарантира: Height ≤ 2 log(n + 1)

9. Practical Applications

9.1. In-Memory Database Index

💡Бърз Lookup

Problem: Efficiently map keys (напр. имена) към records (напр. телефонни номера).

Solution: Balanced BST ensures O(log n) lookup и insertion.

struct Record {
    std::string name;
    std::string phone;
};

class DatabaseIndex {
private:
    std::map<std::string, Record> index;  // Red-Black tree

public:
    void insert(const std::string& name, const Record& record) {
        index[name] = record;  // O(log n)
    }

    Record* search(const std::string& name) {
        auto it = index.find(name);  // O(log n)
        if (it != index.end()) {
            return &(it->second);
        }
        return nullptr;
    }
};

9.2. Dynamic Sorting (Tree Sort)

ℹ️Tree Sort Algorithm

Insert всички елементи в BST
Inorder traversal за sorted output

Complexity:

Balanced: O(n log n)
Unbalanced: O(n²)

void treeSort(std::vector<int>& arr) {
    Node* root = nullptr;

    // Insert all elements (O(n log n) if balanced)
    for (int val : arr) {
        root = insert(root, val);
    }

    // Inorder traversal for sorted output
    int index = 0;
    function<void(Node*)> inorder = [&](Node* node) {
        if (node == nullptr) return;
        inorder(node->left);
        arr[index++] = node->data;
        inorder(node->right);
    };

    inorder(root);
}

✅Кога да Използвате Tree Sort?

Когато данните пристигат over time
Когато трябва да правите additional queries (медиани, ranges)
Когато искате online sorting (sort as you insert)

10. Резюме и Ключови Изводи

ℹ️Основни Точки

BST Fundamentals:

BST invariant: Left < Node < Right (рекурсивно)
Операции: Insert, Search, Delete, Traverse
Inorder traversal → sorted output

Complexity:

Balanced trees: O(log n) за search, insert, delete
Skewed trees: O(n) - деградират до linked list
Height е ключов фактор за performance

Balanced Trees:

AVL Trees: Strict balancing (fast search)
Red-Black Trees: Relaxed balancing (fast insert)
Guarantee: O(log n) operations независимо от input

Applications:

Database indexing
File systems
Dynamic sorting
In-memory indices

Често Срещани Грешки

⚠️Common Pitfalls

Ignoring balancing → води до slow operations
Incorrect deletion с two children → използвайте inorder successor
Memory leaks → винаги delete nodes
Failing to maintain BST invariant → проверявайте след modifications
Stack overflow от deep recursion → използвайте iterative versions

Best Practices

✅Препоръки

Always validate BST property след updates
Consider balancing от началото за large datasets
Write both recursive and iterative versions
Carefully handle duplicate keys и edge cases
Use STL (std::map, std::set) за production code
Test with diverse inputs: random, sorted, reverse-sorted

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

💡Продължете Изучаването

Study AVL Trees и Red-Black Trees за production-ready implementations
Explore B-trees и B+ trees за disk-based databases
Practice on LeetCode/HackerRank за BST problems
Implement balancing сами за по-дълбоко разбиране
Compare performance на balanced vs unbalanced trees

11. Практически Задачи

Създайте пълна BST имплементация с:

insert(int val)
search(int val)
deleteNode(int val)
inorder(), preorder(), postorder()
height()
isValidBST()

Имплементирайте tree sort
Сравнете с quicksort и mergesort
Test с:
- Random data
- Sorted data
- Reverse-sorted data
Analyze результатите

Напишете функция int getBalance(Node* root) която:

Изчислява balance factor за node
Идентифицира unbalanced nodes
Предлага rotations за балансиране

Имплементирайте vector<int> rangeQuery(Node* root, int min, int max):

Връща всички стойности в [min, max]
Използва BST property за ефективност
Complexity: O(log n + k), където k е броят results

Референции

"Data Structures and Algorithms in C++" textbooks

Balanced Trees Туториали

AVL Trees - GeeksforGeeks - Insertion и балансиране
Red-Black Tree - Wikipedia - Детайлно обяснение
Self-Balancing Binary Search Trees - Общ преглед
AVL Tree Tutorial - Programiz - С код и визуализации

Визуализация и Анимация

Visualgo - BST Visualization - Интерактивна визуализация на балансиране
AVL Tree Visualization - Стъпка по стъпка операции
Red-Black Tree Visualization - Визуално представяне

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

AVL Tree Implementation in C++ - Deletion операции
Red-Black Tree Implementation - Пълна имплементация
Balanced BST Operations - Алгоритми

C++ STL

std::map Documentation - Използва Red-Black Tree
std::set Documentation - Балансирана имплементация
C++ Ordered Containers - STL map и set

Академични Ресурси

MIT OpenCourseWare - Binary Search Trees - Академични лекции
Stanford CS166 - Balanced Trees - Advanced Data Structures

Сравнение и Анализ

AVL vs Red-Black Trees - Stack Overflow дискусия
Performance Comparison - Кога да използваме кое

Практика

Balanced Tree Problems - LeetCode - Задачи за практика
AVL Tree Problems - HackerRank

▶⚡ Накратко

🎯Учебни Цели

1. Въведение и Мотивация​

1.1. Performance Comparison​

1.2. Real-World Applications​

File Systems

Database Indices

Document Object Model

Machine Learning

2. Преговор: Pointers, Dynamic Memory и Recursion​

2.1. Pointers и Dynamic Memory​

2.2. Structs и Node Representation​

2.3. Recursion Fundamentals​

3. Tree Structures и Терминология​

3.1. Основни Дефиниции​

3.2. Binary Trees​

Full Binary Tree

Complete Binary Tree

Balanced Binary Tree

3.3. Binary Search Tree (BST) Invariant​

4. Memory Representation на Trees​

4.1. Linked Structure (Pointers)​

4.2. Array Representation​

Linked Structure

Array Representation

5. Tree Traversal: Foundation за BST Operations​

5.1. Inorder Traversal (Left → Root → Right)​

5.2. Други Traversals​

Preorder

Inorder

Postorder

6. Core BST Operations​

6.1. Insertion Operation​

6.2. Search Operation​

6.3. Deletion Operation​

7. Complexity Analysis​

❌ Degenerate BST (Skewed)

✅ Balanced BST

8. Защо Balanced Trees са Важни​

8.1. The Degeneracy Problem​

8.2. Self-Balancing Trees​

8.3. Популярни Self-Balancing Trees​