#016_자료구조와 알고리즘_ 균형잡힌 이진 탐색 트리?

안녕하세요 삽잡이 입니다.

이진 탐색 트리는 검색을 보다 용이하게 하기 위해 만들어진 트리입니다.

그런데 만약, 이진 탐색 트리가 한쪽으로 계속 쏠리게 되면 어떠한 현상이 벌어질까요?

자... 이와 같이 한쪽으로 쏠려있는 트리의 경우 검색 성능이 현저하게 떨어집니다.

균형잡힌 트리에 비해 높이가 더 높아서 

심하면 검색 속도가 선형 자료구조의 검색 속도와 차이가 없어 질 수 도 있습니다.

즉, 균형이 잡혀야 이진 탐색 트리는 속도가 나온다는 것이지요...

따라서 이번 시간에는 균형잡힌 트리를 만들기 위해서 어떻게 해야할지에 대해서

이미 기울어진 트리를 균형잡는 방법과, 애초에 균형 잡히게 트리를 만드는 방법을 알아보겠습니다.

자, 우선 기울어진 트리를 어떻게 하면 균형을 잡을 수 있을까요?

배열을 하나 준비해두고 기울어진 트리를 중위 오더로 기록하는 것입니다. 

그 다음, 기존에 기울어진 트리를 제거하는 것이지요.

마지막으로, 기록한 배열의 노드들을 매달면 됩니다.

말은 참 쉽습니다... 

그런데 이게 의도적이게 편향적으로 매달 수 있는 것도 아니고, 

자료들을 매달다 보면 어떻게 되다 보니 한쪽으로 쏠리는 경우가 많습니다.

따라서, Balance를 잡는 시점을 정해두는 것이 좋습니다.

예를 들어 100개 를 달때마다 Balancing 작업을 해주던지, 50개를 달 때마다 하던지 말입니다.

벨런싱 작업을 하게 되면 당연히 속도가 개선 될 것입니다.

하지만, 밸런스를 유지시키는 비용이 들게 되겠죠...

다음으로, 애초에 균형되게 자료를 보관하는 방법에 대해서 생각해보겠습니다.

균형 잡힌 상태를 유지하는 트리의 종류는 굉장히 다양합니다.

그 중에서 저는 AVL에 대해서 언급하려고 합니다.

위키 백과의 힘을 빌리자면,

AVL Tree는 가장 초기에 나온 '균형 잡힌 이진 탐색 트리'라고 합니다.

AVL의 핵심은 다른 '균형 잡힌 이진 탐색 트리'들의 핵심과도 마찬가지이겠지만 Rotation입니다.

각각 매달려 있는 노드마다 왼쪽과 오른쪽 자식 트리의 높이차에 대해 정보를 가지고 있으며,

높이 차이가 절대값 1 보다 크지 않도록 유지하는 것이지요.

다시 말씀드리자면, 왼쪽 서브 트리 높이에서 오른쪽 서브 트리의 높이를 뺀 값이 

절대값으로 1보다 작거나 같아야 된다는 것입니다.

차이가 1을 초과하게 되면 로테이션 하게 되는 성질을 가진 '균형 잡힌 트리'입니다.

김빠지게도 위키 백과에는

'레드-블랙 트리만큼 효율이 좋지 않아 자주 쓰이지는 않는다.'라고 나와있군요... 허허...

아무튼... 그냥 감만 잡으면 되니깐 말입니다...

이와 같은 트리가 있다고 해봅시다. 맨 상위 노드를 Root 노드라고 해보겠습니다.

Root 노드에는 오른쪽에만 자식 노드가 있습니다.

따라서 왼쪽 자식 노드 - 오른쪽 자식 노드 를 한 값인 Balanced 값은 1이 됩니다.

여기까지는 문제가 없지만, Root 노드의 손자뻘인... Root의 자식 노드 또한 오른쪽 자식만을 가지고 있습니다.

이렇게 되면 왼쪽 높이 차가 총 2가 됨으로 수정이 필요하게 됩니다.

자... 이렇게 rotation을 통해서 balance 작업을 할 수 있는 것이죠.

노드가 보관되면 부모 노드에 영향이 갑니다.

무너진 지점이 어디인지 살펴보는 것이 가장 중요합니다.

무너진 지점만 살펴본 뒤에 균형있게 변화를 시켜주면 됩니다. 

'균형 잡힌 노드'들은 blance 값을 참고해서 트리 구조를 변경하는 것이기 때문에

blance 값을 기재해가며 정렬해야됩니다.

이상 지금까지 삽잡이였습니다!