- 이진탐색 트리의 문제점과
해결방안
- 이진탐색 트리는
삭제 연산을 수행함에
따라 왼쪽이 길어진다.
- 노드가 N인 이진
탐색 트리에서 M번 연산의
수행시간은 M*logN
- 해결방안 : AVL(Adelson-Velskii
and Landis)트리, Splay트리
- AVL 트리 : 모든
노드가 균형조건을 지키도록
제한한다.
- 균현 조건 : 각 노드의
좌우 종속 트리의 높이의
차가 1 이하
- 회전 : 균형 조건에
위반한 노드는 회전으로
밑으로 내려감
- 회전의 종류 : Single
right(left) rotation,
double right(left) rotation
- AVL 트리의 개념
|
|
