Плотная верхняя граница для формирования $ n $-элемента красно-черное дерево с нуля

Question

Я узнал, что в порядок статистическое дерево (дополненное красно-черное дерево, в котором каждый узел $ x $ содержит дополнительное поле, обозначающее количество узлов в Субревное дерево укоренившись на $ x $ ) Найти $ i $ Статистика заказа может быть сделано в $ o (lg (n)) $ Время в худшем случае. Теперь в случае массива, представляющего динамический набор элементов, находящихся в статистике $ i $ th statistic, может быть достигнуто в $ O (n) $ Время в худшем случае. [Где $ n $ - это количество элементов].

Теперь я чувствовал, как нахождение плотной верхней границы для формирования $ n $ Элемент красно-черного дерева, чтобы я мог прокомментировать, какая альтернатива лучше: "поддерживать Установленные элементы в массиве и выполняют запрос в $ O (N) $ Time «или« поддержание элементов в красно-черном дереве (образование которых требует $ O (f (n)) $ Скажите время), а затем выполните запрос в $ O (LG (N)) $ Время ».

---

Так что очень грубый анализ заключается в следующем, вставляя элемент в $ N $ Element Red-Black Breake Tree Trafts $ O (LG (N)) $ ВРЕМЯ И есть $ n $ Элементы для вставки, поэтому требуется $ O (nlg (n)) $ время. Теперь этот анализ довольно свободен, как, когда в красно-черном дереве есть только несколько элементов, высота довольно меньше, а также время вставить в дереве.

Я пытался попытаться попробовать подробный анализ следующим образом (но не удалось, однако):

Пусть при попытке вставить $ j= i + 1 $ th Элемент Высота дерева - Atmost $ 2 .lg (i + 1) +1 $ . Для подходящего $ C $ , общее время работы,

$$ t (n) \ leq \ sum_ {j= 1} ^ {n} c. (2.lg (I + 1) +1) $$

$$= c. \ sum_ {i= 0} ^ {n - 1} (2.lg (i + 1) +1) $$ < / P >.

$$= c. \ Left [\ sum_ {i= 0} ^ {n - 1} 2.lg (i + 1) + \ sum_ {i= 0} ^ {N-1} 1 \ Верно] $$

$$= 2C \ sum_ {i= 0} ^ {n - 1} lg (i + 1) + cn \ tag1 $$

Теперь

$$ \ sum_ {i= 0} ^ {n - 1} lg (i + 1)= lg (1) + lg (2) + lg (3) + ... + lg (n)= lg (1.2.3 .... n) \ tag2 $$

Теперь $$ \ prod_ {k= 1} ^ {n} k \ leq n ^ n, \ text {что очень свободная верхняя граница} \ tag 3 $$

Использование $ (3) $ в $ (2) $ и подставляя результат в $ (1) $ У нас есть $ t (n)= o (nlg (n)) $ , который так же, как грубый анализ ...

Могу ли я сделать все лучше, чем $ (3) $ ?

---

Все узлы называют внутренними узлами в красно-черном дереве.

Answer 1

Чтобы построить красно-черное дерево на $ n $ Элементы, которые вам нужно провести время $ \ Omega (n \ log n) $ , если вам разрешено сравнивать только ключи элементов. Чтобы увидеть это уведомление о том, что визит в заказа любых BST посещает узлы в увеличении порядка своих ключей.

Если бы вы смогли построить красно-черное дерево во время $ t (n)= O (n \ log n) $ Тогда вы также будете в состоянии сортировать $ n $ Элементы во времени $ o (t (n) + n)= o (n \ log n ) $ , противоречащие нижней границе сортировки для сравнения алгоритмов на основе сравнения.

С другой стороны, если элементы уже отсортированы, вы можете построить красно-черное дерево во времени $ O (N) $ : просто рекурсивно строить Сбалансированный BST, если последний уровень неполный цвет, его узлы как красные, а цвет каждый другой узел черный. Это требует линейного времени с момента сложности времени рекурсивного алгоритма может быть описана путем уравнения рецидива $ T (N)= 2T (N / 2) + O (1) $ .