AVL 트리

이진트리는 한쪽으로 치우친 형태로 트리 구조가 만들어 질수 있는데
그렇게 되면 트리 구조가 아닌 일반적인 연결 리스트와 별 차이가 없게 되기 때문에
이진 트리의 장점이 사라지게 된다.

AVL 트리는 이러한 전체 트리의 구조가 균형이 맞도록 하는 트리다.
즉, 쏠린 트리처럼 트리 구조가 한쪽으로 쏠리는 것을 막아 트리 구조의 균형을 맞춤으로써
조회 성능을 O(logN)으로 유지할수 있는것이다.

AVL 트리는 다음과 같은 특징이 있다.

1. 균형도(Balance Factor)라는 개념이 있는데, 이는 각 노드의 왼쪽 노드와 오른쪽 노드의 차이를 말한다.
2. 리프 노드의 균형도는 0이다.
3. 균형도는 '왼쪽 자식 트리의 높이 - 오른쪽 자식 트리의 높이'로 계산한다.

왼쪽 자식 노드와 오른쪽 자식 노드의 균형도는 -1, 0, 1의 세 가지 값만 갖는다.
AVL 트리는 새로운 노드가 삽입되거나, 기존의 노드가 삭제될때 균형을 맞추기 위해서 RR, LL, LR, RL 회전을 통해서 트리의 균형을 맞춘다.
(R은 오른쪽, L은 왼쪽을 의미한다.)

하지만 새로운 노드가 삽입되거나 기존의 노드가 삭제될때마다 회전이 일어난다면 오히려 성능을 떨어트릴수도 있는데,
AVL 트리의 장점은 유지하면서 성능을 떨어트리지 않는 2-3 트리 구조에 대해 알아보자

2-3 트리