12 AVL TREE

¿Que es un AVL Tree?

AVL means Adelson-Velskii and Landis.

Is a binary search tree with a balance condition. This condition is easy to maintain ensuring that the depth of the tree is O(logN).

Each node of an AVL tree has a balance factor.

Balance factor is defined as the height of the right subtree minus the height of the left subtree.

Operación de inserción

Siga el mismo proceso que el algoritmo de búsqueda bianary. El nuevo nodo se agrega como una hoja con un factor de equilibrio de 0.

Retroceda el camino para volver a calcular el factor de equilibrio.

Solo los nodos en la ruta de búsqueda podrían haber cambiado su valor.

Eliminar operación

Cuando el nodo es una hoja, es tan simple como eliminar ese nodo