AVL 트리는 균형 이진 검색 트리입니다. 이 게시물에서는 이진 검색 트리를 소개했습니다. 이진 트리의 검색, 삽입 및 삭제 시간은 트리 높이에 따라 달라집니다. 최악의 경우 높이는 O(n)이다. 트리가 완벽하게 균형을 이루고 즉, 완전한 이진 트리인 경우 높이는 log n입니다. 완벽하게 균형잡힌 트리를 유지할 수 있을까요? 예, 하지만 그렇게 하면 비용이 많이 듭니다. 절충안은 균형이 잘 잡힌 트리를 유지하는 것입니다. 즉, 모든 노드의 두 하위 트리 높이가 거의 같습니다.

AVL 트리는 균형이 잘 잡혀 있습니다. AVL 트리는 1962년 두 명의 러시아 컴퓨터 과학자인 G. M. Adelson-Velsky와 E. M. Landis(따라서 AVL이라는 이름)에 의해 발명되었습니다. AVL 트리에서 모든 노드의 두 하위 트리 높이 차이는 0 또는 1입니다. AVL 트리의 최대 높이는 O(log n)임을 알 수 있습니다.

AVL 트리에서 요소를 삽입하거나 삭제하는 프로세스는 삽입 또는 삭제 작업 후 트리 균형을 다시 조정해야 한다는 점을 제외하면 일반 이진 검색 트리와 동일합니다. 노드의 균형 인자는 오른쪽 하위 트리의 높이에서 왼쪽 하위 트리의 높이를 뺀 값입니다. 균형 요소가 -1, 0 또는 1인 경우 노드는 균형이라고 합니다. 균형 요소가 -1이면 노드는 왼쪽에 무겁다고, 균형 요소가 1이면 오른쪽에 무겁다고 간주됩니다.