AVL 트리(균형 이진 탐색 트리) AVL 트리란? 오른쪽 서브트리의 높이와 왼쪽 서브트리의 높이 차이가 1이하인 이진 탐색 트리를 말한다. 여기서 말하는 높이 차이를 균형 인수(Balance Factor, BF)라고 한다. 이진 탐색 트리의 한 종류이며, 이진 탐색 트리는 이진 트리의 한 종류이다. 따라서, 이진트리와 이진탐색트리의 특징을 모두 갖고 있다. 특징 이진 탐색 트리의 속성을 가진다. 어떤 노드라도 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 크지 않다. (= 최대 1이다.) 높이 차이가 1보다 커지면 회전(Rotation) 을 통해 균형을 맞춰 높이 차이를 줄인다. 삽입, 검색, 삭제의 시간 복잡도가 O(log N)이다. (N : 노드의 개수) 사용하는 이유 이진 탐색 트리를 만들..