[균형트리] 트리의 종류

목차

균형탐색트리
AVL 트리
AVL 트리에 새로운 노드 삽입
2-3트리
...

본문내용

균형탐색트리
좋은 성능을 유지하려면 트리가 한쪽 방향으로 기울어지지 않도록 해야 한다.

말단 노드에서 루트까지의 높이가 모두 같거나 오직 1만큼만 차이가 난다면
최악의 경우
: 비교 횟수가 log2(n)을 넘지 않는다.


AVL 트리
트리의 높이
단말노드로부터 루트 노드까지의 노드 수 중에 가장 긴 것을 가리킨다.
왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 크지 않으면 된다.
AVL트리는 노드가 삽입/삭제될ㅤ때마다 트리가 균형을 이루도록 조정해주어야 한다.
균형치(balance factor)를 부여한다.
( 균형치는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다. )


<균형치가 부여된 AVL트리>


AVL 트리에 새로운 노드 삽입
해당 노드를 삽입하고 균형치를 조정해준다.

균형치가 -1에서 1사이의 값을 가지면 끝낸다.

균형치가 -1보다 작아지거나 1보다 커지면 균형이 깨진 것이다.
(형재 삽입된 노드로부터 가장 가까운 노드에서부터 하위 노드들을 위치를 변형하여 균형을 이루도록 해준다)
2-3트리

참고 자료

없음