AVL 트리 편집하기
IT위키
편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
[[분류:데이터베이스 | [[분류:데이터베이스]] | ||
;Adelson-Velskii and Landis Tree | ;Adelson-Velskii and Landis Tree | ||
;트리내 각각의 노드마다 1 이하의 균형치(Balance | ;트리내 각각의 노드마다 1 이하의 균형치(Balance Facotr, +1,0,1)를 가지기 위해, 삽입과 삭제를 할때마다 균형치를 검사하여 RR, LL, LR, RL 회전연산을 시행하는 이진탐색트리 | ||
* 발표자인 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 이름을 따서 명명 | * 발표자인 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 이름을 따서 명명 | ||
10번째 줄: | 10번째 줄: | ||
== 회전 동작 == | == 회전 동작 == | ||
[[파일:AVL Rotation.gif]] | [[파일:AVL Rotation.gif]] | ||
* LL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽으로 회전 | * LL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽으로 회전 | ||
16번째 줄: | 15번째 줄: | ||
* RL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전 | * RL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전 | ||
* RR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽으로 회전 | * RR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽으로 회전 | ||
== 같이 보기 == | == 같이 보기 == | ||
{{틀:데이터베이스 인덱스 트리}} | {{틀:데이터베이스 인덱스 트리}} |