C AVL 트리(AVL Tree) 설명
※ 트리의 개념과 이진탐색트리를 포함해서 설명이 진행되므로 모르면 아래 링크로 확인 !
C 트리(Tree) 설명
트리 - 비선형 자료구조의 일종이다. - 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조이다. ※ 사용 예로 컴퓨터의 디렉터리 구조를 들 수 있다. 용어 정리 1. 노드(Node) : 트리의 구성요소
srdeveloper.tistory.com
이진탐색트리의 문제점
- 트리의 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다.
※ 위와 같은 순서로 데이터가 누적이 된 상태에서 D의 값을 찾으려면 모든 노드를 탐색하게되며, 이렇게 되면 이진 탐색 트리를 쓰는 의미가 없어진다.
이러한 이진탐색트리의 단점을 해결한 트리를 가리켜 균형잡힌 이진트리라하며 그 중 AVL트리에 대해 설명하고자한다.
AVL 트리
- Adelson-Velsky and Landis에서 따온 이름이다.
- 이진탐색트리의 단점을 해결한 균형잡힌 이진트리 중 처음으로 발명되었다.
- AVL 트리는 균형의 정도를 표현한 균형 인수(Balance Factor)를 사용한다.
※ 계산법 : 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이
- 균형이 무너졌을 때, 구조의 재조정(Rebalancing)의 종류는 LL, RR, LR, RL이 있다.
균형 인수(Balance Factor)
- 노드 위에 적힌 숫자가 균형 인수이다.
- 균형 인수의 절대값이 크면 클수록 트리의 균형이 무너진 상태이다.
※ 따라서 균형 인수의 절대값이 2 이상인 경우에 균형을 잡기 위한 재조정을 진행한다.
LL(Left Left), RR(Right Right) 상태
- 위 그림의 왼쪽 트리를 보면 루트 노드의 균형인수가 2이다.
- 왼쪽의 자식 노드가 연이어 연결된 상태인데 이런 상태를 가리켜 LL(Left Left)상태라고 한다.
※ 반대로 오른쪽으로 자식 노드가 연이어져 있으면 RR(Right Right)상태라 한다.
- 이러한 LL상태에서 불균형 해소를 위한 리밸런싱을 LL회전이라고 한다.
※ 반대로 오른쪽으로는 RR회전이라 한다.
- 키값이 5인 노드를 Child node(이하 CNode), 키값이 10인 노드를 Parent node(이하 PNode)라고 한 뒤, LL회전의 방법은 다음과 같다.
1. PNode를 CNode의 오른쪽 자식으로 보낸다.
※ 이 때, PNode가 CNode의 자식 노드가 되므로 PNode의 기존 자식 참조값은 비워준다.
2. CNode를 Root노드로 설정한다.
※ RR은 반대로 생각해주면 된다.
LR(Left Right), RL(Right Left) 상태
- 왼쪽 자식 노드에 오른쪽 자식 노드가 연결된 상태인데 이런 상태를 가리켜 LR(Left Right)상태라고 한다.
※ 반대로 오른쪽 자식 노드에 왼쪽 자식노드가 이어져있으면 RL(Right Left)상태라 한다.
- 이러한 LR 상태에서 LL회전을 하게되면 이진탐색트리의 규칙에 위배되므로 왼쪽 자식 노드를 RR회전을 먼저 진행해 불균형 상태를 LL로 만든뒤, 루트 노드를 LL회전 해줘서 리밸런싱을 한다.
- 키값이 1인 노드를 Leaf node(이하 LNode), 키값이 5인 노드를 Child node(이하 CNode), 키값이 10인 노드를 Parent node(이하 PNode)라고 한 뒤, LL회전의 방법은 다음과 같다.
1. 먼저 CNode를 RR회전을 해줘서 LNode를 CNode의 자리에 옮기고 CNode를 LNode의 왼쪽 자식으로 옮긴다.
※ 이 과정이 끝나면 트리가 LL상태가 되어있다.
2. (LL 회전 시작) PNode를 LNode의 오른쪽 자식으로 보낸다.
3. LNode를 Root 노드로 설정한다.
※ RL은 반대로 생각해주면 된다. (자식 노드를 LL회전한 뒤 Root 노드를 RR회전)