AVL 트리

AVL Tree

이진 탐색 트리의 경우, 운이 나빠 편향트리가 형성이 되면 O(n)의 시간복잡도를 가지게 됩니다.

그렇기에 좌우 높이차가 1이 넘지 않는 트리를 만드는데, 이것이 AVL 트리입니다.

주의할 점

삽입, 삭제가 이루어지는 경우, AVL 트리의 균형속성이 파괴될 수 있습니다. 이런 경우, 불균형을 찾아서 해소해주어야 합니다. 

때문에 두가지 필요한 매서드가 있습니다.

1. 균형검사 (balance check)

2. 개조 (restructure)

회전
    : 회전 요령은 자동차 핸들을 생각하시면 됩니다.

L - 반시계 방향으로 회전

R - 시계 방향으로 회전

단일회전

이중회전

모든 회전 후

** 개인적 견해 : LL, RR, LR, RL 이렇게 정의를 하는데, 개인적으로는 그냥 이해하고 하는 것이 더 쉽다.

이 용어 이해하려고 하다보니 더 헷갈렸음

성능

균형을 이루게 되기 때문에 항상 O(log n)의 탐색 시간을 갖습니다.

균형의 과정

- 3 노드 개조 : O(1) 시간 수행

- 삽입 or 삭제 : O(log n), 3 노드 개조는 O(1)이지만 올라가면서 반복 수행해야 하기 때문