Изменения

Перейти к: навигация, поиск

Красно-черное дерево

392 байта убрано, 21:26, 24 марта 2012
Нет описания правки
== Преимущество красно-чёрных деревьев ==
Одно из основных преимуществ красно-чёрных деревьев заключается в том, что процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, т.к. алгоритм поиска не зависит от аттрибута оно использует всего 1 бит дополнительной памяти для хранения цвета узловвершины. Также при вставке выполняется не более <tex>O(1)</tex> вращений. Ещё одним достоинством красно-чёрного дерева является, то, что оно использует всего 1 бит дополнительной памяти для хранения цвета вершины.
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL (map, set, multiset, multimap) основаны на красно-чёрных деревьях.
98
правок

Навигация