경고: 로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다. 로그인하거나 계정을 생성하면 편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.
편집을 취소할 수 있습니다.
이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 |
당신의 편집 |
1번째 줄: |
1번째 줄: |
| [[분류:데이터베이스]][[분류:자료 구조]] | | {[[분류:데이터베이스]] |
| ;Adelson-Velskii and Landis Tree | | ;Adelson-Velskii and Landis Tree |
| ;트리내 각각의 노드마다 1 이하의 균형치(Balance Factor, +1,0,1)를 가지기 위해, 삽입과 삭제를 할때마다 균형치를 검사하여 RR, LL, LR, RL 회전연산을 시행하는 이진탐색트리
| |
| * 발표자인 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 이름을 따서 명명
| |
|
| |
| == 특징 ==
| |
| * 한 노드를 중심으로 좌우 종속 트리의 높이 차가 1 이하인 균형 잡힌 트리 | | * 한 노드를 중심으로 좌우 종속 트리의 높이 차가 1 이하인 균형 잡힌 트리 |
| * 이진 트리의 삽입·삭제 과정에서 한 방향으로 치우치거나, 높이 차이로 인해서 수행 시간이 증가되는 것을 막기 위해 균형 유지 | | * 이진 트리의 삽입·삭제를 계속할 때 어느 한 방향으로 치우치거나, 높이 차이로 인해서 수행 시간이 증가되는 것을 막기 위해 균형을 유지 |
| * B 트리 등과 함께 균형잡힌 트리(height-balanced tree)라고도 불림 | | * B 트리 등과 함께 균형잡힌 트리(height-balanced tree)라고도 불림 |
|
| |
| == 회전 동작 ==
| |
| === 개요 ===
| |
| [[파일:AVL Rotation.gif]]
| |
| * LL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽으로 회전
| |
| * LR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전
| |
| * RL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전
| |
| * RR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽으로 회전
| |
|
| |
| === 동작 예시 ===
| |
| * RR 회전
| |
| [[파일:AVL LL Rotation.png|600px]]
| |
| * LR 회전
| |
| [[파일:AVL LR Rotation.png|600px]]
| |
| * RL 회전
| |
| [[파일:AVL RL Rotation.png|600px]]
| |
| * LL 회전
| |
| [[파일:AVL RR Rotation.png|600px]]
| |
|
| |
|
| == 같이 보기 == | | == 같이 보기 == |
| {{틀:데이터베이스 인덱스 트리}} | | {{틀:데이터베이스 인덱스 트리}} |