Почему RB-Tree не может быть списком?

Question

У меня проблема с rb-деревьями. согласно википедии, рб-дерево должно следовать следующему:

1. Узел красный или черный.
2. Корень черный. (Это правило используется в некоторых определениях, а не в других. Поскольку корень всегда можно изменить с красного на черный, но не обязательно наоборот, это правило мало влияет на анализ.)
3. Все листья черные.
4. Оба потомка каждого красного узла черные.
5. Каждый простой путь от данного узла к любому из его дочерних листьев содержит одинаковое количество черных узлов.

Как мы знаем, rb-дерево должно быть сбалансированным и иметь высоту O (log (n)). Но, если мы вставим растущий ряд чисел (1,2,3,4,5 ...) и теоретически мы получим дерево, которое будет выглядеть как список и будет иметь высоту O (n) со всеми узлы черные, что не противоречит свойствам rb-дерева, упомянутым выше. Так где я не прав ??

спасибо.

Answer 1

Ваш пример противоречит свойству № 5, поэтому оно не является допустимым красно-черным деревом.

Дерево у нас есть:

b(1, nil, b(2, nil, b(3, nil, b(4, nil, b(5, nil, nil)))))

Таким образом, чтобы добраться до последних двух листьев (дочерних элементов узла 5), нам нужно посетить пять черных узлов (представленных каждым b), чтобы добраться до листа под узлом 4, нам нужно посещение четырех черных узлов и т. д. Это означает, что существуют простые пути от корня до некоторых из этих потомков, содержащих различное количество черных узлов, что делает недействительным свойство 5.

Answer 2

Чуть дальше в статье :

Вставка начинается с добавления узла так же, как вставка двоичного дерева поиска делает и окрашивая его в красный .