자료구조 avl tree

소개글

자료구조 avl tree에 대한 보고서 자료입니다.

본문내용

AVL Tree
AVL트리는 Adelson-Velskii와 E.M. Landis가 논문을 발표했기 때문에 이름을 따서 AVL트리란 이름이 된 것이다.
각각의 노드마다 왼쪽 서브트리의 높이를 오른쪽 서브트리의 높이로 뺀 값인 균형치(balance factor)를 가지고 있으며, ±1 이하여야 한다. Height Balanced Tree(높이 균형 트리)라고도 합니다.
삽입과 삭제를 할 때 트리의 높이가 달라지게 되는데 만약 어떠한 노드라도 균형치가 ±2일 경우 RR, LL, RL, LR의 네 가지 방식을 이용해 회전을 시킵니다.
■ 동작 구조
노드의 삽입과 삭제 시 노드들을 회전해서 재배열 한다.
회전방법에는 LL, LR, RR, RL의 네 가지 방법이 있으며 LL과 RR은 한번만 회전이 필요한 단순회전이고 LR과 RL은 두 번의 회전이 필요한 이중회전이다.
■ 로테이션의 종류 4 가지
회전 방식은 새로 삽입된 노드 N으로부터 가장 가까우면서 균형치가 맞는 노드 A일 때 기준

키워드

자료구조 avl tree,   AVL Tree,   로테이션