98
правок
Изменения
Нет описания правки
Т.к. общее время выполнения каждой из операций порядка высоты дерева ,то все они выполняются за <tex>O(\log{n})</tex>.
== Преимущество красно-чёрных деревьев ==Одно из основных преимуществ красно-чёрных деревьев заключается в том, что процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, т.к. алгоритм поиска не зависит от аттрибута цвета узлов. Вращение поддеревьев не может выполнятся одновременно с поиском,но при вставке выполняется не более <tex>O(1)</tex> вращений. Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL (map, set, multiset, multimap) основаны на красно-чёрных деревьях. Легко видеть, что красно-чёрные деревья изометричны 2-3-4 B-деревьям.Каждый чёрный узел можно объединить с его красными потомками. Результирующий узел будет иметь не более трех ключей и не более четырех потомков. ==Ссылки.==
* [http://rain.ifmo.ru/cat/view.php/vis/trees/red-black-2002 Визуализатор]
