AA 트리(AA tree)는 컴퓨터 과학에서 정렬된 데이터를 효율적으로 저장하고 탐색하는 데 사용되는 균형 트리의 한 형태이다. AA 나무는 창시자인 스웨덴 컴퓨터 과학자 아르네 안데르손(Arne Andersson)의 이름을 따서 명명되었다.[1]
AA 트리는 항목의 효율적인 추가 및 삭제를 지원하는 이진 탐색 트리의 형태인 레드-블랙 트리의 변형이다. 레드-블랙 트리와 달리 AA 트리의 레드 노드는 오른쪽 하위 자식으로만 추가될 수 있다. 즉, 레드 노드는 왼쪽 하위 자식이 될 수 없다. 그 결과 2–3–4 트리 대신 2–3 트리가 시뮬레이션되어 유지 관리 작업이 크게 단순화된다. 레드-블랙 트리의 유지 관리 알고리즘은 트리의 균형을 적절하게 유지하기 위해 7가지 다른 모양을 고려해야 한다.
![]()
반면에 AA 트리는 오른쪽 링크만 빨간색이 될 수 있다는 엄격한 요구 사항으로 인해 두 가지 모양만 고려하면 된다.
같이 보기
각주
외부 링크
