avl tree heap data structure c
Este tutorial proporciona una explicación detallada de los árboles AVL y la estructura de datos del montón en C ++ junto con ejemplos de árboles AVL para una mejor comprensión:
AVL Tree es un árbol binario de altura equilibrada. Cada nodo está asociado con un factor equilibrado que se calcula como la diferencia entre la altura de su subárbol izquierdo y el subárbol derecho.
El árbol AVL lleva el nombre de sus dos inventores, es decir, G.M. Abelson-Velvety y E.M. Landis, y fue publicado en 1962 en su artículo “Un algoritmo para la organización de la información”.
=> Busque toda la serie de formación en C ++ aquí.
Lo que vas a aprender:
Árbol AVL en C ++
Para que el árbol esté equilibrado, el factor equilibrado para cada nodo debe estar entre -1 y 1. De lo contrario, el árbol se desequilibrará.
A continuación se muestra un ejemplo de árbol AVL.
En el árbol anterior, podemos notar que la diferencia de altura de los subárboles izquierdo y derecho es 1. Esto significa que es una BST equilibrada. Como el factor de equilibrio es 1, esto significa que el subárbol izquierdo está un nivel más alto que el subárbol derecho.
Si el factor de equilibrio es 0, significa que los subárboles izquierdo y derecho están al mismo nivel, es decir, tienen la misma altura. Si el factor de equilibrio es -1, entonces el subárbol izquierdo es un nivel más bajo que el subárbol derecho.
El árbol AVL controla la altura de un árbol de búsqueda binario y evita que se desvíe. Porque cuando un árbol binario se sesga, es el peor de los casos (O (n)) para todas las operaciones. Al utilizar el factor de equilibrio, el árbol AVL impone un límite al árbol binario y, por lo tanto, mantiene todas las operaciones en O (log n).
Operaciones de árbol AVL
Las siguientes son las operaciones admitidas por los árboles AVL.
# 1) Inserción de árbol AVL
La operación de inserción en el árbol AVL de C ++ es la misma que la del árbol de búsqueda binaria. La única diferencia es que para mantener el factor de equilibrio, necesitamos rotar el árbol hacia la izquierda o hacia la derecha para que no se desequilibre.
# 2) Eliminación del árbol AVL
La operación de eliminación también se realiza de la misma manera que la operación de eliminación en un árbol de búsqueda binaria. Nuevamente, necesitamos reequilibrar el árbol realizando algunas rotaciones de árbol AVL.
Implementación del árbol AVL
A continuación se muestra el programa C ++ para demostrar el árbol AVL y sus operaciones.
|_+_|Producción:
El recorrido en orden para el árbol AVL es:
4 5 8 11 12 17 18
Recorrido en orden después de la eliminación del nodo 5:
4 8 11 12 17 18
Tenga en cuenta que hemos utilizado el árbol de ejemplo que se muestra arriba para demostrar el árbol AVL en el programa.
Aplicaciones de los árboles AVL
- Los árboles AVL se utilizan principalmente para tipos de conjuntos y diccionarios en memoria.
- Los árboles AVL también se utilizan ampliamente en aplicaciones de bases de datos en las que las inserciones y eliminaciones son menos, pero hay búsquedas frecuentes de datos necesarios.
- Se utiliza en aplicaciones que requieren una búsqueda mejorada además de las aplicaciones de base de datos. .
Estructura de datos HEAP en C ++
Un montón en C ++ es una estructura de datos especial basada en árboles y es un árbol binario completo.
Los montones pueden ser de dos tipos:
- Min-montón : En min-heap, el elemento más pequeño es la raíz del árbol y cada nodo es mayor o igual que su padre.
- Max-montón : En max-heap, el elemento más grande es la raíz del árbol y cada nodo es menor o igual que su padre.
Considere la siguiente matriz de elementos:
10 20 30 40 50 60 70
El min-montón de los datos anteriores se representa a continuación:
El montón máximo que utiliza los datos anteriores se muestra a continuación:
Montón binario C ++
Un montón binario es la implementación común de una estructura de datos de montón.
Un montón binario tiene las siguientes propiedades:
- Es un árbol binario completo cuando todos los niveles están completamente llenos excepto posiblemente el último nivel y el último nivel tiene sus claves tanto como sea posible.
- Un montón binario puede ser min-heap o max-heap.
Un montón binario es un árbol binario completo y, por lo tanto, se puede representar mejor como una matriz.
Veamos la representación de matriz del montón binario.
Considere el siguiente montón binario.
En el diagrama anterior, el recorrido del montón binario se denomina orden de nivel.
Por lo tanto, la matriz para el montón binario anterior se muestra a continuación como HeapArr:
Como se muestra arriba, HeapArr (0) es la raíz del montón binario. Podemos representar los otros elementos en términos generales de la siguiente manera:
Si HeapArr (i) es una ithnodo en un montón binario, luego los índices de los otros nodos de la ithnodo son:
- HeapArr ((i-1) / 2) => Devuelve el nodo padre.
- HeapArr ((2 * i) +1) => Devuelve el nodo hijo izquierdo.
- HeapArr ((2 * i) +2) => Devuelve el nodo hijo derecho.
El montón binario satisface la 'propiedad de ordenación', que es de dos tipos, como se indica a continuación:
- Propiedad del montón mínimo: El valor mínimo está en la raíz y el valor de cada nodo es mayor o igual que su padre.
- Propiedad Max Heap: El valor máximo está en la raíz y el valor de cada nodo es menor o igual que su padre.
Operaciones en montón binario
Las siguientes son las operaciones básicas que se llevan a cabo en un montón mínimo. En el caso del montón máximo, las operaciones se invierten en consecuencia.
# 1) Insertar () - Inserta una nueva clave al final del árbol. Dependiendo del valor de la clave insertada, es posible que tengamos que ajustar el montón, sin violar la propiedad del montón.
# 2) Eliminar () - Elimina una clave. Nota que la complejidad temporal de las operaciones de inserción y eliminación del montón es O (log n).
# 3) disminuciónKey () - Disminuye el valor de la clave. Es posible que necesitemos mantener la propiedad del montón cuando se lleve a cabo esta operación. La complejidad de tiempo de la operación de disminución de clave del montón también es O (log n).
#4) extractMin() - Elimina el elemento mínimo del min-heap. Necesita mantener la propiedad del montón después de eliminar el elemento mínimo. Por tanto, su complejidad temporal es O (log n).
# 5) getMin () - Devuelve el elemento raíz del min-heap. Esta es la operación más simple y la complejidad de tiempo para esta operación es O (1).
Implementación de la estructura de datos del montón
A continuación se muestra la implementación de C ++ para demostrar la funcionalidad básica de min-heap.
|_+_|Producción:
Montón después de la inserción: 2 4 6 8 10 12
qué tipos de aplicaciones probamos
raíz del montón: 2
Montón después de eliminar clave (2): 2 4 12 8 10
elemento mínimo en el montón: 2
nueva raíz del montón después de la disminución Clave: 1
Aplicaciones de montones
- Heapsort: El algoritmo heapsort se implementa de forma eficaz mediante un montón binario.
- Colas de prioridad: El montón binario admite todas las operaciones necesarias para implementar con éxito las colas de prioridad en tiempo O (log n).
- Algoritmos de gráficos: Algunos de los algoritmos relacionados con los gráficos usan la cola de prioridad y, a su vez, la cola de prioridad usa el montón binario.
- La complejidad del algoritmo de clasificación rápida en el peor de los casos se puede superar mediante la clasificación de montón.
Conclusión
En este tutorial, hemos visto dos estructuras de datos, es decir, árboles AVL y ordenación de montón en detalle.
Los árboles AVL son árboles binarios equilibrados que se utilizan principalmente en la indexación de bases de datos.
Todas las operaciones realizadas en árboles AVL son similares a las de los árboles de búsqueda binaria, pero la única diferencia en el caso de los árboles AVL es que necesitamos mantener el factor de equilibrio, es decir, la estructura de datos debe permanecer como un árbol equilibrado como resultado de varias operaciones. Esto se logra mediante la operación AVL Tree Rotation.
Los montones son estructuras de árbol binario completas que se clasifican en min-heap o max-heap. Min-heap tiene el elemento mínimo como raíz y los nodos subsiguientes son mayores o iguales que su nodo padre. En max-heap, la situación es exactamente opuesta, es decir, el elemento máximo es la raíz del montón.
Los montones se pueden representar en forma de matrices con el 0thelemento como la raíz del árbol. Las estructuras de datos de montón se utilizan principalmente para implementar colas de prioridad y ordenación de montón.
=> Visite aquí para aprender C ++ desde cero.
Lectura recomendada
- Estructura de datos de cola en C ++ con ilustración
- Estructura de datos de pila en C ++ con ilustración
- Estructura de datos de lista enlazada circular en C ++ con ilustración
- Estructura de datos de lista vinculada en C ++ con ilustración
- Introducción a las estructuras de datos en C ++
- Estructura de datos de cola de prioridad en C ++ con ilustración
- Estructura de datos de lista doblemente enlazada en C ++ con ilustración
- Ordenar montón en C ++ con ejemplos