Prueba para la profundidad del árbol de búsqueda equilibrada

Question

Si T es un BST equilibrada con n elementos, L su subárbol izquierdo y R su correcta, ¿cómo puedo demostrar que su profundidad es menor que o igual a 2log (n) + 1?

No es una demostración por inducción, que tengo pero no lo entienden.

(entiendo que stackoverflow es principalmente la programación orientada pero he encontrado algunas preguntas sobre árboles binarios de búsqueda y decidió darle una oportunidad, espero que no estoy haciendo algo que no es bueno:.))

Answer 1

Por definición de "equilibrado", profundidades de cada subárboles izquierdo y derecho de la misma nodo difieren como máximo por uno. "Profundidad" se define normalmente como "número de paso de más larga a pie de la raíz del árbol hasta la hoja", así que por ejemplo un BST con una raíz y dos hojas (tres elementos en la única manera que pueden estar dispuestos en una BST equilibrada) es dice que tiene la profundidad uno (parece que está utilizando una definición ligeramente diferente que darle profundidad dos?), como lo haría una con una raíz y una hoja (ya sea que la hoja es subárbol izquierdo o derecho de la raíz no hace ninguna diferencia), mientras que uno con sólo una raíz que también es una hoja (un solo elemento) habría profundidad 0. (no hay BST con cero elementos).

Así que para n <= 3 elementos, llamando D (n) la profundidad del árbol como se ha definido anteriormente, claramente D(n) < log(n) + 1 (con log significa logaritmo en base 2) mediante inspección, ya que 1 = D(2) < log(2) + 1 = 2 (y también 1 = D(3) para los que el RHS de la desigualdad, log(3) + 1, es de hecho > 2), y 0 = D(1) < log(1) + 1 = 1 - esto nos da la base de inducción

.

Para completar la demostración por inducción tenemos que demostrar que si D(k) < log(k) + 1 para todos k < n, entonces se deduce también que D(n) < log(n) + 1.

Si n es impar, claramente izquierdo y subárbol derecho han (n-1)/2 elementos cada uno, y el árbol tiene profundidad 1 más de los subárboles; pero entonces D(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2) (por la hipótesis de inducción) = 1 + log(n-1) (desde log((n-1)/2) = log(n-1) - 1) y por lo tanto un < 1 + log(n) fortiori, QED.

Si n es incluso le siguen los mismos pasos sólo con log(n) en lugar de log(n-1) y sin el acabado "a fortiori", y prueba de ello todavía mantiene.

Answer 2

Su respuesta es cierto si árbol binario equilibrado se ha completado el número de elementos en la derecha y sub-árbol izquierdo puede ser (n-1) / 2, pero si no es completo, el número de elementos no necesitan ser (n-1) / 2 como último nivel puede tener diferentes elementos