균형탐색트리1 [자료구조] AVL Tree(AVL 트리) - CS면접 대비 이번 글에서는 AVL 트리에 관한 내용을 정리해보고자 한다. 이전 글에서 언급했던 것처럼 BST는 공백인 상태에서 이미 정렬된 수를 연속으로 삽입하는 경우 편향(skewed) 문제가 발생한다. 따라서 최악의 경우 자료 탐색에 소요되는 시간이 리스트를 순차 탐색하는 것과 같아진다. 균형 탐색 트리의 일종인 AVL 트리는 이러한 BST의 편향 문제를 해결하기 위해 고안되었으며, 동적 검색을 O(log N) 시간 내에 할 수 있고, 새로운 키를 O(log N) 시간 내에 삽입하거나 삭제할 수 있다. AVL 트리(AVL Tree) [1] AVL 트리의 정의 어떤 이진트리 노드 T의 balance factor(균형인수)를 $BF(t) = h_L - h_R$ 라 할 때, 모든 노드 T에 대해 $BF(t)$= -1,.. 2021. 12. 7. 이전 1 다음 반응형
