AVL Tree
AVL트리는 Adelson-Velskii와 E.M. Landis가 논문을 발표했기 때문에 이름을 따서 AVL트리란 이름이 된 것이다.
각각의 노드마다 왼쪽 서브트리의 높이를 오른쪽 서브트리의 높이로 뺀 값인 균형치(balance factor)를 가지고 있으며, ±1 이하여야한다. Height Balanced Tree(높이 균형 트리)라고도 합니다.
삽입과 삭제를 할 때 트리의 높이가 달라지게 되는데 만약 어떠한 노드라도균형치가±2일경우 RR, LL, RL, LR의 네 가지 방식을 이용해 회전을 시킵니다.
회전 이전 트리 회전 이후
.... |
2013.07.19
3페이지
