AVL Tree1 AVL 트리 이진 탐색 트리는 트리 구조마다 연산시간이 천차만별입니다. 다음 그림처럼 같은 노드를 가져도 구조에 따라서 연산시간이 다르게 됩니다. 같은 3개의 노드, 같은 요소인데도 8이라는 요소를 탐색 할 때 왼쪽 편향 트리는 노드를 2번 거치는 연산을 하고, 오른쪽 그림의 이진 트리는 오른쪽으로 한 번 이동하는 연산만을 수행하면 됩니다. 이처럼 노드가 늘어날수록 그 차이가 커집니다. 이처럼 노드가 늘어나서 불균형해질수록 이진 트리의 연산횟수가 증가하는 단점이 있는데, 이 단점을 보완한 트리를 균형 이진 탐색 트리 혹은 균형 트리라고 합니다. 이 균형 트리에는 B 트리, AVL 트리 2-3-4 트리 등이 있는데 오늘은 이 중에서 AVL 트리에 대해서 알아보려고 합니다. 1. AVL 트리 Adelson-Velskii.. 2021. 10. 1. 이전 1 다음 300x250
