[ Algorithm ] AVL tree란?

AVL tree란?

           - Binary SearchTree의 경우, 한쪽으로 노드가 쏠릴 수 있다. 트리에서 특정 값을 찾으려면 O(N)의 시간이 필요하다.

              하지만, biasedTree를 AVL tree로 구성하면, 어떤 노드를 탐색하든 O(logN)에 탐색하는 것이 가능하다.

 

                - Binary Search Tree의 속성을 가집니다.

                - 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다.

                - 높이 차이가 1보다 커지면 Rotation을 활용하여, 균형을 맞춰, 높이 차이를 최소화합니다.

                - 삽입, 검색, 삭제의 시간 복잡도가 O(logN) 이다. (N : 노드의 개수)

Balance Factor(BF)

          - AVL트리는 균형이 무너졌는지에 대해 판단할 때, Balance Factor라는 것을 활용합니다.

             AVL트리는 모든 노드의 BF가 -1. 0. 1 중 하나여야 합니다. 만약 이를 벗어나 균형이 깨진 경우, 회전(Rotation)이 필요합니다.

 

회전의 종류  (LL, LR, RR, RL)

         LL(Left Left) Case

                 - Balance Factor(BF)를 벗어난 노드를 기준으로, LL(Left Left) node가 존재한다면,
                    해당 노드를 기준으로 우회전을 적용하면 불균형이 해소됩니다.

         LR(Left Right) Case

                 - Balance Factor(BF)를 벗어난 노드를 기준으로, LR(Left Right) node가 존재한다면,
                      해당 노드의 Left note를 기준으로 좌회전을 진행합니다.
                    이후 Balance Factor(BF)를 벗어난 노드를 기준으로 우회전을 진행하면, 불균형이 해소됩니다.

 

         RR(Right Right) Case

                 - Balance Factor(BF)를 벗어난 노드를 기준으로 RR(Right Right) node가 존재한다면,

                    해당 노드를 기준으로 좌회전을 적용하면, 불균형이 해소됩니다.

         RL(Right Left) Case

                 - Balance Factor(BF)를 벗어난 노드를 기준으로 RL(Right Left) node가 존재한다면,

                    해당 노드의 Right node를 기준으로 우회전을 진행합니다.

                    이후, Balance Factor(BF)를 벗어난 노드를 좌회전을 진행하면, 불균형이 해소됩니다.

 

* 이해가 잘 안되신다면, 하단의 링크를 활용해보시기 바랍니다.

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

AVL Tree Visualzation