이진탐색트리

이진탐색트리는 자기를 기준으로 작은 값은 왼쪽 자식 노드로 큰 값은 오른쪽 자식 노드로 보내는 트리를 말합니다.

이진탐색트리의 단점

이진탐색트리의 탐색 시간은 O(logN)이지만, **최악의 경우에는 (노드가 한쪽으로 편향되어 있을 경우) O(N)**입니다. 이러한 탐색 트리의 단점을 보안하기 위해서는 편향성을 보정해야 합니다. 이를 방법론적으로 만든 것이 바로 자가균형이진탐색트리입니다.

AVL tree

AVL tree는 위에서 말한 것처럼 이진탐색트리의 편향성을 해결하기 위해 고안된 방법입니다. 노드가 새로 들어올 때마다 재귀적으로 리프부터 루트까지 하나씩 balance factor를 검사합니다. 만약 이 때 BF의 절댓값이 1을 넘는다면 해당 노드를 기준으로 그 서브트리를 회전시킵니다. 이런 방식으로 리프부터 루트까지 검사하며 필요한 경우 로테이트를 해 균형을 맞춰주는 것이 AVL tree입니다.

Node

각 노드는 다음과 같은 구조체로 만들어져있습니다. height는 노드의 평향성을 확인하기 위한 수치입니다. 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이를 뺀 값을 확인해 그 값이 -1 보다 작거나 +1 보다 크다면 균형을 맞추기 위해 트리를 조정해야 합니다. 이 때 각 서브트리의 높이를 확인하기 위한 수치인 height를 각 서브트리의 루트에 놓는 것입니다.

typedef sturct s_node
{
	int data;
	int heght; // 내 부모 노드가 내가 속한 서브트리의 깊이를 측정했을 때의 최대 값.
	struct t_node *left;
	struct t_node *right;
}    t_node;

height

height는 위에서 말했듯이, BF(balance factor)를 확인하기 위한 자료입니다. 노드 9를 기준으로 왼쪽 서브트리의 높이는 2, 오른쪽 서브트리의 길이는 1입니다. 그리고 각 수치를 각 서브트리의 루트에 저장합니다. 그렇기 때문에 노드 7에는 2, 노드 10에는 1이 저장되어야 합니다. 이를 통해 알 수 있는 것은 각 노드는 최초 생성시 무조건 height 값이 1로 초기화되며, 자신의 오른쪽 서브트리외 왼쪽 서브트리 중 가장 height가 큰 것이 자신의 height값이 됩니다.