Saltar al contenido

Diferencia entre el árbol de búsqueda binaria y el árbol AVL

Mejorar artículo

Guardar artículo

Me gusta el artículo

Mejorar artículo

Guardar artículo

Árbol de búsqueda binario:

Un árbol de búsqueda binaria también se conoce como árbol binario ordenado u ordenado porque atravesar el árbol de búsqueda binaria siempre se realiza en orden ordenado.

Un árbol de búsqueda binario es un árbol binario con solo dos ramas en el que cada nodo del subárbol izquierdo es menor o igual y cada nodo del subárbol derecho es mayor. Un árbol de búsqueda binario es una estructura de datos de árbol binario basada en nodos. Podemos realizar recorridos previos, en orden y posteriores al pedido utilizando el árbol de búsqueda binaria.

Árbol AVL:

El árbol AVL es un árbol de búsqueda binario autoequilibrado en el que la diferencia de altura entre el subárbol izquierdo y el derecho no puede ser superior a 1 para todos los nodos. Esta diferencia se denomina factor de equilibrio, es decir, 0, 1 y -1.

Para realizar este equilibrio, realizamos las siguientes rotaciones en el árbol de búsqueda binaria desequilibrada/desequilibrada para convertirlo en un árbol AVL.

  • Rotación izquierda
  • Rotación a la derecha
  • Rotación izquierda derecha
  • Rotación derecha izquierda

Las siguientes son las diferencias entre el árbol de búsqueda binaria y el árbol AVL

S.NoÁrbol de búsqueda binarioAuge AVL
1.En el árbol de búsqueda binaria, en el árbol AVL, no todos los nodos siguen el factor de equilibrio.En AVL Tree, cada nodo sigue el factor de equilibrio, es decir, 0, 1, -1.
2.Cualquier árbol de búsqueda binaria no es un árbol AVL.Cada árbol AVL es un árbol de búsqueda binaria.
3.Fácil de implementar.Complejo de implementar.
4.La altura o profundidad del árbol es O(n).La altura o profundidad del árbol es O(logn)
5.La búsqueda no es eficiente cuando hay una gran cantidad de nodos en la estructura de búsqueda binaria.La búsqueda es eficiente porque la búsqueda del nodo deseado es más rápida debido al equilibrio de la altura.
6.La estructura del árbol de búsqueda binaria consta de 3 campos subárbol izquierdo, datos y subárbol derecho.La estructura de árbol AVL consta de 4 campos, subárbol izquierdo, datos, subárbol derecho y factor de equilibrio.
7.No es un árbol equilibrado.Es un árbol equilibrado.
8.En el árbol de búsqueda binaria. Insertar y eliminar es fácil ya que no se requieren rotaciones.En un árbol AVL, la inserción y la eliminación son complejas porque se requieren varias rotaciones para equilibrar el árbol.