Cada nodo de un árbol AVL tiene que guardar el valor del factor de equilibrio.

Coste de una búsqueda en árbol AVL

O(altura) = O(log N)

Mucho mejor que en el caso de los árboles de búsqueda binarios.

¿Hemos mejorado?
 
 

	Inserción	Borrado	Búsqueda
vectores	O(1)	O(N)	O(N)
vectores  ordenados	O(N)	O(N)	O(log N)
listas con  punteros	O(1)	O(N)	O(N)
listas ordenadas  con punt	O(N)	O(N)	O(N)
BST	O(altura)=O(N)	O(altura)=O(N)	O(altura)=O(N)
AVL	O(altura)=O(log N)	O(altura)=O(log N)	O(altura)=O(log N)