AVL TREE란? AVL 트리는 Adelson-Velsky와 Evgenii Landis가 발명한 자가 균형 이진 탐색 트리입니다.
AVL 트리는 BST가 편향 이진 트리에 가까워질수록 연산의 시간복잡도가 O(n)에 가까워진다는 문제점에 입각해서 발명되었습니다. 핵심은 BST를 균형 이진 트리로 유지시킨다는 것입니다.
균형 이진 트리로 유지시킨다는 것은 루트 노드를 기준으로 좌우 서브 트리의 높이차를 1 이하로 유지시킨다는 것입니다. 만약 이 조건을 만족시키지 못한다면 노드 위치 재조정을 수행해야 할 것입니다.
모든 노드에 대해 |HL - HR| ≤ 1 만족시킨다면 트리는 균형 잡혀있다. AVL 트리는 좌우 서브 트리의 높이차를 기준으로 균형 잡혀 있는지를 확인합니다.
따라서 모든 노드 N에 대해 Height(RightSubtree(N)) - Height(LeftSubtree(N)) ∈ {-1, 0, 1}을 만족시킬 경우 주어지는 이진 트리는 AVL 트리입니다. AVL TREE의 구...
![[Data Structure]AVL TREE](https://mblogthumb-phinf.pstatic.net/MjAyNDAxMjJfNjQg/MDAxNzA1OTMxMjA4NzMz.nVCK9kyLR_IzaDUg5EcnYod3F11SUi3_lNJZFYIACTUg.uo3r6e0wpYKxHqncFtaSNv_JvbcfdbMoMjKFKJBcDUkg.PNG.shinefilm1/image.png?type=w2)
#
AVL트리
#
자가균형이진탐색트리
#
균형
#
RR회전
#
RL회전
#
LR회전
#
logn
#
LL회전
#
Datastructure
#
자료구조
원문 링크 : [Data Structure]AVL TREE
![[Data Structure]우선순위 큐(Priority Queue)](https://mblogthumb-phinf.pstatic.net/MjAyMzEyMzBfMTYz/MDAxNzAzOTEzNDI5OTk3.BlY-fQGZMCYbsOvNq44rSFzgJlSs9LHULNRMxuLKIhcg.XKplsrjLxW4_DzTbIwMzEkE-psoKci9lUitHJubGPukg.PNG.shinefilm1/image.png?type=w2)
