Uma árvore AVL é uma árvore binária balanceada, ou seja, que possui altura mínima. Essa altura mínima é conseguida através de rotações, conforme ocorre o processo de inserção e remoção dos elementos. Essa estrutura se chama AVL, por causa dos nomes de seus criadores Adelson Velsky e Landis (AVL). Por ter altura mínima, a árvore AVL garante que o tempo de busca de um elemento será no pior caso: