AVL Tree

<균형 이진검색 트리(Balanced binary search tree)와 불균형 이진검색 트리(Unbalanced binary search tree)>
- 균형 이진검색 트리는 말단 노드가 모두 같은 레벨에 존재하는 형태
  - 이진 트리에 대한 연산이 가장 효율적으로 이루어진다

- 불균형이 가장 심화된 상태(사향트리(skewed tree)의 경우
  - 사향트리의 경우는 데이터값이 크기 순서대로 오름차순 또는 내림차순으로 입력될 때 나타난다

- 검색 트리가 불균형 상태 : 검색 성능의 저하


<AVL Tree>
- 이러한 문제점을 해결한 구조로서 AVL 트리가 있다
  이 이진 검색트리는 모든 노드에서 왼쪽과 오른쪽 부트리의 깊이의 차이가 1이하인 상태를 유지하도록 
  데이터의 삽입/삭제 시에 균형을 이루도록 노드를 재배치하는 구조를 가지고있다

- AVL트리는 이진 검색트리로서 트리의 균형을 유지한다

- 균형트리의 조건
  - 트리의 균형을 유지하기 용이
  - 트리의 깊이가 O(log2n)을 보장
  *완전이진트리의 높이 k=[log2(n+1)] (n은 노드의 개수(데이터의 개수))
  *O(log2n) : 시간복잡도

- 가장 간단한 균형트리의 조건으로서는 모든 노드의 왼쪽과 오른쪽 부속트리가 동일한 높이를 갖도록 하는 것이다

- 그러나 이러한 조건을 만족하기 위해서는 2^k -1(높이 k인 포화이진트리의 노드 개수)개의 노드를 가지는
  트리만이 가능하므로 현실적으로 유연하지 못한 구조

- AVL트리는 이진 검색트리와 동일한 구조를 가지며 단 한가지의 '균형'을 유지하기 위한 조건을 가진다
  - 모든 노드에서 왼쪽 부속트리와 오른쪽 부속트리의 높이의 차가 최대 1까지만 가능하다는 조건이다
  *'균형' : 어느정도의 오차를 허용한다 라는 의미
  *노드 높이 : 자식노드 중 높이+1

- 노드가 하나도 없는 비어있는 트리의 높이를 -1로 정의한다

- AVL 트리를 구성하는 모든 노드에는 해당 노드의 높이 정보가 노드구조로서 저장된다

- AVL 트리의 높이는 아래의 식에  의해 계산될 수 있다(n은 트리를 구성하는 노드의 개수를 나타낸다)
  h=1.44*log2(n+2)-0.328

- 그러나 실제 상황에서의 AVL 트리의 높이는 아래와 같다. 즉, 실험적으로 얻어진 것이다
  h=log2(n+1) + 0.25
  시간복잡도에 의한 표현 O(log2n) -> upper bond(데이터가 무한히 증가해도 O(log2n)의 범위 내에 존재한다 -> 상한선)

- AVL 트리의 높이가 h일 때 트리를 구성하는 최소 숫자의 노드는 다음과 같이 구해진다
  N(h) = N(h-1) + N(h-2) + 1
  즉, 높이 h인 AVL은 좌우높이차가 1이 되는게 최소 노드갯수의 트리이고, 루트노드 1개를 포함한다

- h가 0일 때, N(h)=1, h가 1일 때 N(h)=2가 된다
- 따라서 AVL 트리에 대한 연산은 O(log2n)의 시간으로 수행될 수 있다
- AVL 트리의 특성을 유지하기 위해 만일 균형이 깨진다면 노드를 재구성하는 회전변형(rotation)을 통해
  균형을 유지해야 한다


- 회전변경 알고리즘은 새로이 삽입된 노드의 위치에서 시작하여 루트 노드까지 거슬러 올라가면서 삽입 경로 상에 있는 모든 노드의 균형정보를 업데이트한다
- 만일 경로상에 모든 노드의 균형정보가 AVL 트리의 특성을 벗어나지 않는다면 알고리즘은 종료된다
- 그러나 AVL 트리의 특성을 위반하는 노드가 발견되면 해당노드에 대해 회전 변경을 수행하고 균형정보를 업데이트한다

- 만일 AVL트리에서 데이터 값 k를 삽입할 때 부속트리의 높이 정보가 변함 없으면 연산은 종료된다
  만일 불균형 상태가 발생하면 단일/이중 회전 변형을 수행하고 높이 정보를 수정한다

- 재귀 함수는 논리적인 간결한 표현이 가능한 장점이 있다 
  트리구조에서 재귀함수는 상당히 효율적인 구조가 된다

- 재귀함수를 사용하면 경로 상의 이동정보를 따로 유지관리하지 않아도 재귀함수의 회귀과정에서 자연스럽게 경로의 추적이 이루어진다

- 모든 재귀함수는 반복구조로도 구현이 가능하다
  그러나 트리구조의 경우, 재귀함수를 사용하지 않고 반복구조를 사용하면 정확히 코드를 구현하는 것이 상당히 어려워진다



<삭제 연산(deletion)>
- AVL 트리의 삭제 연산은 이진검색트리의 삭제연산과 동일하게 이루어진다
- 삭제 후 경로를 따라 균형 상태를 확인하여 불균형 상태를 이루는 노드를 회전(rotation)변형을 통해 수정한다
  AVL트리 삭제연산의 경우 연쇄적인 불균형 상태를 유발시킬 수 있다