128 подписчиков
Очередные выводы недели:
Начнем с плюсов. Для реализации уникальной коллекции в срр, как и в будущем для словаря, пришлось вникнуть в строение красно-черных деревьев. Сама идея не сложная, берем двусвязный список и маркируем каждый узел цветом (черным или красным) и в зависимости от цвета либо меняем баланс узлов, чтобы слева и справа была одинаковая глубина поиска, либо добавляем новый элемент, если дерево сбалансированно.
НО на практике классический алгоритм применить оказалось трудно, поэтому я пошла искать дальше и нашла простой, а от этого по моему мнению гениальный, алгоритм Седжвика о балансировке левостороннего красно-черного дерева. В алгоритме мы всегда вставляем красный узел, меняем местами узлы, если левый узел и его левый узел красные, сразу меняем местами, если хотим добавить красный узел справа (т.е. всегда добавляем элементы слева, отсюда и название) и меняем цвета, если у вершины оба потомка красные. Получается реализация вставки всего с 3 условиями балансировки, что облегчает читаемость кода, плюс есть подробные объяснения. Осталось только решить проблему утечки в ключевом методе insert(), и можно спокойно наследовать структуру для Set.
#школа_21 #cpp
Около минуты
7 августа 2022