이진 탐색 트리의 한종류

스스로 균형을 잡는 트리

각 노드는 Balance Factor를 가진다.

BF = left subtree height - right subtree height

정상적인 AVL Tree 라면 모든 노드의 BF는 -1, 0, 1 이다.

그 이외의 값을 가진다면 편향된 트리라서 이를 고쳐야한다.

즉 이진 탐색트리가 편향되는 단점을 고치려고 고안된 트리이다.

편향되는 예제

• 왼쪽, 왼족
• 오른쪽, 오른쪽
• 왼쪽, 오른쪽
• 오른쪽, 왼쪽

이렇게 이진 탐색 트리의 편향성 문제점을 해결한 AVL Tree의 삽입/삭제/검색 시간 복잡도는 O(logN)이다.

그러나 삽입/삭제 후에 트리의 밸런스가 깨지는지 확인하고 트리 구조를 재조정 하기 때문에

시간이 더 걸린다.