[보고서] 구조 AVL Tree
페이지 정보
작성일 19-09-23 16:06
본문
Download : [레포트]자료구조 AVL Tree.docx
삽입과 삭제를 할 때 트리의 높이가 달라지게 되는데 만약 어떠한 노드라도 균형치가 ±2일 경우 RR, LL, RL, LR의 네 가지 방식을 이용해 회전을 시킵니다.
![[레포트]자료구조%20AVL%20Tree_docx_01.gif](http://www.allreport.co.kr/View/%5B%EB%A0%88%ED%8F%AC%ED%8A%B8%5D%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%20AVL%20Tree_docx_01.gif)
![[레포트]자료구조%20AVL%20Tree_docx_02.gif](http://www.allreport.co.kr/View/%5B%EB%A0%88%ED%8F%AC%ED%8A%B8%5D%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%20AVL%20Tree_docx_02.gif)
![[레포트]자료구조%20AVL%20Tree_docx_03.gif](http://www.allreport.co.kr/View/%5B%EB%A0%88%ED%8F%AC%ED%8A%B8%5D%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%20AVL%20Tree_docx_03.gif)
[보고서] 구조 AVL Tree
[보고서] 구조 AVL Tree
Download : [레포트]자료구조 AVL Tree.docx( 48 )
레포트/기타
AVL Tree
AVL트리는 Adelson-Velskii와 E.M. Landis가 논문을 발표했기 때문에 이름을 따서 AVL트리란 이름이 된 것이다.
각각의 노드마다 왼쪽 서브트리의 높이를 오른쪽 서브트리의 높이로 뺀 값인 균형치(balance factor)를 가지고 있으며, ±1 이하여야 한다. Height Balanced Tree(높이 균형 트리)라고도 합니다. Height Balanced Tree(높이 균형 트리)라고도 합니다.
각각의 노드마다 왼쪽 서브트리의 높이를 오른쪽 서브트리의 높이로 뺀 값인 균형치(balance factor)를 가지고 있으며, ±1 이하여야 한다.
회전 이전 트리 회전 이후
■ 시간 복잡도
AVL 트리의 시간복잡도
average(평균)
최악의 경우
공간
검색
삽입
삭제
■ 동작 구조
노드의 삽입과 삭제 시 노드들을 회전해서 재배열 한다.
삽입과 삭제를 할 때 트리의 높이가 달라지게 되는데 만약 어떠한 노드라도 균형치가 ±2일 경우 RR, LL, RL, LR의 네 가지 방식을 이용해 회전을 시킵니다.
회전방법에는 LL, LR, RR, RL의 네 가지 방법이 있으며 LL과 RR은 한번만 회전이 필요한 단순회전이고 LR과 RL은 두 번의 회전이 필요한 이중회전이다.
회전 이전 트리 회전 이후
■ 시간 복잡도
AVL 트리의 시간복잡도
average(평균)
최악의 경우
공간
검색
삽입
삭제
■ 동작 구조
노드의 삽입과 삭제 시 노드들을 회전해서 재배열 한다.
회전방법에는 LL, LR, RR, RL의 네 가지 방법이 있으며 LL과 RR은 한번만 회전이 필요한 단순회전이고 LR과 ...
AVL Tree
AVL트리는 Adelson-Velskii와 E.M. Landis가 논문을 발표했기 때문에 이름을 따서 AVL트리란 이름이 된 것이다.
■ 로테이션의 종류 4 가지
회전 방식은 새로 삽입된 노드 N으로부터 가장 가까우면서 균형치가 맞는 노드 A일 때 기준
RR ( Right Right rotation ) : 왼쪽회전
- N이 A의 왼쪽 서브트리의 왼쪽 서브트리로 삽입되는 경우
LL ( Left Left rotation ) : 오른쪽 회전
- N이 A의 오른쪽 서브트리의 오른쪽 서브트리로 삽입되는 경우
RL ( Right Left rotation ) : 오른쪽 회전 후 왼쪽 회전
- N이 A의 왼쪽 서브트리의 오른쪽 서브트리로 삽입되는 경우
LR ( Left Right rotation ) : 왼쪽 회전 후 오른쪽 회전
- N이 A의 오른쪽 서브트리의 왼쪽 서브트리로 삽입되는 경우
※ 그림의 경우 아래 URL에서 Java applet으로 그렸습니다
http://www.site.uottawa.ca/~stan/csi2514/applets…(skip)
레포트,자료구조,AVL,Tree,기타,레포트
[레포트]자료구조 AVL Tree , [레포트]자료구조 AVL Tree기타레포트 , 레포트 자료구조 AVL Tree
설명
순서
다.
