LR회전

[자료구조] AVL 트리 - 회전 연산을 통해 균형을 유지하다

AVL 트리 AVL 트리는 트리가 한쪽으로 치우치는 것을 방지하여 트리 높이의 균형을 유지한다는 특징이 있다. 즉, 삽입이나 삭제 시에 균형이 어긋나게 되면 스스로 회전 연산을 통해 균형을 유지하는, 자체 힐링이 가능한 트리이다. 이러한 AVL 트리(a.k.a 균형 트리)를 사용하는 이유는 탐색, 삽입, 삭제 연산 시에 균일한 수행 시간 O(logN)을 보장하기 때문인데, 이는 AVL 트리의 높이와 관계가 있다. n개의 노드를 가진 AVL 트리의 높이는 O(logN)이다. AVL 트리의 정확한 정의를 알아보자. AVL 트리는 임의의 노드 x에 대해 x의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1을 넘지 않는 이진 탐색 트리이다. AVL 트리의 회전 연산 회전 연산의 경우 AVL트리는 회전 ..