@ 16. 1 ~ 17. 1/자료구조
AVL 이진트리(개념설명)
namoeye
2014. 2. 18. 21:53
이진 탐색트리가 자동으로 균형을 잡을 수 있도록 개선된것이
AVL 트리
균형인수 = 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이
균형인수의 절댓값이 2이상인 경우에 균형을 잡기위해 트리의 재조정을 진행한다.
LL회전
자식 노드 두개가 왼쪽으로 연이어 연결되어 부모의 균형인수가 2가 되는 것
3
2
1
이런경우를 말하고..LL회전을 거치면
2
1 3
이렇게 된다. 2를 중심으로 오른쪽으로 3이 돌면됨..
RR은 그와 반대로..
3
2
1
RR회전을 거치면
2
3 1
이런식으로 된다.
LR과 RL도 있는데 우선 LR의 경우
1
2
3
이런식을 말하고..
우선 LR상태에서 한번의 회전으로 균형이 잡히는 LL이나 RR로 바꾼다
LR상태에서 RR회전을 하면 LL상태가 된다.
2, 3을 먼저 떼어서 RR회전을 하면
2
3
으로 되고 그걸 다시 붙이면
1
2
3
이렇게 된다. 이것은..? 맞다 LL이다
그럼 RL은? 반대이다 부분 LL 하면 RR이 된다
개념설명은 이정도로..