Limite supérieure serrée pour former un ort-noire rouge N $ N $ à partir de zéro

Question

J'ai appris que dans un arbre statistique de commande (arbre rouge-noir augmenté, dans lequel chaque nœud $ x $ contient un champ supplémentaire désignant le nombre de nœuds dans Le sous-arbre enraciné à $ x $ ) trouver la $ i $ £ statistiques peuvent être effectuées dans $ O (LG (N)) $ TIME Dans le pire des cas. Maintenant, dans le cas d'un tableau représentant l'ensemble dynamique d'éléments trouvant la $ i $ statistique de commande peut être atteint dans la $ O (n) $ dans le pire des cas. [Où $ n $ est le nombre d'éléments].

Maintenant, je me sentais comme trouver une limite supérieure serrée pour former une $ N $ élément rouge-noir de sorte que je puisse commenter quelle alternative est meilleure: "Maintenir les éléments de jeu dans une matrice et exécutent une requête dans $ o (n) $ temps "ou" maintenant les éléments dans un arbre noir rouge (formation qui prend $ O (f (n)) $ Dites de temps), puis effectuez la requête dans $ o (lg (n)) $ temps ".

---

Ainsi, une analyse très approximative est la suivante, insérant un élément dans une $ n $ élément rouge-noir prend $ O (lg (n)) $ temps et il y a $ n $ éléments à insérer, il faut donc $ O (nlg (n)) $ temps. Maintenant, cette analyse est assez lâche comme lorsqu'il n'y a que peu d'éléments dans l'arbre noir rouge, la hauteur est tout à fait de moins en moins de temps pour insérer dans l'arbre.

J'ai essayé d'essayer une analyse détaillée comme suit (mais a échoué):

Soit tout en essayant d'insérer la $ J= I + 1 $ TH ELEMENT La hauteur de l'arborescence est au plus $ 2 .LG (i + 1) +1 $ . Pour une $ C $ C $ , l'heure de fonctionnement totale,

$$ 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. \ \ SUM_ {I= 0} ^ {N-1} 2.LG (i + 1) + \ Sum_ {i= 0} ^ {n-1} 1 \ droite] $$

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

maintenant

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

maintenant $$ \ prod_ {k= 1} ^ {n} k \ leq n ^ n, \ texte {qui est une limite supérieure très lâche} \ tag 3 $$

en utilisant $ (3) $ in $ (2) $ et substituer le résultat dans $ (1) $ nous avons $ t (n)= o (nlg (n)) $ qui est le Identique à l'analyse approximative ...

Puis-je faire quelque chose de mieux que $ (3) $ ?

---

Tous les nœuds mentionnés sont les nœuds internes dans l'arbre noir noir.

Answer 1

Pour construire un arbre noir rouge sur $ N $ oits dont vous avez besoin de passer du temps $ \ omega (n \ journal n) $ si vous n'êtes autorisé à comparer que les clés des éléments. Pour voir cet avis qu'une visite intégrée de toute BST visit les nœuds dans l'ordre croissant de leurs clés.

Si vous avez pu construire un arbre noir noir dans le temps $ t (n)= O (n \ journal n) $ alors vous seriez également Capable de trier $ N $ éléments dans le temps $ o (t (n) + n)= O (n \ journal n ) $ , contredisant la liaison inférieure sur le tri pour des algorithmes à base de comparaison.

D'autre part, si les éléments sont déjà triés, vous pouvez construire un arbre noir rouge à temps $ o (n) $ : juste de la construction récursive BST équilibré, si le dernier niveau est incomplet, ses nœuds sont en rouge et colorent tous les autres nœud noirs. Cela nécessite du temps linéaire car la complexité de l'algorithme récursif peut être décrite par l'équation de récurrence $ t (n)= 2T (n / 2) + o (1) $ .