Красно-чёрное дерево (удалить)

Материал из Викиконспекты
Версия от 08:07, 10 марта 2011; Efimenko (обсуждение | вклад) (Новая страница: «'''Красно - чёрное дерево''' - самобалансирующееся двоичное дерево поиска, в котором баланс о…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Красно - чёрное дерево - самобалансирующееся двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" и "чёрный". При этом дерево должно удовлетворять следующим свойствам:

  1. Все листья дерева чёрные.
  2. Все сыновья красного узла чёрные.
  3. На каждой ветви дерева, идущей от корня к листу, число чёрных узлов одно и то же.

При этом все листья дерева являются фиктивными и не содержат данных. Число чёрных узлов между корнем и узлом называется чёрной высотой дерева.