[Data Structure] AVL 트리

[2d3k]

1. AVL 트리에 대해 설명하시오.

2. rotation의 종류를 설명하시오.

[2d3k]

1 AVL 트리는 자가 균형 이진 탐색 트리(Self-balancing binary search tree)의 일종으로, 노드들이 트리 내에서 높이가 균형을 유지하도록 하는 자료 구조입니다. AVL 트리는 높이 균형 인자(balance factor)를 이용하여 트리의 균형을 확인하고, 불균형이 발생하면 회전 연산(rotation operation)을 이용하여 균형을 맞춥니다.

AVL 트리의 노드는 일반적으로 두 개의 자식 노드를 가지며, 자식 노드들은 부모 노드보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 위치합니다. AVL 트리는 이진 탐색 트리의 모든 기능을 제공하면서도, 삽입, 삭제, 검색 등의 연산에 대해 평균적으로 O(log n)의 시간 복잡도를 보장합니다.

[2d3k]

2 AVL 트리에서 노드의 높이 균형 인자(balance factor)가 -2 또는 2를 초과하면 해당 노드는 균형을 잃은 상태로, 회전 연산(rotation operation)을 통해 균형을 맞추어야 합니다.

AVL 트리에서는 두 가지 종류의 회전 연산이 있습니다.

왼쪽 회전(Left Rotation): 오른쪽 자식 노드의 왼쪽 서브트리를 부모 노드의 오른쪽 자식 노드로 옮기고, 부모 노드를 오른쪽 자식 노드의 왼쪽 자식 노드로 옮깁니다. 오른쪽 회전(Right Rotation): 왼쪽 자식 노드의 오른쪽 서브트리를 부모 노드의 왼쪽 자식 노드로 옮기고, 부모 노드를 왼쪽 자식 노드의 오른쪽 자식 노드로 옮깁니다.