Порядок вставки для наихудшего случая черная высота красного черного дерева

Question

Допустим, что мы имеем дело с ключами 1-15. Чтобы получить наихудшую производительность обычного BST, вы должны вставлять ключи в порядке возрастания или убывания следующим образом:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Тогда BST по существу станет связанным списком.

Для лучшего случая BST вы должны вставлять ключи в следующем порядке, они устроены таким образом, что следующая введенная клавиша составляет половину от общего диапазона, который должен быть вставлен, поэтому первый из них равен 15/2 = 8, а затем 8/2 = 4 и т.д. ...

8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15

Тогда BST будет хорошо сбалансированным деревом с оптимальной высотой 3.

Самый лучший вариант для красного черного дерева также можно построить с лучшим корпусом из BST. Но как мы строим худший случай для красного черного дерева? Это то же самое, что в худшем случае для BST? Существует ли конкретный шаблон, который даст худший случай?

Answer 1

Вы не сможете. Красно-черное дерево сохраняет себя «густым», поэтому оно будет вращаться, чтобы исправить дисбаланс. Длина вашего наихудшего случая для Red-Black Tree ограничена двумя элементами, но это все еще не «плохой» случай; это то, что ожидается, поскольку lg (2) = 1, и у вас есть 1 слой за корнем с двумя элементами. Как только вы добавите третий элемент, вы получите следующее:

B     B 
\    /\ 
    R  =>  R R 
    \ 
    R 

Answer 2

Вы ищете тощее дерево, не так ли? Это можно сделать, вставив [1 ... , 2^(n+1)-2] в обратном порядке.