AA 트리

AA 트리(AA tree)는 컴퓨터 과학에서 정렬된 데이터를 효율적으로 저장하고 탐색하는 데 사용되는 균형 트리의 한 형태이다. AA 나무는 창시자인 스웨덴 컴퓨터 과학자 아르네 안데르손(Arne Andersson)의 이름을 따서 명명되었다.

AA 트리는 항목의 효율적인 추가 및 삭제를 지원하는 이진 탐색 트리의 형태인 레드-블랙 트리의 변형이다. 레드-블랙 트리와 달리 AA 트리의 레드 노드는 오른쪽 하위 자식으로만 추가될 수 있다. 즉, 레드 노드는 왼쪽 하위 자식이 될 수 없다. 그 결과 2–3–4 트리 대신 2–3 트리가 시뮬레이션되어 유지 관리 작업이 크게 단순화된다. 레드-블랙 트리의 유지 관리 알고리즘은 트리의 균형을 적절하게 유지하기 위해 7가지 다른 모양을 고려해야 한다.

파일:Red Black Shape Cases.svg

반면에 AA 트리는 오른쪽 링크만 빨간색이 될 수 있다는 엄격한 요구 사항으로 인해 두 가지 모양만 고려하면 된다.

파일:AA Tree Shape Cases.svg

 같이 보기 
 레드-블랙 트리
 B 트리
 AVL 트리
 스케이프고트 트리

 각주 

 외부 링크 
 A. Andersson. Balanced search trees made simple
 A. Andersson. A note on searching in a binary search tree
 BSTlib  – an open source AA tree library for C by trijezdci
 AA Visual 2007 1.5 - OpenSource Delphi program for educating AA tree structures
 Thorough tutorial Julienne Walker with lots of code, including a practical implementation
 Object Oriented implementation with tests
 A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67–75) – comparison of AA trees, red–black trees, treaps, skip lists, and radix trees
 An Objective-C implementation
 Python implementation

분류:탐색 트리