C/C++에서의 AA 트리(AA Tree)란? 개념과 균형 유지 방법 총정리

AA 트리란 무엇인가?

컴퓨터 과학에서 AA 트리(AA Tree)는 정렬된 데이터를 효율적으로 저장하고 검색하기 위해 구현된 균형 트리(balanced tree)의 한 형태입니다. AA 트리는 이진 탐색 트리(binary search tree)의 일종인 레드-블랙 트리(red-black tree)의 변형으로 간주되며, 항목의 삽입과 삭제를 효율적으로 지원합니다.

레드-블랙 트리와 달리, AA 트리에서는 빨간색 노드가 오른쪽 자식(right subchild)으로만 추가될 수 있으며 왼쪽 자식으로는 추가될 수 없습니다. 이러한 제약 조건의 결과로 AA 트리는 2-3-4 트리 대신 2-3 트리를 시뮬레이션하게 되며, 이는 유지 보수 연산을 크게 단순화시킵니다.

레드-블랙 트리의 유지 보수 알고리즘은 트리를 적절히 균형 있게 만들기 위해 최대 7가지 서로 다른 형태를 고려해야 합니다.

반면 AA 트리는 '빨간 링크는 오른쪽에만 존재할 수 있다'는 엄격한 요구 사항 덕분에 단 두 가지 형태만 고려하면 됩니다.

균형 회전(Balancing Rotations)과 레벨(Level)

레드-블랙 트리가 노드당 1비트의 균형 메타데이터(색상 정보)만 필요한 것과 달리, AA 트리는 노드당 O(log(log(N))) 비트의 메타데이터가 필요합니다. 이 메타데이터는 정수형 "level(레벨)" 값으로 표현됩니다. AA 트리에는 다음과 같은 불변식(invariant)이 성립합니다.

• 모든 리프 노드(leaf node)의 레벨은 1입니다.
• 모든 왼쪽 자식의 레벨은 부모보다 정확히 1 작습니다.
• 모든 오른쪽 자식의 레벨은 부모와 같거나 1 작습니다.
• 모든 오른쪽 손자 노드(right grandchild)의 레벨은 조부모(grandparent)보다 엄격하게 작습니다.
• 레벨이 1보다 큰 모든 노드는 반드시 두 개의 자식을 가집니다.

AA 트리의 재균형(re-balancing) 절차는 레드-블랙 트리의 재균형보다 훨씬 간단합니다. AA 트리에서 균형을 복원하는 데 필요한 연산은 단 두 가지, 즉 skew와 split입니다.

Skew 연산

Skew는 오른쪽 회전(right rotation)으로, 왼쪽 수평 링크(left horizontal link)로 구성된 서브트리를 오른쪽 수평 링크로 구성된 서브트리로 교체하는 연산입니다.

function skew is
    input: 재균형이 필요한 AA 트리의 노드 t
    output: 재균형된 AA 트리의 노드
if nil(t) then
    return nil
else if nil(left(t)) then
    return t
else if level(left(t)) == level(t) then
    // 왼쪽 수평 링크의 포인터를 교환한다.
    l = left(t)
    left(t) := right(l)
    right(l) := t
    return l
else
    return t
end if
end function

Split 연산

Split은 왼쪽 회전(left rotation)과 레벨 증가를 통해, 두 개 이상의 연속된 오른쪽 수평 링크로 구성된 서브트리를 연속된 오른쪽 수평 링크가 두 개 더 적은 서브트리로 교체하는 연산입니다.

function split is
    input: 재균형이 필요한 AA 트리의 노드 t
    output: 재균형된 AA 트리의 노드
if nil(t) then
    return nil
else if nil(right(t)) or nil(right(right(t))) then
    return t
else if level(t) == level(right(right(t))) then
    // 두 개의 오른쪽 수평 링크가 존재한다.
    // 중간 노드를 끌어올려 반환한다.
    r = right(t)
    right(t) := left(r)
    left(r) := t
    level(r) := level(r) + 1
    return r
else
    return t
end if
end function

마무리

AA 트리는 레드-블랙 트리의 복잡한 균형 조건을 단순화하여 구현 난이도를 크게 낮춘 자료구조입니다. skew와 split이라는 두 가지 기본 연산만으로 트리의 균형을 유지할 수 있기 때문에, C/C++에서 균형 이진 탐색 트리를 직접 구현하고자 할 때 훌륭한 선택지가 됩니다. 특히 코드가 간결하고 디버깅이 상대적으로 쉬워 학습용 및 실무용 모두에 적합합니다.