Antes de conocer las diferencias entre el árbol de búsqueda binaria y el árbol AVL, debemos conocer el árbol de búsqueda binaria y el árbol AVL por separado.
¿Qué es un árbol de búsqueda binaria?
El árbol de búsqueda binaria es un árbol árbol binario . Como sabemos, ese árbol puede tener 'n' número de hijos, mientras que; el árbol binario puede contener como máximo dos hijos. Entonces, la restricción de un árbol binario también va seguida del árbol de búsqueda binario. Cada nodo en un árbol de búsqueda binario debe tener como máximo dos hijos; en otras palabras, podemos decir que el árbol binario de búsqueda es una variante del árbol binario.
El árbol de búsqueda binaria también sigue las propiedades de la búsqueda binaria. En la búsqueda binaria, todos los elementos de una matriz deben estar ordenados. Calculamos el elemento del medio en la búsqueda binaria en la que la parte izquierda del elemento del medio contiene el valor menor que el valor del medio y la parte derecha del elemento del medio contiene los valores mayores que el valor del medio.
En el árbol de búsqueda binaria, el elemento del medio se convierte en el nodo raíz, la parte derecha se convierte en el subárbol derecho y la parte izquierda se convierte en el subárbol izquierdo. Por lo tanto, podemos decir que el árbol de búsqueda binario es una combinación de un árbol binario y búsqueda binaria .
Nota: El árbol de búsqueda binaria se puede definir como el árbol binario en el que todos los elementos del subárbol izquierdo son menores que el nodo raíz y todos los elementos del subárbol derecho son mayores que el nodo raíz.
Complejidad temporal en el árbol de búsqueda binaria
Si el árbol de búsqueda binaria es casi un árbol equilibrado, entonces todas las operaciones tendrán una complejidad temporal de O(iniciar sesión) porque la búsqueda se divide hacia el subárbol izquierdo o derecho.
negrita el texto en css
Si el árbol de búsqueda binaria está sesgado hacia la izquierda o hacia la derecha, entonces todas las operaciones tendrán la complejidad temporal de En) porque necesitamos recorrer hasta los n elementos.
¿Qué es el árbol AVL?
Un árbol AVL es un árbol de búsqueda binario autoequilibrado donde la diferencia entre las alturas de los subárboles izquierdo y derecho no puede ser más de uno. Esta diferencia se conoce como factor de equilibrio. En el árbol AVL, los valores del factor de equilibrio pueden ser -1, 0 o 1.
¿Cómo se produce el autoequilibrio del árbol de búsqueda binario?
Como sabemos, el árbol AVL es un árbol de búsqueda binario autoequilibrado. Si el árbol de búsqueda binaria no está equilibrado, puede autoequilibrarse con algunas reorganizaciones. Estos reordenamientos se pueden realizar mediante algunas rotaciones.
Entendamos el autoequilibrio a través de un ejemplo.
Supongamos que queremos insertar 10, 20, 30 en un árbol AVL.
Las siguientes son las formas de insertar 10, 20, 30 en un árbol AVL:
Paso 1: Primero, creamos un árbol de búsqueda binario, como se muestra a continuación:
Paso 2: En la figura anterior, podemos observar que el árbol está desequilibrado porque el factor de equilibrio del nodo 30 es 2. Para convertirlo en un árbol AVL, necesitamos realizar algunas rotaciones. Si realizamos la rotación hacia la derecha en el nodo 20, entonces el nodo 30 se moverá hacia abajo, mientras que el nodo 20 se moverá hacia arriba, como se muestra a continuación:
Como podemos observar, el árbol final sigue la propiedad del árbol de Búsqueda Binaria y un árbol balanceado; por tanto, es un árbol AVL.
jsp
En el caso, el árbol fue árbol dejado desequilibrado, entonces realizamos la rotación correcta en el nodo.
Paso 1: Primero creamos un árbol de búsqueda binaria como se muestra a continuación:
Paso 2: En la figura anterior, podemos observar que el árbol está desequilibrado porque el factor de equilibrio del nodo 10 es -2. Para convertirlo en un árbol AVL, necesitamos realizar algunas rotaciones. Es un árbol desequilibrado hacia la derecha, por lo que realizaremos rotación hacia la izquierda. Si realizamos una rotación hacia la izquierda en el nodo 20, entonces el nodo 20 se moverá hacia arriba y el nodo 10 se moverá hacia abajo, como se muestra a continuación:
Como podemos observar, el árbol final sigue la propiedad del Árbol de búsqueda binaria y un árbol equilibrado ; por tanto, es un árbol AVL.
Paso 1: Primero creamos el árbol de búsqueda binaria como se muestra a continuación:
Paso 2: En la figura anterior, podemos observar que el árbol está desequilibrado porque el factor de equilibrio del nodo raíz es 2. Para convertirlo en un árbol AVL, necesitamos realizar algunas rotaciones. El escenario anterior está desequilibrado de izquierda a derecha ya que un nodo está a la izquierda de su nodo principal y otro está a la derecha de su nodo principal. Primero, realizaremos la rotación hacia la izquierda, y la rotación ocurre entre los nodos 10 y 20. Después de la rotación hacia la izquierda, 20 se moverá hacia arriba y 10 hacia abajo como se muestra a continuación:
método de subcadena en java
Aún así, el árbol está desequilibrado, por lo que realizamos la rotación correcta en el árbol. Una vez que se realiza la rotación correcta en el árbol, el árbol quedará como se muestra a continuación:
Como podemos observar en el árbol anterior, el árbol sigue la propiedad del árbol de Búsqueda Binaria y un árbol balanceado; por tanto, es un árbol AVL.
Paso 1: Primero, creamos el árbol de búsqueda binaria, como se muestra a continuación:
Paso 2: En la figura anterior, podemos observar que el árbol está desequilibrado porque el factor de equilibrio del nodo raíz es 2. Para convertirlo en un árbol AVL, necesitamos realizar algunas rotaciones. El escenario anterior está desequilibrado de derecha a izquierda, ya que un nodo está a la derecha de su nodo principal y otro nodo está a la izquierda de su nodo principal. Primero, realizaremos la rotación a la derecha que ocurre entre los nodos 30 y 20. Después de la rotación a la derecha, 20 se moverá hacia arriba y 30 hacia abajo como se muestra a continuación:
Aún así, el árbol anterior está desequilibrado, por lo que debemos realizar una rotación hacia la izquierda en el nodo. Una vez que se realiza la rotación hacia la izquierda, el nodo 20 se moverá hacia arriba y el nodo 10 se moverá hacia abajo como se muestra a continuación:
Como podemos observar en el árbol anterior, el árbol sigue la propiedad del árbol de Búsqueda Binaria y un árbol balanceado; por tanto, es un árbol AVL.
Diferencias entre el árbol de búsqueda binaria y el árbol AVL
| Árbol de búsqueda binaria | árbol AVL |
|---|---|
| Cada árbol de búsqueda binario es un árbol binario porque ambos árboles contienen como máximo dos hijos. | Cada árbol AVL también es un árbol binario porque el árbol AVL también tiene dos hijos como máximo. |
| En BST, no existe ningún término, como factor de equilibrio. | En el árbol AVL, cada nodo contiene un factor de equilibrio y el valor del factor de equilibrio debe ser -1, 0 o 1. |
| Cada árbol de búsqueda binaria no es un árbol AVL porque BST puede ser un árbol equilibrado o desequilibrado. | Cada árbol AVL es un árbol de búsqueda binario porque el árbol AVL sigue la propiedad de BST. |
| Cada nodo en el árbol de búsqueda binaria consta de tres campos, es decir, el subárbol izquierdo, el valor del nodo y el subárbol derecho. | Cada nodo en el árbol AVL consta de cuatro campos, es decir, subárbol izquierdo, valor de nodo, subárbol derecho y factor de equilibrio. |
| En el caso del árbol de búsqueda binaria, si queremos insertar cualquier nodo en el árbol, comparamos el valor del nodo con el valor raíz; si el valor del nodo es mayor que el valor del nodo raíz, entonces el nodo se inserta en el subárbol derecho; de lo contrario, el nodo se inserta en el subárbol izquierdo. Una vez insertado el nodo, no es necesario verificar el factor de equilibrio de altura para completar la inserción. | En el caso del árbol AVL, primero encontraremos el lugar adecuado para insertar el nodo. Una vez insertado el nodo, calcularemos el factor de equilibrio de cada nodo. Si se satisface el factor de equilibrio de cada nodo, se completa la inserción. Si el factor de equilibrio es mayor que 1, entonces necesitamos realizar algunas rotaciones para equilibrar el árbol. |
| En el árbol de búsqueda binaria, la altura o profundidad del árbol es O(n), donde n es el número de nodos en el árbol de búsqueda binaria. | En el árbol AVL, la altura o profundidad del árbol es O (logn). |
| Es sencillo de implementar ya que debemos seguir las propiedades de Búsqueda binaria para insertar el nodo. | Es complejo de implementar porque en el árbol AVL, primero tenemos que construir el árbol AVL y luego debemos verificar el equilibrio de altura. Si la altura está desequilibrada, entonces debemos realizar algunas rotaciones para equilibrar el árbol. |
| BST no es un árbol equilibrado porque no sigue el concepto de factor de equilibrio. | El árbol AVL es un árbol con altura equilibrada porque sigue el concepto de factor de equilibrio. |
| La búsqueda es ineficiente en BST cuando hay una gran cantidad de nodos disponibles en el árbol porque la altura no está equilibrada. | La búsqueda es eficiente en el árbol AVL incluso cuando hay una gran cantidad de nodos en el árbol porque la altura está equilibrada. |