AVL Tree에 대해
페이지 정보
작성일 23-01-26 03:07본문
Download : AVL Tree에 대해.docx
각각의 노드마다 왼쪽 서브트리의 높이를 오른쪽 서브트리의 높이로 뺀 값인 균형치(balance factor)를 가지고 있으며, ±1 이하여야한다.AVL Tree에 대해
RR ( RightRight rotation ) : 왼쪽회전- N이 A의 왼쪽 서브트리의 왼쪽 서브트리로 삽입되는 경우
노드의 삽입과 삭제 시노드들을 회전해서 재배열 한다.
순서
설명
AVL트리는 Adelson-Velskii와 E.M. Landis가 논문을 발표했기 때문에 이름을 따서 AVL트리란 이름이 된 것이다.
AVL Tree,Adelson-Velskii
Download : AVL Tree에 대해.docx( 59 )
■ 로테이션의 종류 4 가지
회전방법에는 LL, LR, RR, RL의 네 가지 방법이 있으며 LL과 RR은 한번만 회전이 필요한 단순회전이고 LR과 RL은 두 번의 회전이 필요한 이중회전이다.
회전 방식은 새로 삽입된 노드 N으로부터 가장 가까우면서 균형치가 맞는 노드 A일 때 기준
■ 동작 구조
레포트 > 공학,기술계열
다.
각각의 노드마다 왼쪽 서브트리의 높이를 오른쪽 서브트리의 높이로 뺀 값인 균형치(balance factor)를 가지고 있으며, ±1 이하여야한다. Height Balanced Tree(높이 균형 트리)라고도 합니다. Height Balanced Tree(높이 균형 트리)라고도 합니다.
AVL트리는 Adelson-Velskii와 E.M. Landis가 논문을 발표했기 때문에 이름을 따서 AVL트리란 이름이 된 것이다.