Remote Training on Programming

Бинарное дерево поиска является красно-черным деревом,  если оно удовлетворяет следующим свойствам:

             – каждый узел покрашен либо в черный, либо в красный цвет

             – корень дерева является черным

             – каждый лист дерева (NIL) является черным

             – если узел – красный, то оба его дочерних узла – черные

             – для каждого узла все пути от него  до листьев, являющихся потомками данного узла, содержат одно и то же количество черных вершин.

 

    Необходимо найти черную высоту красно-черного дерева (т.е. максимальное число черных узлов на пути от корня до какого-либо листа).

 

Входные данные

 

Элементы (ключи) дерева (целые числа), разделённые пробелами или переводами строк. Ввод элементов дерева завершается после ввода нуля. Число элементов не превышает 10000.

Элементы при вводе могут повторяться, но если элемент уже имеется в дереве, он никак не учитывается.

 

Выходные данные

 

Черная высота красно-черного дерева (целое число)

 

Пример входных данных

 

9 2 44

35 47 2

1 41

0

 

Пример выходных данных

 

3

 

Рисунок для пояснения примера

 

Автор: Абраменко Т.Д.