[컴][알고리즘] AVL Tree

알고리즘 / 자료구조 / 트리 /

avl tree

balanced bst(binary search tree) 이다. 그 중에서도 self-balancing bst 이다.
인데 그래서 height 를 일정하게 유지하는것이 주요 목적이다.

height 의 정의가 명확해야 한다. 가장 긴 노드의 깊이가 height 이다.
그런데 이 차일드가 가진 height 중 높은 녀석에서 한개의 깊이가 더해지면 그게 자신의 height 가 된다.
근데 avl 은 여기서 height 를 유지하기 위해 조건이 하나 붙는다.

balanced 를 유지하기 위해 왼쪽 차일드와 오른쪽 차일드의 차이가 1 을 초과하면 안된다.
근데 이렇게 balanced 를 강하게 유지하기 때문에 insertion, deletion, 등을 할 때 좀 더 많은 rotation이 일어나야 한다.

그래서 삽입 제거등이 빈번하게 일어날 때는 red black tree 가 유리하다. 좀 덜 타이트하게 밸런스를 유지하기 때문이다.
대신에 retrieval 에 좋다. 그래서 한 번 만들고 잘 추가하지 않는 경우에 좋다. 그러니까 cpu 에서 opcode 를 찾을 때 좋다.

이런 bst트리들이 이용되는 이유는 worst case가 좋아서 그렇다. 가장 안좋은 상황에서도 일정한 속도를 내줘야 하는 경우 그래서 real time app 같은 경우에 쓰인다.
어찌보면 time critical 한 곳인듯 하다.

이때 height 를 유지하는 방법이 rotate이다.
rotate는 일단 insert를 하고나서 그 부분의 height 가 커져서 avl 에서 벗어난다면 그 부분을 rotate 시켜서 height 를 낮춘다.

이 부분이 제일 쉽게 설명한다.
http://en.m.wikipedia.org/wiki/File:AVL_Tree_Rebalancing.svg

http://en.m.wikipedia.org/wiki/File:Tree_Rotations.gif

핵심은 길게 만들고 그것을 이제 Rotate 하는 것이다. 길게 만들때도 rotate 를 이용한다.

이 rotate 는 길게 만든 녀석중 중간 부분이 위로 가고 가장 윗부분이 왼쪽또는 오른쪽으로 간다.
이것을 꺾인다 라고 얘기한다면,
꺾일때 가운데 녀석의 차일드를 가져간다. 물론 자신과 가까운 쪽의 녀석을
그리고 제일위로 가는 노드가 이제 자기 자식으로 꺾인 녀석을 연결하면 된다.
그림을 보면 바로 이해된다.