Красно-чёрное дерево
Материал из Википедии — свободной encyclopedia
Красно-чёрное дерево (англ. red-black tree, RB tree) — один из видов самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и позволяющее быстро выполнять основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
Красно-чёрное дерево | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Тип | дерево поиска | |||||||||||||||
Год изобретения | 1972 | |||||||||||||||
Автор | Рудольф Байер | |||||||||||||||
Сложность в О-символике | ||||||||||||||||
|
||||||||||||||||
Медиафайлы на Викискладе |
Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимбаса и Р. Седжвика (1978). По словам Гимбаса, они использовали ручки двух цветов[1]. По словам Седжвика, красный цвет лучше всех смотрелся на лазерном принтере[1][2].
Красно-чёрное дерево используется для организации сравнимых данных, таких как фрагменты текста или числа. Листовые узлы красно-чёрных деревьев не содержат данных, благодаря чему не требуют выделения памяти — достаточно записать в узле-предке в качестве указателя на потомка нулевой указатель. Однако в некоторых реализациях для упрощения алгоритма могут использоваться явные листовые узлы.