Rotación de árboles
Se utiliza para cambiar la forma del árbol, y en particular para disminuir su altura moviendo subárboles más pequeños hacia abajo y subárboles más grande, lo que resulta en un mejor rendimiento de muchas operaciones de los árboles.
En este artículo se adopta el enfoque del lado a donde los nodos quedan cambiados.
La operación inversa es la rotación a la izquierda, lo que resulta en un movimiento en sentido contrario a las agujas del reloj (la rotación izquierda se muestra más arriba tiene sus raíces en P).
Además, el programador debe tener en cuenta que esta operación puede dar lugar a una nueva raíz para todo el árbol y tener cuidado para actualizar los punteros en consecuencia.
Aquí están los recorridos finde de los árboles que se muestran arriba: Computar uno a partir del otro es muy simple.
Lo siguiente es ejemplo de código Python que realiza ese cálculo: Otra forma de verlo es: Giro a derechas del nodo Q: Rotación izquierda del nodo P: Todas las demás conexiones se dejan tal cual.
Por lo tanto, se puede aplicar estratégicamente rotaciones para nodos cuyos izquierda infantil y derecho difieren en altura por más de 1. auto-equilibrio árboles binarios de búsqueda aplicar esta operación automáticamente.
Con esta distancia, el conjunto de los árboles binarios de n-nodo se convierte en un espacio métrico: la distancia es simétrica y positiva cuando se les da dos árboles diferentes, y satisface la desigualdad triangular.
