[AVL 트리] 이론

오늘 공부해볼 내용은 AVL 트리이다.

 

AVL 트리는 "균형잡힌" 이진 탐색 트리라고 할 수 있다.

트리에서 "균형잡혔다" 라는 의미는 오른쪽과 왼쪽의 서브 트리의 높이 차이가 1이하 인 경우이다.

 

따라서 새로운 노드를 삽입하거나, 노드를 삭제할 때 높이가 달라지는 부분에서 트리를 rotate 해야 한다.

 

아래는 그림으로 그려본 AVL트리의 예시이다.

지금 8에서 문제가 발생한다. 오른쪽은 깊이가 2인데 왼쪽은 0이다. 차이가 1을 초과하므로 회전 시켜줘야한다.

왼쪽으로 회전 시켜줘서 균형잡힌 트리를 만들 수 있다.

 

이번에도 8에서 문제가 발생한다. 왼쪽이 깊이가 2인데 오른쪽이 0이다. 차이가 1을 초과한다.

오른쪽으로 회전시켜 균형을 맞춰준다.

 

이번에는 조금 더 복잡한 경우이다. 회전을 여러번 해줘야한다.

먼저는 4에서 문제가 생긴다. 9 때문에 생기는 문제이다. 따라서 왼쪽 오른쪽 회전을 시켜야한다.

그렇지만 아직도 문제가 해결되지 않았다. 따라서 다시 왼쪽 회전을 시켜준다.

이렇게 해서 균형잡힌 트리를 만들 수 있다.

 

간단하게 AVL 트리를 설명해 보았다. 이후에는 코드로 개념을 설명해볼 것이다.