День 43 - Сбалансированные деревья. Красно-черное дерево, B-Trees 🤯

Закончил первую часть теории 5ой недели по сбалансированным деревьям. Теория довольно сложная и потребовала глубокого разбора.
Основные вещи, которые проходятся на неделе:

2-3 Trees
Очень важно разобрать данный вид деревьев, так как они является базой для понимания Красно-Черного дерева на основе деревьев бинарного поиска - Red-Black BST
Имлементировать данную DS не надо. Это займет очень много времени и сил и вы все-равно не запомните, так как операции удаления и вставки, имееют очень много операций трансформаций над деревом. Как, мне кажется, важно запомнить Time Complexity и понять базовый принцип работы структуры.

Red-Black Binary Search Trees
А вот тут стоит подготовить свою нервную систему. Готовьтесь к тому, что придется потратить пару дней для того, чтобы вкурить и понять эту DS. Основный принцип, что мы с помощью BST иммитируем структуру 2-3 дерева и все операции направлены на поддержание данной структуры. Как начать и не сдаться?

1. Берем первую и самую простую операцию - search. Здесь не требуется никаких изменений по-сравнению с обычным BST. Это обычный поиск по бинарному дереву. Имлементим данную операцию.

2. Понять, как связь между двумя линками помечается красной или черной. Посмотреть из теории 2-3 Дерева, что такое 3-node и 4-node. Научиться конвертировать 3-Node в бинарное дерево на листочке.

3. Освоить операции поворота узла влево и вправо (rotateLeft и rotateRight), которые используется для поддержания дерева сбалансированным. Это несложная операция, которая требует проработки на листочке или доске. Пару раз достаточно нарисовать все и будете вертеть узлы как шашлык 😁

4. Учимся превращать воображаемый 4-Node в 2 Node путем смены цвета связей между узлами. flipColors

5. Разбираемся с финальным боссом - insert. Там есть несколько кейсов, каждый кейс стоит разорать на листочке
- 2 левых узла красные h.left == RED && h.left.left == RED ( поворот направо )
- Правый красный, левый черный ( поворота налево )
- Левый и Правый красный ( смена цветов )

Посмотрите, как каждая операция поддерживает структуру нашего красно-черное дерево в виде 2-3 дерева. Как только в голове придет понимание как это все соотносится, будет на много легче ☺️ Я реально страдал, пока разбирался 😭

6. Есть операция, хуже финального босса - это удаление. У Сенджвика написано 2 научных работы о том, как удалять узлы из такого дерева. Лично мне кажется, это то, что можно пропустить и не пытаться разбирать. Алгоритм запомнить очень сложно, много условий, кода и трансформаций. Врятли после курса вы вспомните об этом методе и врятли на собеседовании вас попросят его написать 😁
Если очень интересно, в учебнике Сенджвика есть имлементация этого метода. Я ее даже прочел, но закрыл как страшный сон 🙈
Все предыдущие операции ( вставка. поиск, повороты ) дают 90% базы, о том, как работает данная структура данных, а нам важно умение применять и понимать, что применяешь.

Полезно, но опционально: B-Trees
В курсе также рассказыается про данный вид деревьев, которые активно применяются в базах данная и различных индексах. Для себя нашел эту тему полезной, так как неплохо расширяет кругозор. Сможете по-умничать и сказать, как устроен поиск по индексу в SQL базе данных 😁

Вот полезное видео на эту тему, одного просмотра достаточно для понимания:
https://www.youtube.com/watch?v=aZjYr87r1b8&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=77

Следующие шаги:
1. Geometric Applications of BST - звучит как жара 🔥
2. Последний ассаймент курса 🤯

Stay Tuned 👍

#algorithms_part_1, #bst, #red_black_tree, #week_5