AVL 트리

이진 탐색 트리의 한 종류로 스스로 균형을 잡는 트리이다. 이때 balance factor를 통해 균형을 유지하는게 핵심이다. 그럼 balance factor에 대해서 조금 더 자세히 알아보자. 노드의 balance factor란 임의의 노드 x에 대해서 그 노드의 왼쪽 서브트리의 높이와 그 노드의 오른쪽 서브트리의 높이의 차이를 구했을때, 그 높이 차이를 그 노드의 balance factor라고 한다. 여기서 AVL 트리의 특징은 트리의 모든 노드들의 balance factor가 -1, 0 ,1 값을 가진다는 특징이 있다. 또한 AVL 트리는 트리에 삽입 혹은 삭제후에 balance factor가 -1, 0, 1이 아닌 노드가 생기면 균형을 맞추는 작업을 수행한다. 즉, AVL 트리에서 삽입/삭제를 위해서는 기본적으로 이진 탐색 트리이기 때문에 루트 노드에서 적절한 위치까지 찾아가서 처리를 해주는데, 이때 AVL 트리의 특징이 깨지지 않았는지 확인을 해줘야하기 때문에 삽입 혹은 삭제가 발생한 위치에서 루트 노드로 거꾸로 올라오면서 Balance Factor를 확인하여 균형이 깨졌다면 재조정을 해줘야 한다.

AVL 트리에 값을 insert하고, delete 하는 과정은 다음과 같다.

 

 

 

 

AVL 트리는 결국 이진 탐색 트리이기 때문에 시간 복잡도 측면에서 삽입, 삭제, 검색 모두 best case에서는 O(1)이고, average case에서는 O(logN)이다. 하지만, worst case에서 이진 탐색 트리와 비교해서 O(logN)이라는 강점을 가지고 있다. 하지만 단점도 있는데, 엄격하게 균형을 유지하기 때문에 삽입 혹은 삭제시 트리의 균형을 확인하고, 만약 균형이 깨졌다면 트리 구조를 재조정하기 때문에 이때 시간이 꽤 소요된다. 그래서 이 문제를 해결하는 것이 red-black tree이다.