Comments 6
Нынче такое название недостаточно толерантно. Чёрные и белые списки уже запретили.
Интересно узнать, зачем вообще понадобилось такая структура как 2-3 дерево? Потому как если предположить, что корень может быть пуст, кажется, все остальное дерево может быть бинарным с не пустыми нодами. Пока читал думал, что может для экономии памяти на ссылки узлов. Или есть какой-то отдельный алгоритм именно под такую упаковку.
Свойства кчд действительно выходят такими из 2-3 дерева как свойства развернутой структуры на основе упакованной.
2-3 дерево классное, потому что не требует дополнительной метаинфы (и расхода памяти на нее) на хранение высоты или цвета. Плюс да, объединение двух узлов тоже экономит память и уменьшает высоту дерева, ускоряя поиск и обход (уменьшая стэк).
Мне не совсем понятно откуда берется сбалансированность 2-3 дерева
При добавлении всё совсем очевидно, так как добавление нового узла случается только когда в корень с двумя элеменами нужно добавить третий и он туда «не лезет». Сверху над всей конструкцией пристраивается новый корень с двумя поддеревьями, что оставляет дерево сбалансированным.
При удалении — сложнее, но идея та же: высота дерева либо не меняется, либо меняется за счёт объединения трёх вершин «на самом верху».
Понимаем красно-черное дерево. Часть 1. Введение