AVL 트리의 노드 삽입 방법과 C 코드

목차

없음

본문내용

*AVL 트리에서의 노드 삽입 방법을 상세히, 알기 쉽게 설명하시오.
AVL트리는 항상 균형을 유지하는 이진트리이다. 모든 노드의 서브트리 높이 차이가 1이하이고, 만약 높이 차이가 2이상이 된다면 노드들은 재배치하여 균형 상태를 유지해야한다.

AVL트리의 균형은 삽입, 삭제할 때 깨질수 있다. 삽입연산시에는 삽입되는 위치에서 루트까지의 경로에 있는 조상 노드들의 균형인수에 영향을 줄 수 있다. 새로운 노드를 삽입 후 이때 균형인수가 ±2이상이 되는 노드가 생기면 균형인수가 2가 된 가장 가까운 조상 노드부터 하위 노드까지 회전을 시켜 균형을 맞춘다.
(균형인수란 왼쪽서브트리의 높이 - 오른쪽 서브트리의 높이로 정의된다.)
즉, 균형인수가 ±1인 이진트리면 AVL트리이다.

참고 자료

없음