Limite superior apertado para formar uma árvore vermelha-preta $ N $ n $

Question

Eu aprendi que em uma árvore estatística de ordem (árvore vermelha vermelha aumentada, na qual cada nó $ x $ contém um campo extra denotando o número de nós em A sub-árvore enraizada na $ x $ ) Encontrando a $ i $ as estatísticas do pedido podem ser feitas em $ O (LG (n)) $ tempo no pior caso. Agora, no caso de uma matriz que representa o conjunto dinâmico de elementos que encontram a estatística de $ i $ a estatística de pedido pode ser alcançado na $ O (n) $ tempo no pior caso. [Onde $ n $ é o número de elementos].

Agora eu senti vontade de encontrar um limite superior apertado para formar uma $ n $ elemento árvore vermelha de vermelho para que eu possa comentar sobre qual alternativa é melhor: "Mantenha os elementos definidos em uma matriz e executar consulta na $ O (n) $ tempo "ou" Manter os elementos em uma árvore vermelha (formação de que leva classe="contêiner matemática"> $ o (f (n)) $ time diga) e, em seguida, execute a consulta na $ O (LG (n)) $ Tempo ".

---

.

Portanto, uma análise muito aproximada é a seguinte, inserindo um elemento em uma classe $ n $ elemento Vermelho-preto árvore leva $ O (lg (n)) $ tempo e há $ n $ elementos para inserir, então é preciso $ O (nlg (n)) $ tempo. Agora esta análise é bastante solta como quando há apenas alguns elementos na árvore vermelho-preto A altura é bastante menor e é a hora de inserir na árvore.

Eu tentei tentar uma análise detalhada da seguinte forma (mas falhou no entanto):

Deixe ao tentar inserir a $ J= i + 1 $ th elemento A altura da árvore é a mais uma $ 2 .lg (i + 1) +1 $ . Para uma $ c $ , o tempo total de funcionamento,

$$ 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 \ Direita] $$

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

agora

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

agora $$ \ Prod_ {k= 1} ^ {n} k \ leq n ^ n, \ text {Qual é um limite superior muito solto} \ tag 3 $$

Usando $ (3) $ na $ (2) $ e substituindo o resultado em $ (1) $ temos $ t (n)= O (nlg (n)) $ que é o mesmo que a análise aproximada ...

Posso fazer qualquer coisa melhor do que $ (3) $ ?

---

.

Todos os nós referidos são os nós internos na árvore vermelho-preto.

Answer 1

Para construir uma árvore vermelha vermelha na $ n $ elementos que você precisa gastar tempo $ \ Omega (n \ Log n) $ , se você só tem permissão para comparar as chaves dos elementos. Para ver este aviso de que uma visita de encomenda de qualquer BST visita os nós na ordem crescente de suas chaves.

Se você foi capaz de construir uma árvore vermelha-preta no tempo $ t (n)= o (n \ log n) $ então você também seria capaz de classificar $ n $ elementos no tempo $ o (t (n) + n)= o (n \ log n ) $ , contradizendo o limite inferior na classificação para algoritmos baseados em comparação.

Por outro lado, se os elementos já estiverem classificados, você pode construir uma árvore-negra vermelha no tempo $ O (n) $ : Apenas recursivamente construir Um BST equilibrado, se o último nível estiver incompleto colorir seus nós como vermelho, e cor de cada outro nó preto. Isso requer tempo linear, uma vez que a complexidade do tempo do algoritmo recursivo pode ser descrita pela equação de recorrência $ t (n)= 2T (n / 2) + O (1) $ .