Что такое Красно-Чёрное дерево.

R5AM, Александр Ящук, Москва, 2022г.
На главную

Красно-Чёрное дерево - это сбалансированное бинарное дерево поиска, которое имеет дополнительную информацию в 1 бит для узла: цвет узла красный или чёрный. Для балансировки деревьев применяется операция Поворот дерева. Балансировка для красно-чёрного дерева достигается менее чем двумя поворотами после добавления элемента данных и не более чем тремя после его удаления. Худший дисбаланс красно-чёрного дерева может оказаться до 2 раз, то есть самый длинный путь в 2 раза длиннее самого короткого.

Бинарное дерево поиска - структура данных, имеющая высокую эффективность алгоритмов для поиска и сортировки.

Сбалансированность - для красно-чёрного дерева будет соблюдена, если самый длинный путь не более, чем в 2 раза длиннее самого короткого. Желательно, чтобы все пути в дереве от корня до листьев имели примерно одинаковую длину, то есть чтобы глубина и левого, и правого поддеревьев была примерно одинакова в любом узле. В противном случае теряется производительность.






На главную
К началу страницы