Implementación de varios algoritmos para árboles binarios balanceados

Luego se modifica el número 1 y los datos se vuelven a conectar como se muestra en la Figura 2 a continuación:

La Figura 2 muestra las siguientes propiedades:

1. Todos los nodos del subárbol izquierdo son más pequeños que sus correspondientes nodos principales (4, 5, 6) (7)> ​​(5)> (9); > 3. El valor absoluto de la diferencia del factor de equilibrio de cada nodo

4. Cada nodo satisface las tres características anteriores.

Un árbol que cumple estas condiciones se denomina árbol AVL.

P: ¿Cuántas veces se necesitan para encontrar el nodo 5 nuevamente?

Debido a que los datos están organizados en orden, la búsqueda es muy rápida de arriba a abajo: 7-5, solo necesita buscar en el subárbol izquierdo, es decir, debe recorrer dos veces. encontrar 5. Supongamos que desea encontrar el nodo hoja 10, solo necesita buscar en el subárbol de la derecha, lo que lleva hasta 3 veces, 7-9-10. En otras palabras, el árbol AVL tiene un buen rendimiento en la búsqueda. El peor de los casos es la cantidad de veces que se busca un nodo, que es la cantidad de capas del árbol, y la complejidad es O (logN).

¿Qué debo hacer si hay demasiados nodos? Supongamos que ahora hay 31 nodos, representados por un árbol AVL, como se muestra en la Figura 3:

La Figura 3 es un árbol AVL con una altura de 4, con 5 capas y 31 nodos. Naranja es la raíz. nodo., el azul son nodos de hoja. La búsqueda del árbol AVL parece perfecta, ¿se puede optimizar aún más? Por ejemplo, ¿puedes aumentar la clave almacenada en este nodo? ¿Puedes reducir el número total de niveles en el árbol? Entonces solo podemos encontrar formas de reducir la profundidad desde la dirección horizontal. En este momento, puede considerar utilizar un árbol de múltiples ramas.