둘러보기 메뉴
검색
바뀐글
임의글
개인 도구
가입하기
로그인
도움말
도움말
질문게시판
자주 묻는 질문
커뮤니티
실시간 채팅방
가입인사게시판
자유게시판
뉴스게시판
제재안게시판
최근 토론
페미위키
공지사항
개선 요청
바뀐글
임의글
파일 올리기
다면 분류 목록
특수 문서 목록
AVL 트리 문서 원본 보기
이름공간
문서
토론
주시
도구
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
위키베이스 항목
행위
보기
읽기
원본 보기
역사 보기
←
AVL 트리
문서 편집 권한이 없습니다. 다음 이유를 확인해주세요.
요청한 명령은 다음 중 하나의 권한을 가진 사용자에게 제한됩니다:
사용자
,
Seeders
.
문서를 고치려면 이메일 인증 절차가 필요합니다.
사용자 환경 설정
에서 이메일 주소를 입력하고 이메일 주소 인증을 해주시기 바랍니다.
문서의 원본을 보거나 복사할 수 있습니다.
'''AVL 트리'''는 [[자가 균형 이진 탐색 트리]]의 하나이다. 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 [[이진 탐색 트리]]를 말한다. AVL 트리는 트리가 비균형 상태가 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. == 균형 인수 == [[파일:AVL-tree-wBalance K.svg|섬네일|균형 인수가 표시된 AVL 트리의 예.]] 한 노드의 균형 인수(balance factor)는 한쪽 서브 트리의 높이 - 반대편 서브 트리의 높이로 정의된다. 모든 노드의 균형 인수가 ±1 이하면 AVL 트리이다. == 재균형 == AVL 트리는 삽입이나 삭제 연산으로 인해 균형 상태가 깨질 수 있는데, 삽입 연산의 경우 새로운 노드의 삽입 후에 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다. 불균형 상태로 변한(균형 인수가 ±2가 된) 가장 가까운 조상 노드의 서브 트리들에 대하여 균형을 잡는 일을 재균형(rebalance)이라 한다. === 회전 === 삽입 연산에서의 재균형은 노드가 삽입된 위치에 따라 노드를 회전(rotation)시키는 것으로 새로운 노드의 삽입에는 다음의 경우가 있다. 새로 삽입된 노드 N으로부터 가장 가까우면서 균형 인수가 ±2가 된 조상 노드를 A라고 하자. ; LL 타입 : N이 A의 왼쪽 서브 트리의 왼쪽 서브트리에 삽입된다. ; RR 타입 : N이 A의 오른쪽 서브 트리의 오른쪽 서브트리에 삽입된다. ; RL 타입 : N이 A의 오른쪽 서브 트리의 왼쪽 서브트리에 삽입된다. ; LR 타입 : N이 A의 왼쪽 서브 트리의 오른쪽 서브트리에 삽입된다. LL과 RR, RL과 LR은 각각 대칭이다. 재균형시키는 방법은 다음과 같다. ; LL 타입 : A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킨다. ; RR 타입 : A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킨다. ; RL 타입 : A부터 N까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전시킨다. ; LR 타입 : A부터 N까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전시킨다. 한 번만 회전시키는 것을 단순 회전(single rotation)이라고 하며 LL 회전, RR 회전이 여기에 속한다. 두 번의 회전이 필요한 것을 이중 회전(double rotation)이라고 하며 LR 회전, RL 회전이 여기에 속한다. === LL 회전과 RR 회전 === [[파일:AVL Rotação Simples à Direita.PNG|섬네일]] {{빈 문단}} === RL 회전과 LR 회전 === {{빈 문단}} == [[시간복잡도]] == AVL 트리는 [[균형 트리]]임이 항상 보장되기 때문에 탐색이 <math>O(log _2 n)</math> 시간 안에 끝나고 삽입과 삭제 연산도 <math>O(log _2 n)</math> 시간 안에 할 수 있다. == 역사 == * Adelson-Velskii와 Landis에 의해 1962년에 제안되었다. [[분류:종류/자가 균형 이진 탐색 트리]]
이 문서에서 사용한 틀:
틀:빈 문단
(
원본 보기
)
틀:알림 상자
(
원본 보기
)
틀:알림 상자/styles.css
(
원본 보기
)
AVL 트리
문서로 돌아갑니다.
다른 언어