AVL Tree에 대해 설명하세요
Keyword
회전,탐색,삽입,삭제
Script
AVL Tree는 스스로 균형을 잡는 binary search tree로, 왼쪽 sub tree의 높이와 오른쪽 sub tree의 높이의 차이를 표현하는 Balance Factor가 2 이상일 때 회전을 통해 균형을 맞춥니다. binary search tree의 단점인 편향트리를 방지하기위해 고안되었으며, AVL Tree는 항상 Tree의 높이를 log(n)으로 유지하기 때문에, 탐색, 삽입, 삭제에 O(log n)의 시간복잡도를 가집니다.
Additional
회전(Rotation)
탐색은 Balance Factor를 변경하지 않지만, 삽입과 삭제에서는 Balance Factor가 변경될 수 있기 때문에, BF의 절댓값이 2 이상일 때 불균형 노드를 기준으로 sub tree의 위치를 변경하는 회전 작업을 수행한다. 회전에는 LL, RR, LR, RL 불균형이 발생할 수 있으며, 각각의 규칙에 따라 Tree의 균형을 맞춘다.
LL Case
RR Case
*LR Case
RL Case
with programming