Límite superior ajustado para formar un árbol rojo-negro con elemento $n$ desde cero

Question

Aprendí que en un árbol de orden-estadística (árbol rojo-negro aumentado, en el que cada nodo $x$ contiene un campo adicional que indica el número de nodos en el subárbol con raíz en $x$) encontrar el $yo$ Las estadísticas de orden se pueden hacer en $O(lg(n))$ tiempo en el peor de los casos.Ahora, en el caso de una matriz que represente el conjunto dinámico de elementos que encuentran el $yo$ El estadístico de orden ésimo se puede lograr en el $O(n)$ tiempo en el peor de los casos.[ donde $n$ es el número de elementos].

Ahora tenía ganas de encontrar un límite superior ajustado para formar una $n$ elemento Red-Black Tree para poder comentar cuál alternativa es mejor:"mantener los elementos establecidos en una matriz y realizar consultas en $O(n)$ tiempo" o "mantener los elementos en un Árbol Rojo-Negro (cuya formación toma $O(f(n))$ tiempo digamos) y luego realizar la consulta en $O(lg(n))$ tiempo".

---

Entonces, un análisis muy aproximado es el siguiente: insertar un elemento en un $n$ elemento Árbol Rojo-Negro toma $O(lg(n))$ tiempo y hay $n$ elementos a insertar, por lo que se necesitan $O(nlg(n))$ tiempo.Ahora bien, este análisis es bastante vago ya que cuando hay solo unos pocos elementos en el árbol Rojo-Negro, la altura es bastante menor y también lo es el momento de insertarlos en el árbol.

Intenté intentar un análisis detallado de la siguiente manera (pero fallé):

Deje mientras intenta insertar el $j=i+1$ º elemento la altura del árbol es casi $2.lg(yo+1)+1$.Para una apropiada $c$, el tiempo total de ejecución,

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

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

$$=c.\left[\sum_{i=0}^{n-1}2.lg(i+1)+\sum_{i=0}^{n-1}1 ight]$$

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

Ahora

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

Ahora $$\prod_{k=1}^{n}k\leq n^n, ext{que es un límite superior muy flexible} ag 3$$

Usando $(3)$ en $(2)$ y sustituyendo el resultado en $(1)$ tenemos $T(n)=O(nlg(n))$ que es lo mismo que el análisis aproximado...

¿Puedo hacer algo mejor que $(3)$?

---

Todos los nodos mencionados son los nodos internos del Árbol Rojo-Negro.

Answer 1

Para construir un árbol rojo-negro en $n$ elementos que necesitas para pasar el tiempo $\Omega(n\log n)$, si solo se le permite comparar las claves de los elementos.Para ver este aviso, una visita en orden de cualquier BST visita los nodos en orden creciente de sus claves.

Si pudieras construir un árbol rojo-negro a tiempo $t(n) = o(n \log n)$ entonces también podrás ordenar $n$ elementos en el tiempo $O(t(n) + n) = o(n \log n)$, contradiciendo el límite inferior de clasificación para algoritmos basados ​​en comparación.

Por otro lado, si los elementos ya están ordenados, entonces puedes construir un árbol rojo-negro a tiempo. $O(n)$:simplemente construya recursivamente un BST equilibrado, si el último nivel está incompleto, coloree sus nodos en rojo y coloree todos los demás nodos en negro.Esto requiere un tiempo lineal ya que la complejidad temporal del algoritmo recursivo puede describirse mediante la ecuación de recurrencia. $T(n) = 2T(n/2) + O(1)$.