C/C++의 AA 트리?

컴퓨터 과학에서 AA 트리는 정렬된 데이터를 효율적으로 저장하고 검색하기 위해 구현된 균형 트리의 한 형태로 정의됩니다. AA 트리는 항목의 효율적인 추가 및 삭제를 지원하는 이진 검색 트리의 한 형태인 레드-블랙 트리의 변형으로 취급됩니다. 레드-블랙 트리와 달리 AA 트리의 레드 노드는 오른쪽 하위 하위로만 추가할 수 있고 왼쪽 하위 하위로는 추가할 수 없습니다. 이 작업의 결과는 2-3-4 트리 대신 2-3 트리를 시뮬레이션하여 유지 관리 작업을 단순화합니다. 레드-블랙 트리의 유지 관리 알고리즘은 트리의 균형을 적절하게 유지하기 위해 7가지 다른 모양을 가정하거나 고려해야 합니다.

반면에 AA 트리는 오른쪽 링크만 빨간색일 수 있다는 엄격한 요구 사항으로 인해 두 가지 모양만 가정하거나 고려하면 됩니다. −

균형 회전

레드-블랙 트리는 노드당 1비트의 밸런싱 메타데이터(색상)가 필요한 반면, AA 트리는 정수 "레벨" 형태로 노드당 메타데이터의 O(log(log(N))) 비트가 필요합니다. 아래의 불변량은 AA 트리에 대해 유지됩니다. -

• 모든 리프 노드의 레벨은 하나로 취급됩니다.

• 모든 왼쪽 자식의 수준은 부모보다 정확히 하나 작습니다.

• 모든 오른쪽 자식의 수준은 부모의 수준과 같거나 하나 작습니다.

• 모든 오른쪽 손자의 수준은 조부모의 수준보다 엄격하게 낮습니다.

• 1보다 높은 레벨의 모든 노드에는 두 개의 자식이 있습니다.

AA 트리의 균형을 조정하는 것이 절차상 적-검정 트리의 균형을 조정하는 것보다 훨씬 쉽고 간단합니다.

AA 트리의 경우 균형을 복원하는 데 "기울기"와 "분할"의 두 가지 작업만 필요합니다. Skew는 왼쪽 수평 링크로 구성된 서브트리를 오른쪽 수평 링크로 구성된 서브트리로 교체하기 위해 오른쪽 회전으로 처리됩니다. 분할의 경우 두 개 이상의 연속적인 오른쪽 수평 링크로 구성된 하위 트리를 두 개의 연속적인 오른쪽 수평 링크가 더 적은 하위 트리로 교체하는 것은 왼쪽 회전 및 레벨 증가입니다. "skew" 및 "split" 작업은 아래에 설명되어 있습니다. -

함수 왜곡은

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
if nil(t) then
return nil
else if nil(left(t)) then
return t
else if level(left(t)) == level(t) then
   Exchange the pointers of horizontal left links.
   l = left(t)
left(t) := right(l)
right(l) := t
return l
else
return t
end if
end function

기능 분할은

   input: An AA tree that needs to be rebalanced is represented by a node, t.
   output: The rebalanced AA tree is represented by another node.
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
We have two horizontal right links. The middle node is taken, elevate it, and return it.
      r = right(t)
right(t) := left(r)
left(r) := t
level(r) := level(r) + 1
return r
else
return t
end if
end function

분할 -