AA Tree

AA Tree

• Data structure
• 2021년 6월 3일

RB-Tree를 응용한 트리로 RB-Tree의 많은 조건을 일부 제거하여 구현을 더 간단하게 만든 트리로 균형을 맞추기 위해 레벨의 개념을 사용한 트리이다. 부모와 레벨이 같은 자식 노드의 연결을 수평 링크라고 하며, 이 노드를 구분하기 위해 RED라는 개념을 이용한다. 1. 특징 왼쪽 자식은 RED가 될 수 없다. 연속으로 RED가 올 수 없다. (이중 RED 불가 == 이중 수평 링크) 루트에서 null가지 leafnode까지의 경로에는 동일한 수의 블랙 노드가 존재한다. (RB Tree의 규칙) 모든 leaf node의 레벨은 1이다. 모든 왼쪽 자식의 레벨은 부모의 레벨보다 1 낮다. 모든 오른쪽 자식의 레벨은 부모와 같거나 1 낮다. 모든 오른쪽 손자의 레벨은 할아버지 노드보다 낮다. 1보다 큰 레벨의 모든 노드들은 2개의 자식을 갖는다. 왼쪽 트리를 얼핏 보면 RB-Tree같지만 왼쪽 자식은 RED를 갖지 않는 AA-Tree이고, 이를 레벨을 기준으로 보면 오른쪽과 같이 그려 볼 수 있다....