반응형
AVL 트리
AVL 트리는 이진 트리의 단점 (편향 이진 트리의 경우 O(N))을 보완하기 위해 스스로 균형을 잡는 트리를 의미한다. 이 때 트리의 균형을 맞추기 위해 (좌측 자식 노드의 깊이 - 우측 자식 노드의 깊이)의 절댓값이 1이하인 경우를 유지하며, 초과할 경우 회전을 통해 균형을 맞춘다.
- 노드의 균형도는 다음과 같이 좌측 균형도 - 우측 균형도를 통해 계산한다.
불균형 트리
- 다음과 같이 균형도의 절댓값이 2 이상이 된 경우를 불균형 트리라고 부르며, 균형도가 양수이면 좌측 비대 트리, 음수이면 우측 비대 트리라고 부른다. 불균형도의 양수와 음수를 판단하여 LL, RR, LR, RL 회전을 사용하여 불균형을 해결한다.
LL 회전
- LL 회전은 이름 그대로 Left, Left로 치우쳐서 불균형이 발생한 경우로, 왼쪽 자식 노드를 현재 부모노드로 승격하고 현재 부모노드를 왼쪽 자식 노드의 오른쪽 자식 노드로 만드는 방식이다. 이때 주의할 점은 4번 노드의 우측 자식 존재 여부이다. 존재한다면 6번 노드의 우측 자식 노드로 연결해야 한다.
RR 회전
- RR 회전은 LL과 반대로 오른쪽으로 치우친 경우로 부모노드의 우측 자식노드의 좌측 자식 노드의 존재 여부를 판단하는 것만 주의하면 LL 방식과 동일하다.
LR 회전
- LR 회전은 LEFT, RIGHT 로 인해 불균형이 발생한 경우에 사용하는 회전방식이며, LL 회전과 RR 회전이 섞여있는 상태이다. 순서는 RR,LL 순서로 간다. 회전의 이름인 LR에서 반대로 RL순으로 간다고 이해하면 기억하기 쉽다.
- 다음과 같이 RR 회전을 먼저 적용 시킨다. RR 회전에서 중간 노드의 좌측 노드가 존재하므로 이부분을 신경써서 처리하자.
- 동일한 방법으로 LL 회전을 적용 시키면 균형 트리가 완성된다.
RL 문제는 RR 문제와 RL 문제가 합쳐져 있는
RL 회전
- RL 회전은 LL 회전, RR 회전 순서대로 적용하면 해결할 수 있다.
- LL 회전을 적용하면 다음과 같이 트리를 구성할 수 있다. 이때도 마찬가지로 LL 회전에서 7번 노드의 우측 자식 노드를 주의하자.
- 다음으로 남은 RR 회전을 적용하면 다음과 같이 균형 트리를 만들 수 있다.
REFERENCES
반응형
