📒 CS/📝 Data Structure
[Data Structure] AVL 트리
AVL 트리 AVL 트리 (Adelson-Velsky and Landis tree)는 이진 탐색 트리가 데이터 삽입 순서로 인해 선형적인 형태의 트리가 되는 것을 방지하고자 스스로 균형을 잡는 이진 탐색 트리를 말한다. 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다. (균형 이진 트리의 일종) 데이터 삽입, 삭제시 균형이 항상 맞도록 트리 일부를 왼쪽 혹은 오른쪽으로 회전시킨다 (리밸런싱). 🔹가장 처음 나온 자가 균형 이진 트리 🔹red-black tree보다 균형은 훨씬 잘 잡힘 🔹red-black tree보다 삽입, 삭제가 느림 🔹서브 트리 높이 차이가 1보다 커지면 회전(리밸런싱) 통해 차이 줄임 💡탐색, 삽입, 삭제 시간 복잡도: O(logN) Balance Factor..
