C/C++의 AA 트리란 무엇입니까?

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

레드-블랙 트리와 달리 AA 트리는 올바른 링크만 빨간색일 수 있으므로 두 가지 모양만 가정하거나 고려하면 됩니다.

균형 회전

Red-black 트리에는 노드당 하나의 균형 메타데이터 비트(색상)가 필요한 반면, AA 트리에는 노드당 O(log(log(N))) 메타데이터 비트가 필요합니다. 정수 "레벨"입니다. AA 트리에는 다음 불변성이 적용됩니다.

• 각 리프 노드의 레벨은 1로 간주됩니다.

• 각 왼쪽 하위 노드의 레벨은 상위 노드보다 1 낮습니다.

• 각 오른쪽 하위 노드의 레벨은 상위 노드와 같거나 1 작습니다.

• 각 오른쪽 손자 노드의 수준은 조부모 노드보다 엄격히 작습니다.

• 레벨이 1보다 큰 모든 노드에는 두 개의 하위 노드가 있습니다.

AA 트리의 균형을 재조정하는 것은 레드-블랙 트리의 균형을 재조정하는 것보다 훨씬 간단합니다.

AA 트리에서는 균형을 복원하는 데 "기울기"와 "분할"이라는 두 가지 작업만 필요합니다. 기울이기는 오른쪽 회전으로 처리되어 왼쪽 수평 링크로 구성된 하위 트리를 오른쪽 수평 링크로 대체합니다. 분할(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

함수 분할 is

번역은 다음과 같습니다.

함수 분할은

   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

분할 -

위 내용은 C/C++의 AA 트리란 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!