From c73c3187af1ba2e3bb7772429064a851086025f3 Mon Sep 17 00:00:00 2001 From: Desislava Shunina <115353472+desiish@users.noreply.github.com> Date: Tue, 26 Nov 2024 18:10:25 +0200 Subject: add pract08 --- Practicum/pract08/readme.md | 88 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 88 insertions(+) create mode 100644 Practicum/pract08/readme.md (limited to 'Practicum/pract08') 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, + class Allocator = std::allocator +> class set; +``` +- **Key** + Типът на обектите, които ще се съхраняват в множеството. + +- **Compare** + Функция или обект за сравнение, която определя критерия за сравнение между елементите. Това влияе върху начина, по който множеството подрежда елементите. + *По подразбиране:* Използва се стандартният оператор за сравнение за съответния тип (`std::less`). + +- **Allocator** + Механизъм за управление на паметта, който определя как ще се разпределя и освобождава паметта за елементите в множеството. + *По подразбиране:* Използва се стандартният алокатор `std::allocator`. + +Поддържа следните методи: +- **Добавяне на елементи**: `set.insert(value)` - O(logN) (връща pair); +- **Премахване на елементи**: `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, + class Allocator = std::allocator> + +> class map; +``` + +## `std::map` +std::map представлява дърво от двойки от ключ и стойност. Всеки ключ е уникален. + +- **Key** + Типът на обектите, които ще се съхраняват в множеството. + +- **T** + Типът на обектите, които ще се съхраняват в множеството. + +- **Compare** + Обект или функция за сравнение, която определя как ключовете се подреждат в контейнера. + *По подразбиране:* Използва се стандартният оператор за сравнение за съответния тип на ключа (`std::less`). + +- **Allocator** + Механизъм за управление на паметта, който определя как ще се разпределя и освобождава паметта за елементите в множеството. + *По подразбиране:* Използва се стандартният алокатор `std::allocator>`. + + Поддържа следните операции: +- **Добавяне на елементи**: `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/) -- cgit v1.3.1-26-gb76a