[C++/알고리즘] 자가 균형 이진 탐색 트리(AVL 트리)

자가 균형 이진 탐색 트리(AVL트리)란?

자가 균형 이진 탐색 트리는 삽입과 삭제가 일어나는 경우에 자동으로 그 높이(루트에서부터 내려갈 수 있는 최대 레벨)를 작게 유지하는 노드 기반 이진 탐색 트리입니다. 이진 탐색 트리의 문제점은 삽입과 삭제를 할 때마다 트리의 높이가 증가하면서 탐색 시간이 길어지는 문제가 있습니다. 이를 해결하기 위해 균형 이진 탐색 트리를 사용합니다.

AVL 트리는 레드-블랙 트리를 제외하고 가장 많이 사용되는 균형 이진 탐색 트리 중 하나입니다. 레드-블랙 트리에 비해 회전 연산이 더 많이 필요하지만, 검색 시간은 레드-블랙 트리보다 더욱 빠릅니다.

회전(Rotation)

AVL 트리에서 삽입, 삭제 연산을 하여 트리 높이가 불균형 상태가 된다면 노드들을 재배치하여 높이 균형 상태로 만들어야 합니다. 이때 재배치하는 작업을 회전(Rotation)이라고 합니다.
AVL 트리에서의 회전 연산은 LL, RR, LR, RL 4가지가 있습니다. 각각의 경우에 대해 회전 연산을 수행하여 균형을 맞춥니다.

시뮬레이션 사이트
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

균형 이진 탐색 트리의 장단점

장점

• AVL 트리는 모든 연산에 대해 O(log n)의 시간 복잡도를 보장합니다. 레드-블랙 트리와 마찬가지로 검색, 삽입, 삭제 연산 등에서 빠른 속도를 보입니다.
• AVL 트리는 높이 균형을 유지하므로 트리의 균형이 매우 중요한 경우에 적합합니다. 예를 들어, 데이터베이스 인덱싱에 사용됩니다.

단점

• AVL 트리는 레드-블랙 트리보다 회전 연산이 더 많이 필요합니다. 따라서 삽입, 삭제 연산이 레드-블랙 트리보다 더 느릴 수 있습니다.
• AVL 트리의 높이 균형을 유지하기 위해 추가적인 메모리 공간이 필요합니다. 각 노드마다 균형 인수를 저장해야 하기 때문입니다.

AVL 트리는 높이 균형을 유지해야 하는 중요한 데이터 구조에 적합합니다. 그러나 삽입, 삭제 연산이 레드-블랙 트리보다 느리다는 단점이 있으므로, 레드-블랙 트리와 같은 다른 균형 이진 탐색 트리를 사용해야 하는 경우도 있습니다.

시간 복잡도

1. 접근 - O(log n)

• AVL 트리는 이진 탐색 트리의 일종으로, 모든 노드에 대해 왼쪽 서브트리는 해당 노드보다 작은 값을, 오른쪽 서브트리는 해당 노드보다 큰 값을 가지므로, 이진 탐색을 통해 원하는 값을 찾을 수 있습니다.
• 이진 탐색 트리의 높이가 log n 이하이므로, AVL 트리의 접근 시간 복잡도는 O(log n)입니다.

2. 검색 - O(log n)

• AVL 트리는 이진 탐색 트리의 일종으로, 모든 노드에 대해 왼쪽 서브트리는 해당 노드보다 작은 값을, 오른쪽 서브트리는 해당 노드보다 큰 값을 가지므로, 이진 탐색을 통해 원하는 값을 찾을 수 있습니다.
• 이진 탐색 트리의 높이가 log n 이하이므로, AVL 트리의 검색 시간 복잡도는 O(log n)입니다.

3. 삽입 및 삭제 - O(log n)

• AVL 트리에서 삽입 연산을 수행할 때, 모든 노드에 대한 균형인수가 ±1 내에 값이면 균형이 유지된 것이므로 삽입 과정을 마칩니다. 하지만 한 노드의 균형 인수만이라도 그 범위를 벗어나면 균형을 맞춰주기 위한 회전(Rotation) 작업을 해주어야 합니다.
• 회전 연산은 O(1)의 시간 복잡도를 가지므로, 삽입 연산의 시간 복잡도는 O(log n)입니다.
• AVL 트리에서 삭제 연산을 수행할 때, 삭제한 노드의 부모 노드부터 루트 노드까지 올라가면서 균형을 맞춰주어야 합니다. 이때 회전 연산은 O(1)의 시간 복잡도를 가지므로, 삭제 연산의 시간 복잡도는 O(log n)입니다.
• 삭제 연산에서 균형을 맞추기 위해 회전 연산을 수행해야 하는 경우는 최대 O(log n)번이므로, 삭제 연산의 시간 복잡도는 O(log n)입니다.