컴공 일기232

게시글 주소: https://dev.orbi.kr/00062255284

저번에 올렸었던 AVL 트리의 기본 이론 입니다.

일반 이진 트리의 경우 1-9를 삽입한다면 오른쪽으로 확 쏠려버리는 구조가 나옵니다. 이런 경우, 이진 탐색이 선형 탐색과 별반 다를 바가 없는 기이한 현상이 일어나고, 이진 탐색 트리의 장점이라 볼 수 있는 '탐색 속도'가 무의미하게 되지요. 따라서, Node가 삽입 혹은 삭제되는 과정에서 트리의 균형을 잡아주는 알고리즘이 필요한데, 그것이 AVL트리의 경우 RR,LL,RL,LR 회전입니다. 말하자면, 전체 구조 속에서 균형이 무너지기 시작할 때, 회전을 해서 다시 균형을 잡아주는 것이지요.

일반 이진 탐색 트리의 경우, 9를 탐색한다면 9번 연산을 진행해야 하지만, 균형이 잡힌 AVL 트리에서는, 4번의 연산만으로 탐색할 수 있지요. Node 수가 적을 땐 9번이든 4번이든 큰 차이가 없다고 할 수 있겠지만, 데이터가 증가하면 증가할수록, 이 차이는 그에 비례해서 커집니다.

선형 탐색의 경우 시간복잡도는 O(N)이고, 균형 이진 트리의 경우 시간복잡도는 O(logN)입니다.