diff options
add pract08
1 files changed, 88 insertions, 0 deletions
| -rw-r--r-- | Practicum/pract08/readme.md | 88 |
diff --git a/Practicum/pract08/readme.md b/Practicum/pract08/readme.md new file mode 100644 index 0000000..52a2158 --- /dev/null +++ b/Practicum/pract08/readme.md @@ -0,0 +1,88 @@ +# Практикум №8 по Структури от данни, спец. ИС + +На семинари вече сте разгледали балансирани дървета. Едни много известни балансирани дървета са именно т.нар. Red-Black Trees. Те работят по малко по-различен начил от AVL. +Балансираността тук не е дефинирана чрез balance factor, а чрез редица свойства, които винаги трябва да са в сила (така наречения **инвариант**). + +Инвариантът на Red-Black Tree гласи: +1) Всеки възел има цвят - черен или червен + +2) Всеки NIL възел (празен възел) е черен + +3) Червен възел не може да има червен наследник + +4) Всеки път от произволен връх до всички NIL елементи в поддървото му трябва да преминава през равен брой черни върхове + +5) Коренът винаги е черен (не е задължително, но често се прилага) + +* Следствие: Ако произволен връх има точно 1 наследник, то той е червен + +Балансирането отново се извършва по време на самите операции за добавяне и премахване. Отново се разчита на принципа на ротациите, но също така има случаи в които вместо ротация се предпочита обикновенно преоцветяване на върховете. +[Визуализация на RB tree](https://ds2-iiith.vlabs.ac.in/exp/red-black-tree/red-black-tree-oprations/simulation/redblack.html) + +На базата на червено-черното дърво са имплеметирани 2 от най-използваните структури от данни - std::set и std::map. + +## `std::set` +std::set представлява дърво от уникални стойности, наречени ключове. +При създаване на обект от тип `std::set`, могат да се зададат три типа параметри: + +```c++ +template< + class Key, + class Compare = std::less<Key>, + class Allocator = std::allocator<Key> +> class set; +``` +- **Key** + Типът на обектите, които ще се съхраняват в множеството. + +- **Compare** + Функция или обект за сравнение, която определя критерия за сравнение между елементите. Това влияе върху начина, по който множеството подрежда елементите. + *По подразбиране:* Използва се стандартният оператор за сравнение за съответния тип (`std::less<Key>`). + +- **Allocator** + Механизъм за управление на паметта, който определя как ще се разпределя и освобождава паметта за елементите в множеството. + *По подразбиране:* Използва се стандартният алокатор `std::allocator<Key>`. + +Поддържа следните методи: +- **Добавяне на елементи**: `set.insert(value)` - O(logN) (връща pair<iterator, bool>); +- **Премахване на елементи**: `set.erase(value)`- O(logN) (връща колко елементи са били премахнати); +- **Премахване на елементи чрез итератор**: `set.erase(iterator)`- Θ(1) / O(logN) (връща итератор към следващия елемент); +- **Търсене на елементи**: `set.find(value);` - O(logN) (връща итератор или `set.end()`, ако не е намерен); +- **Проверка на размера**: `set.size()` - O(1) + +```c++ +template< + class Key, + class T, + class Compare = std::less<Key>, + class Allocator = std::allocator<std::pair<const Key, T>> + +> class map; +``` + +## `std::map` +std::map представлява дърво от двойки от ключ и стойност. Всеки ключ е уникален. + +- **Key** + Типът на обектите, които ще се съхраняват в множеството. + +- **T** + Типът на обектите, които ще се съхраняват в множеството. + +- **Compare** + Обект или функция за сравнение, която определя как ключовете се подреждат в контейнера. + *По подразбиране:* Използва се стандартният оператор за сравнение за съответния тип на ключа (`std::less<Key>`). + +- **Allocator** + Механизъм за управление на паметта, който определя как ще се разпределя и освобождава паметта за елементите в множеството. + *По подразбиране:* Използва се стандартният алокатор `std::allocator<std::pair<const Key, T>>`. + + Поддържа следните операции: +- **Добавяне на елементи**: `map[key] = value`- O(logN) +- **Достъп до елементи**: `map[key]` - O(logN) +- **Премахване на елементи**: `map.erase(key)` - O(logN) (връща колко елементи са били премахнати) +- **Премахване на елементи чрез итератор**: `map.erase(iterator)` - Θ(1) / O(logN) (връща итератор към следващия елемент) +- **Търсене на елементи**: `map.find(key)` - O(logN) (връща итератор или `map.end()`, ако не е намерен) +- **Проверка на размера**: `map.size()` - O(1) + +[Линк към задачите](https://leetcode.com/problem-list/a6culvq1/) |
