AVL Tree

AVL 트리

BST의 한 종류
스스로 균형을 잡는 트리
(balance Factor를 이용)

• balance Factor?
  

  임의의 노드 x에 대해서
  bf(x) = h(LSubTree(x)) - h(RSubTree(x))
  (bf : balance factor,
  h : 높이
  LSubTree : 왼쪽 서브트리
  RSubTree : 오른쪽 서브트리)
  

AVL 트리의 특징

이 트리의 모든 노드들은
BF(x) = -1 or 0 or 1
(-1,0,1 의 집합에 해당 값이 속함)

삽입/삭제는 BST와 거의 동일하다

이 때, 삽입 혹은 삭제 후,
위의 규칙이 무너지면
재조정을 한다

요점은 양 서브트리의 높이 차가 1을 넘지 않도록 하는것

BF(x)가 해당 집합에서 벗어난 경우,
해당 x의 기준으로 ‘회전’하며 서브트리의 높이를 맞춰줌

BF가 정상적이지 않은 노드 N에 대하여
L : 왼쪽 자식
R : 오른쪽 자식

• 회전의 종류
  
  • LL (Left-Left) 회전: 발생 조건: 즉, L의 왼쪽 서브트리가 오른쪽 서브트리보다 더 높은 상황
    N을 기준으로 왼쪽 회전한다
    

  • LR (Left-Right) 회전:
    발생 조건: L의 오른쪽 서브트리가 왼쪽 서브트리보다 더 높고, N의 왼쪽 서브트리가 오른쪽 서브트리보다 더 높은 상황
    

    LR 회전은 먼저 L에 대한 RR (Right-Right) 회전을 수행하여 L의 오른쪽 서브트리를 오른쪽으로 회전
    그런 다음 N에 대한 LL (Left-Left) 회전을 수행하여 N을 왼쪽으로 회전
    

  • RL (Right-Left) 회전:
    발생 조건: R의 왼쪽 서브트리가 오른쪽 서브트리보다 더 높고, N의 오른쪽 서브트리가 왼쪽 서브트리보다 더 높은 상황
    

    RL 회전은 먼저 R에 대한 LL (Left-Left) 회전을 수행하여 R의 왼쪽 서브트리를 왼쪽으로 회전
    그런 다음 N에 대한 RR (Right-Right) 회전을 수행하여 N을 오른쪽으로 회전
    

  • RR (Right-Right) 회전:
    발생 조건: R의 오른쪽 서브트리가 왼쪽 서브트리보다 더 높고, N의 오른쪽 서브트리가 왼쪽 서브트리보다 더 높은 상황
    N을 오른쪽으로 회전
    

삽입/삭제 발생 시
해당 위치에서, 루트 노드로 거슬러 올라오며
BF를 확인하고 균형이 깨졌는지 확인하고
깨졌다면 조정한다

AVL 의 시간복잡도

평균, 최악의
탐색, 삭제, 삽입 모두 O(log n)

다만
균형을 엄격히 유지하는 트리이기에
삽입, 삭제 시
‘회전’을 많이 할 가능성이 높다
(무조건 root까지 올라가며 확인한다)

따라서 보통 삽입과 삭제가 ‘빈번히’일어나는 경우라면,
RB-Tree가 조금 더 유리한 자료구조이다
(이 경우, 회전을 적게하며,
‘색’을 통해 평균 높이가 더 낮게 유지될 가능성이 있음)

단순 검색 작업의 빈도가 더 높은 경우,
균형을 더 엄격히 잡는 AVL이
평균 높이가 더 낮게 유지될 가능성이 있기에
AVL을 사용

그렇기에 보통
dictinary(사전) 라던가
한번 만들어놓은 뒤, 삽입/삭제가 거의 없는 경우 사용 가능