Изменения

[[Файл:RbtreeRBT.JPG‎|350px|thumb|Пример красно-чёрного дерева.]]'''Красно - чёрное дерево''' - самобалансирующееся двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" и "чёрный".

Одно из основных преимуществ красно-чёрных деревьев заключается в том, что процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, т.к. алгоритм поиска не зависит от аттрибута цвета узлов. Вращение поддеревьев не может выполнятся одновременно с поиском,но Также при вставке выполняется не более <tex>O(1)</tex> вращений.

 Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL (map, set, multiset, multimap) основаны на красно-чёрных деревьях. Легко видеть, что красно-чёрные деревья изометричны 2-3-4 B-деревьям.Каждый чёрный узел можно объединить с его красными потомками. Результирующий узел будет иметь не более трех ключей и не более четырех потомков.