AVL 트리 개념 정리
이 전 포스팅으로 이진 탐색 트리나, RED-BLACK TREE를 살펴봤다. 이진 탐색 트리의 비효율성을 개선하기 위해 균형 이진 탐색 트리(Balanced Binary Search Tree)의 개념이 등장했고 RB-Tree가 이 균형 이진 탐색 트리의 종류 중 하나였다. 이번에는 또 다른 균형 이진 탐색 트리인 AVL 트리에 대해 정리하겠다.AVL 트리란?AVL 트리라는 이름은 이 자료구조를 만든 두 사람, Adelson-Velsky와 Landis의 이름을 따서 지어졌다.모든 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 이진 탐색 트리(BST)이다.이 높이 차이를 균형 인수(Balance Factor)라고 하며,Balance Factor=(left subtree height)−..
