¿Por qué la altura mínima de un árbol binario

10

En mi clase de Java, estamos aprendiendo sobre la complejidad de diferentes tipos de colecciones.

Pronto hablaremos de árboles binarios, sobre los que he estado leyendo. El libro establece que la altura mínima de un árbol binario es , pero no ofrece más explicaciones.log2(n+1)1

¿Alguien puede explicar por qué?

CodyBugstein
fuente
Lo explico aquí stackoverflow.com/a/13093274/550393
2cupsOfTech

Respuestas:

11

Un árbol binario tiene 1 o 2 hijos en nodos no hoja y 0 nodos en nodos hoja. Deje que haya nodos en un árbol y tenemos que organizarlos de tal manera que todavía formen un árbol binario válido.norte

Sin probar, estoy afirmando que para maximizar la altura, los nodos dados deben estar dispuestos linealmente, es decir, cada nodo no hoja debe tener solo un hijo:

                              O 1
                              |
                              O 2
                              |
                              O 3
                              |
                              O 4
                              |
                              O 5
                              |
                              O 6
                              |
                              O 7
                              |
                              O 8

Aquí, la fórmula para calcular la relación de altura en términos de número de nodos es sencilla. Si es la altura del árbol, entonces h = n - 1 .hh=norte-1

Ahora, si intentamos construir un árbol binario de nodos con altura mínima (siempre reducible a un árbol binario completo), tenemos que empaquetar tantos nodos como sea posible en los niveles superiores, antes de pasar al siguiente nivel. Entonces, el árbol toma la forma del siguiente árbol:norte

                              O
                              |1
                              |
                       O------+-----O
                       |2           |3
                       |            |
                   O---+---O    O---+----O
                   |4      |5    6        7
                   |       |
               O---+--O    O
                8      9    10

Comencemos con un caso particular, .norte=2metro-1

Sabemos que,

20 0+21+22+...+2metro-1=2metro-1

Además, es fácil demostrar que, un nivel puede tener como máximo 2 i nodos en ella.yo2yo

Usando este resultado en la suma anterior, encontramos que para cada nivel , de 0 a m , existe un término correspondiente 2 i - 1 en la expansión de 2 m - 1 . Esto implica que un árbol binario completo de 2 m - 1 nodos está completamente lleno y tiene una altura, h ( 2 m - 1 ) = m - 1 , donde h ( n ) = altura de un árbol binario completo con n nodos.yo0 0metro2yo-12metro-12metro-1h(2metro-1)=metro-1h(norte)=norte

Usando este resultado, , ya que el árbol con 2 m - 1 nodos está completamente lleno y, por lo tanto, un árbol con ( 2 m - 1 ) + 1 = 2 m nodos tiene que acomodar el nodo adicional en el siguiente nivel m , aumentando la altura en 1 de m - 1 a m .h(2metro)=metro2metro-1(2metro-1)+1=2metrometrometro-1metro

Hasta ahora hemos demostrado, h ( 2 m + 1 ) = m + 1 así como, h ( 2 m + 1 - 1 ) = m

h(2metro)=metro,
h(2metro+1)=metro+1
h(2metro+1-1)=metro

Por lo tanto, m h ( n ) < m + 1norteZ,2metronorte<2metro+1

metroh(norte)<metro+1

Pero, tomando log (base 2) en ambos lados, m = log 2 ( n )

metroIniciar sesión2(norte)<metro+1
metro=Iniciar sesión2(norte)

Por lo tanto, h ( n ) = m = log 2 ( n ) norte,norte[2metro,2metro+1)

h(norte)=metro=Iniciar sesión2(norte)

Y podemos generalizar este resultado usando la inducción.norteZ

Iniciar sesión2(norte+1)-1norteIniciar sesión2(norte)norte

Anurag Kalia
fuente
18

norte

4 41+12+122+12223

nodos=1+2+22+23+...+2profundidad=k=0 0profundidad2k=1-2profundidad+11-2.

nodos=2profundidad+1-1,
nodos+1=2profundidad+1Iniciar sesión2(nodos+1)=Iniciar sesión2(2profundidad+1)=profundidad+1Iniciar sesión2(nodos+1)-1=profundidad.
MikeDan
fuente
4

Para mantener la altura mínima, es fácil ver que necesitamos completar todos los niveles, excepto posiblemente el último. ¿Por qué? de lo contrario, podríamos subir los nodos del último nivel a espacios vacíos en los niveles superiores.

Ahora, imagine que tengo un número no especificado de frijoles y le doy un grano a la vez y le pido que construya un árbol binario con la altura mínima posible. Puede que me quede sin frijoles cuando llenes el último nivel por completo o al menos tengas un frijol en el último nivel. Digamos que tienes la altura de tu árbol h en este punto.

20 0+21+22+23++2h=2h+1-1norte.
h=lg(norte+1)-1.
usuario1234
fuente