49
правок
Изменения
Новая страница: «'''Красно - чёрное дерево''' - самобалансирующееся двоичное дерево поиска, в котором баланс о…»
'''Красно - чёрное дерево''' - самобалансирующееся двоичное дерево поиска, в котором баланс осуществляется на основе "цвета" узла дерева, который принимает только два значения: "красный" и "чёрный". При этом дерево должно удовлетворять следующим свойствам:
# Все листья дерева чёрные.
# Все сыновья красного узла чёрные.
# На каждой ветви дерева, идущей от корня к листу, число чёрных узлов одно и то же.
При этом все листья дерева являются фиктивными и не содержат данных. Число чёрных узлов между корнем и узлом называется '''чёрной высотой дерева.'''
# Все листья дерева чёрные.
# Все сыновья красного узла чёрные.
# На каждой ветви дерева, идущей от корня к листу, число чёрных узлов одно и то же.
При этом все листья дерева являются фиктивными и не содержат данных. Число чёрных узлов между корнем и узлом называется '''чёрной высотой дерева.'''
