C# 자료구조 정리..

z균형 이진 탐색트리

VL트리는 Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리로서 각 노드에서 왼쪽 서브 트리의 높이와
오른쪽 서브 트리의 높이 차이가 1이하인 이진 탐색 트리를 말한다.
AVL 트리는 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. 따라서 AVL트리는
균형 트리가 항상 보장되기 때문에 탐색시간이 O(log₂n)시간안에 끝나게 된다.
또한 삽입과 삭제 연산도 O(log₂n)시간안에 할 수 있다. 

AVL트리에서 균형인수는 매우 중요하다. 

균형인수란 왼쪽서브트리의 높이 - 오른쪽 서브트리의 높이로 정의된다.
모든 노드의 균형인수가 ±1 이하이면 AVL 트리이다. 

(그림 출처 : SafariBooks )

* 균형 인수

여기서 노드 아래의 숫자 -1, 0, 1 이것이 의미하는 게 왼쪽 자식 노드들의 높이 - 오른쪽 자식 노드들의 높이 라고 생각하면 됩니다. 정확한 명칭은 균형 인수 입니다. 균형인수의 범위는 균형이 맞춰져 있을 경우 : -1 ~ 1 이고, 균형이 깨지는 경우가 +2, -2 입니다. 이 균형 인수를 계산 하는 방법은 앞서 말했듯이 왼쪽 자식노드의 높이 - 오른쪽 자식노드의 높이 입니다. 

예를 들자면,

노드 82를 보면 왼쪽 자식 노드의 높이가 2, 오른쪽 자식 노드의 높이가 1 이 되어 2-1을 해주어 1이 됩니다. 

한 가지 더 예를 들자면, 노드 60을 보시면 왼쪽 자식노드의 높이가 0, 오른쪽 자식노드의 높이가 1 입니다. 따라서 0 - 1 을 해주어 -1이 되는 것입니다.

삽입 연산

균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 것은 삽입과 삭제 연산시이다. 삽입 연산시에는 삽입되는
위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다. 따라서 새로운 노드의 삽입 후
불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형인수가 ±2가 된 가장 가까운 조상 노드의 서브 트리들에 대해
다시 균형을 잡아야 한다. 그 외의 다른 노드들은 일체 변경할 필요가 없다. 

※ AVL트리에서 균형이 깨지는 경우
AVL트리에서 균형이 깨지는 경우는 다음의 4가지 경우가 있다. 새로 삽입된 노드를 N,가장 가까우면서 균형인수가
±2가 된 조상 노드를 A라고 하자.

(1) LL타입 : N이 A의 왼쪽 서브트리의 왼쪽에 삽입되는 경우(A노드의 왼쪽노드의 왼쪽에 삽입)
(2) LR타입 : N이 A의 왼쪽 서브트리의 오른쪽에 삽입되는 경우 (A노드의 왼쪽노드의 오른쪽에 삽입)
(3) RR타입 : N이 A의 오른쪽 서브트리의 오른쪽에 삽입되는 경우(A노드의 오른쪽노드의 오른쪽에 삽입)
(4) RL타입 : N이 A의 오른쪽 서브트리의 왼쪽에 삽입되는 경우(A노드의 오른쪽노드의 왼쪽에 삽입)ㅡ

말이 조금 헷갈리지만 당연한 모든 경우의 수 이다. (왼쪽-왼쪽,왼쪽-오른쪽,오른쪽-오른쪽, 오른쪽-왼쪽)
LL과 RR은 대칭이고 LR과 RL도 대칭이다. 재균형시키는 방법도 각 경우에 따라 달라진다.

(1) LL회전 : A부터 N까지의 경로상의 노드들을 오른쪽으로 회전 시킨다. 
(2) LR회전 : A부터 N까지의 경로상의 노드들을 왼쪽 - 오른쪽으로 회전 시킨다.
(3) RR회전 : A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킨다.
(4) RL회전 : A부터 N까지의 경로상의 노드들을 오른쪽 - 왼쪽으로 회전 시킨다.

한번만 회전하는 것을단순회전(single rotation)이라고 하며 두번 회전이 필요한것을 이중회전(double rotation)
이라고 한다. LL,RR은 단순회전, LR,RL은 이중 회전이며 회전은 탐색 순서를 유지하면서 부모와 자식 원소의
위치를 교환하면 된다.

진짜 중요한건 이진탐색트리이기 때문에 기준노드로부터 왼쪽은 작은수 오른쪽은 큰수가 들어간다는것..정렬이 되어있다는것!!

코드를 작성할때 가장 중요하게 인식해야할 부분이다..

AVL트리에서 균형인수를 구할때 먼저

높이를 구하는데

높이는 왼쪽, 오른족 재귀를 통해서 구하는데 왼쪽 오른쪽 비교해서 더 큰값에 + 1하면 높이가 된다고라...