AVL 트리: Difference between revisions
From IT Wiki
No edit summary |
(→동작 예시) |
||
| (10 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 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]] | |||
== 같이 보기 == | == 같이 보기 == | ||
{{틀:데이터베이스 인덱스 트리}} | {{틀:데이터베이스 인덱스 트리}} | ||
Latest revision as of 10:46, 3 June 2023
- Adelson-Velskii and Landis Tree
- 트리내 각각의 노드마다 1 이하의 균형치(Balance Factor, +1,0,1)를 가지기 위해, 삽입과 삭제를 할때마다 균형치를 검사하여 RR, LL, LR, RL 회전연산을 시행하는 이진탐색트리
- 발표자인 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 이름을 따서 명명
특징[edit | edit source]
- 한 노드를 중심으로 좌우 종속 트리의 높이 차가 1 이하인 균형 잡힌 트리
- 이진 트리의 삽입·삭제 과정에서 한 방향으로 치우치거나, 높이 차이로 인해서 수행 시간이 증가되는 것을 막기 위해 균형 유지
- B 트리 등과 함께 균형잡힌 트리(height-balanced tree)라고도 불림
회전 동작[edit | edit source]
개요[edit | edit source]
- LL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽으로 회전
- LR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전
- RL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전
- RR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽으로 회전
동작 예시[edit | edit source]
- RR 회전
- LR 회전
- RL 회전
- LL 회전
