"AVL 트리"는 자가 균형(Self-Balancing) 이진 검색 트리로, 좌우 서브 트리의 높이 차이가 1을 유지한다. 만약, 높이 차이가 1 이상이 나게 된다면 스스로 균형을 맞추어 높이 차이 1을 유지한다.  이전 포스팅에서 보았던 이진 검색 트리의 경우에는 최악의 경우 모든 연산의 시간복잡도가 $O(N)$이 되었다. 이는 다음과 같이 편향트리가 될 수 있기 때문이다.  따라서, AVL트리는 자가 균형을 통해 높이차를 1을 유지함으로써, 모든 연산의 평균 최악 모두 $O(logN)$을 보장한다.  Balance Factor 이진 트리에서 Balance Factor는 다음과 같이 정의된다. 즉, 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 값이다. AVL 트리는 BF값이 [-1, 1]범위 ..