AVL 트리 이진탐색트리는 큰 문제점이 있으니, 위 그림과 같이 한쪽으로 노드가 쏠릴 수가 있다. 10,9,8,7,6을 순서대로 삽입한다고 생각해보면 저런 형태의 트리가 만들어진다는 것을 알 수 있을 것이다. 위와 같은 형태의 트리에서 특정 값을 찾으려면 O(n)의 시간이 필요할 것이다.
예를 들어 6을 찾으려면 모든 노드를 탐색해야지 찾을 수 있다. 따라서 성능이 매우 나빠지게 된다.
이런 단점을 극복할 수 있는 자료구조가 AVL트리이다. 예를 들어 [그림 1]의 편향트리를 [그림 2]처럼 AVL 트리로 재구성하면 어떤 노드를 탐색하든 O(log N)에 탐색할 수 있다.
AVL트리는 다음과 같은 특징을 가진다. 1. 이진 탐색 트리의 속성을 가진다. 2.
왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다. 3. 높이 차이가 1보다 커지면 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다. 4.
삽입, 검색, 삭제의 시간 복잡도가 O(logn)이다. (N : 노드의 개...
원문 링크 : AVL 트리
