본문 바로가기

AVL트리

[C] AVL트리
coding/Data Structure(C) 2020. 12. 13. [C] AVL트리 AVL트리에 대해 알아보자. 이전 포스트에서, BST 순회와 연산의 시간복잡도를 줄이기 위해 균형잡힌 이진트리를 만든다고 했었다. 그 중 한 방법이 AVL트리이다. AVL트리는 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1이하이다. 그리고 노드가 삽입되는 과정에서 스스로 노드들을 재배치해서 균형 상태를 유지한다. 균형 인수 = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이 'AVL트리이다'는 말은 모든 노드의 균형 인수가 다음을 충족시킬 때를 일컫는다. -1 RR회전) 그림으로 보자. 노드 1을 삽입했다. 3보다 작기 때문에 3의 왼쪽자식으로 배정. 하지만 노드 5와 7의 균형인수가 2를 넘어버렸다! 이럴때는 노드 1과 가장 가까우면서 균형이 깨진 조상노드를 찾아야 하는데, 노드 5이다. 노..

티스토리툴바