[자료구조] Avl Tree

🌳 AVL 트리(Adelson-Velsky and Landis Tree)란?AVL 트리는 이진 탐색 트리(Binary Search Tree, BST)의 일종으로,트리의 균형을 유지하여 탐색, 삽입, 삭제 연산을 O(log n) 시간 복잡도로 보장하는 자기 균형 이진 탐색 트리다.   특징균형 인수(Balance Factor, BF)어떤 노드의 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이가능한 값: -1, 0, 1BF = 2 또는 -2가 되면 불균형 → 회전(Rotation) 필요자동 균형 유지삽입/삭제 시 불균형 발생 → 회전 연산으로 균형 유지탐색, 삽입, 삭제 모두 O(log n) 여기서 주목할 점은 균형을 유지하기위해 하는 회전 연산이다. 근데 왜 균형을 유지해야할까? 얘도 어차피 이진트리 아닌가..