트리를 균형있게 만들어야 하는 이유

-> 트리의 높이가 h라면 이진 탐색 트리의 시간 복잡도는 O(h)가 된다.
즉, 한쪽으로만 치우친 트리는 트리로써의 역할을 제대로 하지 못하는 것이다!

트리를 균형있게 만들기 위한 방법 -> AVL 트리

AVL 트리의 특징

-> AVL 트리는 이진 탐색 트리의 속성을 가집니다.
-> 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 입니다.
-> 어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 높이 차이를 줄입니다.
-> AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN) 입니다.

AVL 트리에서 가장 중요한 요소는 Balance Factor(BF) 입니다.
Balance Factor(BF)는 ( 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이 ) 가 된다.

그럼 이제 AVL트리와 이진 탐색 트리의 차이점에 대해서 알아보자

예시 : 20, 15, 3, 12, 5, 11, 6, 40, 25, 18
1. 이진 탐색 트리

단순히 다음에 삽입되는 숫자가 이전 수보다 작으면 왼쪽 자식 노드에 더 크다면 오른쪽 자식노드에 위치시킨다면 삽입되는 숫자의 대소관계에 따라 그림과 같은 불균형한 이진 트리가 나올 수 있다.

2. AVL 트리
   AVL 트리는 BF라는 요소를 계속해서 계산해야 한다.
   좌, 우의 자식이 없다면 BF는 좌 우 모두 0이다.
   AVL 트리는 이 양쪽의 BF 차이가 1이하로 유지되어야 한다.

이렇게 작은 수가 삽입되면 왼쪽으로 삽입해가다 BF의 차이가 2가 되었기 때문에 양쪽의 BF를 맞춰주는 작업이 필요하다.
그렇기 때문에 양쪽의 BF를 맞출 수 있도록 트리 모양을 변경한다.
다음으로, 5를 넣으면 15보다 작으니 왼쪽 -> 3보다 크니 오른쪽 -> 12보다 작으니 왼쪽에 위치시키면 3과 15의 BF에서 문제가 발생한다.
이때,!! 삽입한 노드에서부터 올라가며 처음 만나는 노드를 수정해준다.
즉, 3 - 12 - 5로 이어지는 노드를 수정해야 한다.

11을 삽입하게 되면 15 - 5 - 12 로 이어지는 노드에 BF가 문제가 발생한다. 그렇기 때문에 수정해야 하는데 5가 왼쪽 노드, 12가 부모 노드, 15가 오른쪽 노드가 되려면 원래 12에 붙어있던 11과 15에 붙어 있던 20을 어떻게 처리해 줘야 할까?
11과 20을 다시 삽입해 준다.
]

AVL 트리 시간 복잡도

N은 트리의 노드 수입니다.
AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)입니다.

AVL 트리에서 BF가 안 맞을때 BF를 유지하는 방법 : 회전(Rotation)

LL(Left Left) case
y는 z의 왼쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우 right rotation을 수행하여 균형을 맞춥니다.

right rotation 수행 과정

y노드의 오른쪽 자식 노드를 z노드로 변경합니다.
z노드 왼쪽 자식 노드를 y노드 오른쪽 서브트리(T2)로 변경합니다.
y는 새로운 루트 노드가 됩니다.

struct node lefttRotate (struct node z) {
struct node y = z->right;
struct node T2 = y->left;

// y의 왼쪽 자식 노드를 z로 지정
y->left = z;
// z의 오른쪽 자식 노드를 T2로 지정
z->right = T2;

// 새로운 루트 노드 y를 반환
return y;
}

RR(Right Right) case
y는 z의 오른쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left rotation을 수행하여 균형을 맞춥니다.

left rotation 수행 과정

y노드의 왼쪽 자식 노드를 z노드로 변경합니다.
z노드 오른쪽 자식 노드를 y노드 왼쪽 서브트리(T2)로 변경합니다.
y는 새로운 루트 노드가 됩니다.

struct node rightRotate (struct node z) {
struct node y = z->left;
struct node T2 = y->right;

// y의 오른쪽 자식 노드를 z로 지정
y->right = z;
// z의 왼쪽 자식 노드를 T2로 지정
z->left = T2;

// 새로운 루트 노드 y를 반환
return y;
}

LR(Left Right) case
y는 z의 왼쪽 자식 노드이고, x는 y의 오른쪽 자식 노드인 경우 left , right 순으로 총 두 번의 rotation을 수행하여 균형을 맞춥니다.

y = z->left;
y = leftRotate(y);
z = rightRotate(z);

RL(Right Left) case
y는 z의 오른쪽 자식 노드이고, x는 y의 왼쪽 자식 노드인 경우, right, left 순으로 총 두번의 rotation을 수행하여 균형을 맞춥니다.

y = z->right;
y = rightRotate(y);
z = leftRotate(z);

AVL 트리를 만드는 모든 그림은 https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=dhdh6190&logNo=221062784111에서 발췌하였습니다.

트리를 균형있게 만들기 위한 방법 -> Red-Black 트리

1. Root Property : 루트노드의 색깔은 검정(Black)이다.

2. External Property : 모든 external node들은 검정(Black)이다.

3. Internal Property : 빨강(Red)노드의 자식은 검정(Black)이다.

== No Double Red(빨간색 노드가 연속으로 나올 수 없다.)

4. Depth Property : 모든 리프노드에서 Black Depth는 같다.

== 리프노드에서 루트노드까지 가는 경로에서 만나는 블랙노드의 개수는 같다.

(그냥 노드의 수는 다를 수 있음.)

그냥 BST의 성질에 맞게 삽입하다 보면 다음과 같은 상황이 발생할 수 있다.
이런 경우(Double Red)에 Red-Black 트리의 3번에 위배된다.
이런 Double Red를 해결하는 전략으로 2가지 방법이 있다.

1. Restructuring
2. Recoloring

해당 과정을 수행하는 경우

부모의 형제노드가 Black이냐 Red냐에 따라서 결정됩니다.
z가 삽입되었으니 z의 부모인 v의 형제 노드인 w에 따라 수행과정이 결정되는 것입니다.
w가 Black -> Restructuring
w가 Red -> Recoloring

먼저 Restructuring 부터 살펴보자.

1. 나(z)와 내 부모(v), 내 부모의 부모(Grand Parent)를 오름차순으로 정렬
2. 무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 올라간 가운데 있는 값을 검정(Black)으로 만들고 그 두자식들을 빨강(Red)로 만든다.
   위의 그림의 case1을 예시로 살펴보면 삽입된 노드(6)와 그 부모 노드(7), 부모의 부모 노드(4)를 잡아 수행합니다.

4 6 7을 오름차순으로 정렬하고 중간값을 부모로 하는 이진탐색트리 형태로 바꿉니다.

부모 노드를 Black으로 자식 노드를 Red로 바꾸고 원래 4의 자식이었던 2를 추가해주면 완료!!

Restructuring은 다른 서브트리에 영향을 끼치지 않기 때문에 단 한번이면 OK!!
Restructuring자체의 시간복잡도는 O(1)에 끝나지만, 어떤 노드를 insertion한 뒤 일어나므로 총 수행시간은 O(logn)

다음은 Recoloring

1. 현재 inset된 노드(z)의 부모와 그 형제(w)를 검정(Black)으로 하고 Grand Parent(내 부모의 부모)를 빨강(Red)로 한다.

2. Grand Parent(내 부모의 부모)가 Root node가 아니었을 시 Double Red가 다시 발생 할 수 있다.