La motivación para los árboles equilibrados

El tiempo necesario para consultar/agregar/eliminar un árbol de búsqueda es proporcional a la altura h del árbol, pero no proporcional a la capacidad n del árbol. Si puede mantener el árbol corto y grueso, es decir, mantener H alrededor de O (lg n), completar el trabajo anterior ahorrará tiempo. Un árbol de búsqueda que siempre puede mantener una buena forma y no se torce debido a adiciones y eliminaciones se denomina árbol de búsqueda equilibrado.

Rotación: una pequeña operación que no destruye las características de la izquierda pequeña y la derecha grande.

Hay muchos tipos de árboles equilibrados, algunos de los cuales se equilibran mediante cirugía plástica:

En la figura, xey son nodos; a, b, c son números enteros. árbol. Imagínese: si x era originalmente el hijo izquierdo de y ahora desea cambiar X a padre, ¿cómo debería cambiarse el resto del árbol? Debe convertirse en el niño adecuado para mantener las características de BST: izquierda pequeña y derecha grande. En cuanto a las otras partes bajo X e Y, toda la cadena de subárboles se puede procesar junta: el subárbol izquierdo original de X (A) sigue siendo el subárbol izquierdo de X después del ajuste, el subárbol derecho original de Y (C) sigue siendo; Y después del ajuste. El subárbol derecho de X; y el subárbol derecho original (B) de Mantener las características de BST después del ajuste es la única respuesta. Puedes verlo más claramente dibujando los dos valores de X e Y y las tres cadenas de valores en los tres subárboles A, B y C en el eje numérico:

- x - y -

BC

Esta acción se llama rotación hacia la derecha o hacia la derecha. El padre original (y) se llama pivote y el hijo original (x) se llama rotador.

Mire la imagen de arriba al revés. Si el árbol original se parece a la imagen de la derecha y desea cambiarlo a la imagen de la izquierda, se llama rotación hacia la izquierda o rotación en sentido antihorario. . El padre original (x) se llama pivote y el hijo original (y) se llama rotador. El subárbol del árbol binario equilibrado tiene una raíz, el subárbol derecho es X, la raíz del subárbol izquierdo es RootL y los dos subárboles del subárbol izquierdo son LLeftChild y LRightChild. Después de la rotación hacia la derecha, la raíz de este subárbol es RootL, el subárbol izquierdo es LLeftChild, la raíz del subárbol derecho es Root y los dos subárboles de Root son LRightChild (izquierda) y x (derecha).

¿Cuántos nodos hay en el antiguo árbol padre-hijo-izquierdo? ¿Cuántos nodos tiene el subárbol de la derecha? ¿Cuántos nodos hay en los subárboles izquierdo y derecho del nuevo nodo principal después de la rotación? Se encontró que el efecto de la derecha moverá el centro de gravedad del árbol hacia la derecha; el efecto de la izquierda moverá el centro de gravedad del árbol hacia la izquierda. Si su árbol ha pasado por muchas vicisitudes de inserción/extracción, etc., se torcerá cada vez más a medida que se alargue. Si lo giras en el momento adecuado, ¿no podría volver a su apariencia baja, gorda y hermosa? Por lo tanto, las manos izquierda y derecha son las operaciones básicas utilizadas por varios árboles de equilibrio; sólo los árboles de equilibrio son diferentes y el momento y las condiciones para la selección quirúrgica son diferentes.

Un árbol con nodos secundarios izquierdo y derecho simétricos es un árbol equilibrado; de lo contrario, es un árbol desequilibrado.

Un árbol desequilibrado afectará la eficiencia de consultar, insertar y eliminar datos en el árbol. Por ejemplo, cuando un árbol binario está extremadamente desequilibrado, es decir, cuando todos los nodos están en el mismo lado de la raíz y el árbol no tiene ramas, se convierte en una lista enlazada. La disposición de los datos es unidimensional, no bidimensional. En este caso, la velocidad de búsqueda cae a O(N) en lugar de O(logN) para un árbol binario equilibrado.

Para buscar un árbol en un tiempo O(logN) más rápido, debe asegurarse de que el árbol esté siempre equilibrado (o al menos mayoritariamente equilibrado). Es decir, para cada nodo del árbol, el número de descendientes a su izquierda debe ser aproximadamente igual al número de descendientes a su derecha.