árbol de búsqueda binario con los principales valores de $ a_1 < \dots < a_k$. ¿Cómo elijo $j$ a conseguir un árbol con un mínimo de altura?

Question

Así que al principio he vacío de un árbol de búsqueda binario. Por otra parte tengo la clave de los valores de $a_1 < \dots < a_k$. ¿Cómo podemos elegir $j$ , de modo que después de la primera inserción de un elemento con el valor de clave de $a_j$ un árbol de altura mínima es todavía posible por las nuevas inserciones.

Mis pensamientos:

Mi primera idea fue la de elegir a $j=1$ ( más tarde $j=k$), lo cual es obviamente falso. Sé que de alguna manera hemos de utilizar el hecho de que hayamos $a_1 < \dots < a_k$. Tal vez podríamos optar $j = \frac{k}{2}$ o algo así. Pero esto es sólo una idea. No sé cómo discutir por eso.

Answer 1

El mayor número de nodos de un árbol binario (no necesariamente BST) de altura $H \in \mathbb{N}$ (un solo vértice del árbol tiene la altura $1$) puede alojar es $$ 1 + 2 + ...+2^{H-1} = 2^H - 1, $$ lo que ocurre, precisamente, cuando todos los niveles están llenos. Así, para un BST con $n$ nodos necesitamos al menos la altura de la $H \in \mathbb{N}$ tan satisfactorio $n \leq 2^H - 1$, lo que implica $$H \geq \lceil \log_2(1+n) \rceil \tag{1}$$ donde $\lceil \cdot \rceil$ soportes para el techo de la función. Desde BST es un árbol binario, la mejor altura mínima a $H$ se puede conseguir en $n$ claves deben satisfacer $(1)$.

Vamos ahora a ver que $(1)$ es alcanzable dado una adecuada estructura de los nodos (las teclas). En primer lugar, observe que los valores particulares de $a_1<...<a_n$ de las teclas no importa, podemos WLOG trabajo con claves de $1<2<...<n$ a simplificar la notación. Siguiente, se observa que para $n\in \mathbb{N}$ en el rango de $$2^{k-1} \leq n < 2^k \tag{2} $$ the height estimate $(1)$ da $\lceil \log_2(1+n) \rceil = k $. Por lo tanto es suficiente para mostrar que, para $n$ claves donde $n$ satisface $(2)$ podemos construir un BST de la altura de la $k$ en este teclas. Esta será la configuración óptima, es decir, con la mínima altura (puede haber más de uno de los árboles en $n$ teclas de tener un mínimo de altura dependiendo $n$). Para mostrar esto considere el peor de los casos cuando se $n = 2^k - 1$, se demuestra por inducción que la altura óptima debe ser $k$. De hecho, el caso de $k = 1$ es trivial. Para $k>1$ elija $2^{k-1}$ como la raíz de la BST y poner todo de $\{1,2,...,2^{k-1} - 1 \}$ en la izquierda subárbol y el resto $\{2^{k-1} + 1,...,2^k - 1\}$ a la derecha del subárbol. Esto conservará la BST condición para el nodo raíz. Observe que tanto la izquierda y la derecha subárboles son binarios de búsqueda de árboles con $2^{k-1} - 1$ nodos, y por lo tanto la inducción por tanto tener una altura $k-1$ en la configuración óptima. Esto le da a la altura de la $k$ para el conjunto original de las llaves y completa la inducción de paso.

Ahora, para el conjunto de la incompleta claves, es decir, cuando se $2^{k-1} \leq n < 2^k $ pero no necesariamente $n = 2^k - 1$, podemos añadir "ficticio" de las teclas para hacer $n = 2^k-1$, a continuación, construir el árbol óptimo para este agrandamiento de conjunto de claves y, a continuación, colocar los nodos con un maniquí claves.

Por ejemplo, la ubicación óptima para las llaves $\{1,2,...,7\}$ sería $$ 4\a [2\a[1,3], 6\a [5,7]], $$ con $4$ como la raíz.