AVL 트리: 두 판 사이의 차이

IT위키
(새 문서: 분류:데이터베이스 ;Adelson-Velskii and Landis Tree * 한 노드를 중심으로 좌우 종속 트리의 높이 차가 1 이하인 균형 잡힌 트리 * 이진 트리의...)
 
편집 요약 없음
(사용자 2명의 중간 판 11개는 보이지 않습니다)
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 까지의 경로상의 노드들을 왼쪽으로 회전
=== 동작 예시 ===
* LL 회전
[[파일:AVL LL Rotation.png|600px]]
* LR 회전
[[파일:AVL LR Rotation.png|600px]]
* RL 회전
[[파일:AVL RL Rotation.png|600px]]
* RR 회전
[[파일:AVL RR Rotation.png|600px]]
== 같이 보기 ==
{{틀:데이터베이스 인덱스 트리}}

2019년 12월 28일 (토) 12:55 판

Adelson-Velskii and Landis Tree
트리내 각각의 노드마다 1 이하의 균형치(Balance Factor, +1,0,1)를 가지기 위해, 삽입과 삭제를 할때마다 균형치를 검사하여 RR, LL, LR, RL 회전연산을 시행하는 이진탐색트리
  • 발표자인 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 이름을 따서 명명

특징

  • 한 노드를 중심으로 좌우 종속 트리의 높이 차가 1 이하인 균형 잡힌 트리
  • 이진 트리의 삽입·삭제 과정에서 한 방향으로 치우치거나, 높이 차이로 인해서 수행 시간이 증가되는 것을 막기 위해 균형 유지
  • B 트리 등과 함께 균형잡힌 트리(height-balanced tree)라고도 불림

회전 동작

개요

AVL Rotation.gif

  • LL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽으로 회전
  • LR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전
  • RL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전
  • RR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽으로 회전

동작 예시

  • LL 회전

AVL LL Rotation.png

  • LR 회전

AVL LR Rotation.png

  • RL 회전

AVL RL Rotation.png

  • RR 회전

AVL RR Rotation.png

같이 보기