AVL Tree

AVL Tree

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