Как стать автором
Обновить

Комментарии 6

Нынче такое название недостаточно толерантно. Чёрные и белые списки уже запретили.

Интересно узнать, зачем вообще понадобилось такая структура как 2-3 дерево? Потому как если предположить, что корень может быть пуст, кажется, все остальное дерево может быть бинарным с не пустыми нодами. Пока читал думал, что может для экономии памяти на ссылки узлов. Или есть какой-то отдельный алгоритм именно под такую упаковку.


Свойства кчд действительно выходят такими из 2-3 дерева как свойства развернутой структуры на основе упакованной.

B-tree являются самобалансирующимися деревьями и проще в реализации, чем red-black tree.

2-3 дерево классное, потому что не требует дополнительной метаинфы (и расхода памяти на нее) на хранение высоты или цвета. Плюс да, объединение двух узлов тоже экономит память и уменьшает высоту дерева, ускоряя поиск и обход (уменьшая стэк).

Мне не совсем понятно откуда берется сбалансированность 2-3 дерева

Её поддерживают, очевидно. Ваш КО.
При добавлении всё совсем очевидно, так как добавление нового узла случается только когда в корень с двумя элеменами нужно добавить третий и он туда «не лезет». Сверху над всей конструкцией пристраивается новый корень с двумя поддеревьями, что оставляет дерево сбалансированным.
При удалении — сложнее, но идея та же: высота дерева либо не меняется, либо меняется за счёт объединения трёх вершин «на самом верху».
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.