AA나무

AA tree

컴퓨터 공학에서 AA 트리는 정렬된 데이터를 효율적으로 저장하고 검색하는데 사용되는 균형 트리의 한 형태이다.AA 나무들의 [1]이름은 그것들을 이론화한 아네 안데르손의 이름을 따서 지어졌다.

AA 트리는 항목의 효율적인 추가 및 삭제를 지원하는 이진 검색 트리의 한 형태인 빨간색-검은색 트리의 변형이다.빨간색-검은색 트리와 달리 AA 트리의 빨간색 노드는 오른쪽 하위 자식으로만 추가할 수 있습니다.즉, 빨간색 노드는 왼쪽 서브자식이 될 수 없습니다.따라서 2-3-4 트리가 아닌 2-3 트리가 시뮬레이션되므로 유지보수 작업이 대폭 간소화됩니다.빨간색-검은색 트리의 유지 보수 알고리즘에서는 트리의 균형을 적절하게 맞추기 위해 7가지 모양을 고려해야 합니다.

Red Black Shape Cases.svg

반면 AA 트리는 올바른 링크만 빨간색으로 할 수 있다는 엄격한 요건 때문에 다음 두 가지 셰이프만 고려하면 됩니다.

AA Tree Shape Cases.svg

회전 밸런스

빨간색-검은색 트리는 노드당 1비트의 메타데이터(색상) 밸런싱을 필요로 하는 반면, AA 트리는 정수 "레벨"의 형태로 노드당 O(log(log(N)) 비트의 메타데이터를 필요로 한다.AA 트리에는 다음 불변량이 있습니다.

  1. 모든 리프 노드의 레벨은 1입니다.
  2. 모든 왼쪽 자녀들의 수준은 부모들의 수준보다 정확히 한 개 적다.
  3. 모든 올바른 자녀들의 수준은 부모들의 수준과 같거나 그 이하이다.
  4. 모든 올바른 손자의 수준은 조부모의 수준보다 엄격히 낮다.
  5. 1보다 큰 레벨의 각 노드에는 2명의 자녀가 있습니다.

자녀의 수준이 부모의 수준과 동일한 링크를 수평 링크라고 하며 빨간색-검은색 트리의 빨간색 링크와 유사합니다.개별 우측 수평 링크는 허용되지만 연속되는 링크는 금지됩니다.좌측 수평 링크는 모두 금지됩니다.이는 레드-블랙 트리의 유사한 제약사항보다 더 제한적인 제약사항이며, 결과적으로 AA 트리의 재조정이 레드-블랙 트리의 재조정보다 절차적으로 훨씬 간단하다.

삽입과 삭제는 일시적으로 AA 트리의 균형을 잃게 할 수 있다(즉, AA 트리 불변성을 위반하게 한다).균형을 복원하려면 "skew"와 "split" 두 가지 작업만 필요합니다.스큐는 왼쪽 수평 링크를 포함하는 서브트리를 오른쪽 수평 링크를 포함하는 서브트리로 대체하기 위한 오른쪽 회전입니다.스플릿은 2개 이상의 연속된 우측 수평 링크를 포함하는 서브트리를 2개 적은 우측 수평 링크를 포함하는 서브트리로 대체하기 위한 좌측 회전 및 레벨 상승입니다.균형을 유지하는 삽입과 삭제의 실장은, 스큐 조작과 스플릿 조작에 의존해, 필요에 따라서만 트리를 변경하는 것으로, 발신자에게 스큐와 스플릿 중 어느 쪽을 선택할지를 결정하게 하는 것이 아니라, 심플하게 됩니다. 

함수 스큐가 입력됩니다.T는 재조정이 필요한 AA 트리를 나타내는 노드입니다.출력:재조정된 AA 트리를 나타내는 또 다른 노드. 0(T)이면 Nil을 반환하고, 0(T)이면 Nil을 반환하고, level(왼쪽(T)== level(T)이면 T를 반환하고, 수평 왼쪽 링크의 포인터를 스왑합니다.L = left(T) left(T) : = right(L) right(L) : = T return L, end function인 경우 T end를 반환합니다.

스큐:

함수 분할이 입력됩니다.T는 재조정이 필요한 AA 트리를 나타내는 노드입니다.출력:재조정된 AA 트리를 나타내는 또 다른 노드입니다. 0(T)이면 Nil을 반환하고 0(오른쪽)이면 Nil을 반환하고, 레벨(T) == 레벨(오른쪽(T))이면 T를 반환합니다. 그러면 2개의 수평 오른쪽 링크가 있습니다.  중간 노드를 들어 올린 후 반환하십시오.R = right(T) right(T) : = left(R) left(R) : = T level(R) : = level(R) + 1 Return(R) R이 반환되고 그렇지 않으면 T end가 반환됩니다.

분할:

삽입

삽입은 일반 바이너리 트리 검색 및 삽입 절차에서 시작합니다.그런 다음 콜 스택이 해제되면(검색 재귀 구현을 전제로), 트리의 유효성을 확인하고 필요에 따라 로테이션을 수행할 수 있습니다.수평 좌측 링크가 발생하면 스큐가 실행되고, 2개의 수평 우측 링크가 발생하면 분할이 실행되어 현재 서브트리의 새로운 루트노드 레벨이 높아질 수 있습니다.상기와 같은 코드에서는 레벨(T)의 증분에 주의해 주세요.이 경우 수정 내용이 리프에서 버블이 발생할 때 트리의 유효성을 계속 확인해야 합니다. 

함수 삽입은 삽입할 값인 X와 삽입할 트리의 루트인 T를 입력합니다.출력: X를 포함한 균형 잡힌 버전T 。일반 바이너리 트리 삽입 절차를 수행합니다.만약 X< 만약 nil(T) 다음 X수익률과 node(X, 1, 닐, 닐) 다른 새로운 리프 노드를 만듭니다.;value(T) 다음 left(T):)insert(X, 왼쪽(T)) 다른 만약 X입니다.;value(T) 다음 right(T):)insert(X, 그렇죠(T))앙 사건에 새로운 노드가 만들어진 정확한 아이나subtree 변화의 근본에 대 자기 호출의 결과 설정합니다.d만약 NX == 값(T)의 대소문자가 지정되지 않은 경우. 위에서 설명한 바와 같이 삽입은 효과가 없습니다. 구현자는 다른 동작을 원할 수 있습니다.스큐를 실행한 후 분할합니다. 회전 여부를 결정하는 조건은 위와 같이 절차 내부에 있습니다.T : = 스큐(T) T : = 분할(T) 반환 T 엔드 함수

삭제

대부분의 균형잡힌 이진 트리와 마찬가지로 내부 노드의 삭제는 내부 노드를 트리에 있거나 구현자의 변덕에 따라 가장 가까운 이전 노드 또는 후속 노드와 스왑함으로써 리프 노드의 삭제로 바뀔 수 있습니다.선행 링크를 취득하는 것은 왼쪽 링크 1개와 나머지 오른쪽 링크를 모두 따라가면 됩니다.마찬가지로 null 포인터가 발견될 때까지 오른쪽으로 한 번 이동한 후 왼쪽으로 이동하여 후계자를 찾을 수 있습니다.2자녀를 가진 1개 이상의 모든 노드의 AA 속성으로 인해 후속 노드 또는 이전 노드는 레벨1이 되어 삭제가 간단해집니다.

트리의 균형을 재조정하기 위해서는 몇 가지 방법이 있습니다.Andersson이 원래 논문에서 설명한 것이 가장 단순하며, 실제 구현에서는 보다 최적화된 접근방식을 선택할 수 있지만 여기에 설명되어 있습니다.삭제 후 트리 유효성을 유지하기 위한 첫 번째 단계는 자녀가 2단계 이하인 노드 또는 누락된 노드의 수준을 낮추는 것입니다.그런 다음 전체 레벨을 치우쳐 분할해야 합니다.이 접근방식은 개념적으로 설명하면 쉽게 이해할 수 있는 세 가지 단계가 있기 때문에 선호되었습니다.

  1. 필요에 따라서 레벨을 낮춥니다.
  2. 레벨을 비스듬히 합니다.
  3. 레벨을 분할합니다.

그러나 이번에는 노드만 있는 것이 아니라 전체 레벨을 스큐하고 분할해야 하기 때문에 코드가 복잡합니다. 

function delete는 삭제할 값인 X와 삭제할 트리의 루트인 T를 입력합니다.출력: T, 밸런스, 값 X 없음. X > 값(T)이면 T else를 반환하고, X < 값(T)이면 right(T): = delete(X, right(T)), X < 값(T)이면 lef : = delete(X, left(T)이면 right(T)를 반환하고, 그렇지 않으면 리프 케이스를 줄일 수 있습니다.리프(T)가 0(왼쪽(T)이면 오른쪽(T)을 반환하고, 0(T)이면 오른쪽(T)을 반환하고, L := successor(T) right(T) := delete(L), right(T) value(T) value(T)를 반환합니다. 그렇지 않으면 L := prevalue(T) := delete(Left)e 트리 필요에 따라서, 이 레벨의 모든 노드의 레벨을 내린 후, 새로운 레벨의 모든 노드를 스큐 및 분할합니다.T : = decreed_level (T) T : = skew (T) right (T) : = skew (right (T) right (T) right (T) right (T)) right (T) right (T) right (T) right (T) right (T) : = skew (right (T) returnal (t) return) returning : = sketurning : = sketurning : = sketurning : un)
function decrement_level이 입력됩니다.T는 레벨을 건너뛰는 링크를 삭제하는 트리입니다.출력:T는 레벨이 낮아졌다.should_be = min(level(left(T)), level(right(T)), level(T)이 되어야 하는 경우 =이 < level(right(T)이 되어야 하는 경우 =이 되어야 하며 T가 함수를 반환하는 경우 level(right(T): =이 종료되어야 합니다.

이 알고리즘에 의한 삭제의 좋은 예는 Anderson의 논문에 기재되어 있습니다.

성능

AA 트리의 성능은 빨간색-검은색 트리의 성능과 동일합니다.AA 트리가 빨간색-검은색 트리보다 더 많은 회전을 하는 반면, 단순한 알고리즘은 더 빠른 경향이 있으며, 이 모든 것이 유사한 성능으로 귀결됩니다.빨간색-검은색 트리는 AA 트리보다 성능이 더 일관되지만, AA 트리는 더 평평한 경향이 있어 검색 [2]시간이 약간 더 빠릅니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Andersson, Arne (1993). "Balanced Search Trees made Simple". WADS '93: Proceedings of the Third Workshop on Algorithms and Data Structures. Springer-Verlag: 60–71. ISBN 3540571558.
  2. ^ "A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75)" (PDF). Archived from the original (PDF) on 2014-03-27. Retrieved 2010-10-17.

외부 링크