Красно-чёрное дерево
Красно-чёрное дерево (, ) — один из видов самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и позволяющее быстро выполнять основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».

Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимбаса и Р. Седжвика (1978). По словам Гимбаса, они использовали ручки двух цветов. По словам Седжвика, красный цвет лучше всех смотрелся на лазерном принтере.

Красно-чёрное дерево используется для организации сравнимых данных, таких как фрагменты текста или числа. Листовые узлы красно-чёрных деревьев не содержат данных, благодаря чему не требуют выделения памяти — достаточно записать в узле-предке в качестве указателя на потомка нулевой указатель. Однако, в некоторых реализациях для упрощения алгоритма могут использоваться явные листовые узлы.
Q623818
двоичных деревьев поиска
Concept
Q11197
логарифм
Concept
None
высоты дерева
UNK
None
узлов
UNK
None
основные операции
UNK
Q300159
Сбалансированность
Concept
Q66656
Рудольфа Байера
PER
None
Л. Гимбаса
UNK
Q92983
Р. Седжвика
PER
None
Листовые узлы
UNK
Q506496
Красно-чёрное дерево
Concept
Q506496
Красно-чёрное дерево
Concept
1978-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
1978
DATE
+1978^^http://www.w3.org/2001/XMLSchema#decimal
1978
NUMBER
discoverer or inventor