AVL Tree 자가균형 이진 탐색트리의 한 유형 각 노드의 서브트리 높이 차이가 최대 1을 유지하도록 스스로 균형을 유지하는 트리 이 서브트리의 높이 차이를 균형계수(BalanceFactor, BF)라 한다. 그렇기 때문에 삽입, 삭제 연산을 수행할 때마다 트리의 균형계수를 체크하고, 균형계수가 1보다 커질 때 회전(Rotation) 연산을 통해 균형을 유지한다. 검색, 삽입, 삭제 모두 O(logN) 하지만 삽입, 삭제시마다 회전연산을 수행하기에 연산속도가 느릴 수 있다. 회전연산의 종류 왼쪽 - 왼쪽 오른쪽 - 오른쪽 Single rotation 왼쪽 - 오른쪽 오른쪽 - 왼쪽 double rotation 특징 이진 검색 트리 모든 노드의 두 하위 트리의 높이는 최대 1까지 차이가 난다. 트리의 모..