[데이터베이스시스템] 이진트리 이해하기

B+ Tree를 구현하라는 과제가 나왔다. 우리학교 데베시는 상당한 난도를 자랑한다. 자료구조를 2-1때 배웠기 때문에 당장 B Tree도 기억이 나지 않는 상황 ...! 과제를 하지 못하면 가장 코어 과목을 드랍해야하는 상황에 놓이기 때문에 빠르게 트리 구조를 복습해보기로 하였다. B-Tree를 시작하기 전 이진트리 개념부터 공부하고 넘어가자.

 

이진트리 종류는 생각보다 다양하다. 그 종류들을 정리해 보도록 하겠다.

 

1. 이진트리(Binary Tree)

트리 중에서 각 노드가 최대 2개의 자식을 가지는 트리이다. 이 두 자식 노드를 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)이라 부른다. 같은 루트에 같은 자식 노드를 하나 가지고 있더라도 왼쪽과 오른쪽 놓인 위치에 따라 다른 자식 노드에 속한다. 

또한 오른쪽 왼쪽이 명확히 구분되기 때문에 오른쪽 서브 트리, 왼쪽 서브 트리로 다시 나눌 수 있다.

해당 트리는 이진 트리로 볼 수 있다.

노드 1이 3개의 자식 노드를 가지고 있으므로 이진트리가 아니다.

 

2.  완전 이진 트리(Complete Binary Tree)

완전 이진 트리는 마지막 레벨을 제외한 모든 레벨의 노드가 채워져 있으며, 마지막 레벨의 노드는 왼쪽부터 오른쪽으로 차례대로 채워져 있는 트리이다. 효율적인 배열 구현에 적합하며, 주로 힙 구조에서 사용된다.

오른쪽부터 차례대로 채워져있는 모습을 확인할 수 있다.

 

3. 전 이진 트리(Full Binary Tree)

포화 이진 트리는 모든 노드가 0개 또는 2개의 자식을 가지는 트리이다. 즉, 모든 레벨의 노드가 꽉 차 있다. 모든 리프 노드가 같은 깊이를 가지게 되며 트리의 높이가 h일 때 최대 노드의 개수는 2^h+1-1이 된다.

모든 노드가 0개 또는 2개의 자식 노드를 가지고 있어야 한다.

 

4. 포화 이진 트리(Perfect Binary Tree)

완전 포화 이진 트리는 포화 이진 트리의 하위 집합으로 모든 리프 노드가 같은 깊이를 가진다. 즉, 모든 레벨이 완전히 채워져 있는 트리이다.

모든 레벨이 완전이 채워져 있음을 확인할 수 있다.

 

5. 균형 이진 트리(Balanced Binary Tree)

균형 이진 트리는 모든 리프 노드의 깊이가 비슷하게 맞춰진 트리이다. 정확하게 말하자면 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이가 최대 1만큼 차이가 날 수 있는 이진 트리이다. 균형을 이루고 있기 때문에 트리의 높이를 최소화하고 탐색, 삽입, 삭제 등의 작업을 

왼쪽과 가운데 트리는 하위 트리의 높이 차이가 2이기 때문에 균형 이진 트리가 아니고 오른쪽은 하위 트리의 높이 차이가 1이기 때문에 균형 이진 트리이다.

 

6. 이진 탐색 트리(Binary Search Tree, BST)

이진 탐색 트리는 노드의 값이 왼쪽 서브트리의 모든 값보다 크고, 오른쪽 서브트리의 모든 값보다 작은 특성을 가지는 트리이다. 이와 같은 규칙을 유지하기 때문에 효율적인 탐색이 가능하고 빈번한 자료 입력과 삭제가 가능하다. 평균적으로 탐색, 삽입, 삭제 연산이 O(logn)의 시간복잡도를 가진다.

굉장히 균형을 이룬 트리이므로 O(logn)의 시간복잡도를 가진다.

 

하지만 자료가 많아질수록 트리의 높이가 커지기 때문에 검색에 불리해지고 편향되어 있는 최악의 경우 O(n)의 시간 복잡도를 가질 수 있다. 이처럼 이진 탐색 트리가 한 쪽으로 치우쳐져 있는 트리를 편향 이진 탐색 트리(skewed binary search tree)라 한다. 

이와 같은 경우 트리의 높이 값이 n에 가까워지기 때문에 탐색할 시 성능이 매우 떨어진다.

이러한 문제를 해결하기 위해 트리의 입력, 삭제 단계에 트리 전체의 균형을 맞추는 균형 이진 탐색 트리(Balanced Binary Search Tree)이다.

 

7. 균형 이진 탐색 트리(Balanced Binary Search Tree)

이진 탐색 트리의 한 종류로 트리의 높이를 균형있게 유지하여 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행할 수 있도록 설계된 트리이다. 균형을 유지함으로 최악의 경우에도 시간 복잡도를 O(logn)으로 제한한다. 아무리 노드를 추가하거나 삭제해도 높이가 일정 크기 이상이 되지 않도록 제한하는 특성이 있어 성능상 매우 유리하다. 이의 예로 AVL Tree, Red-Black Tree, B Tree, B+ Tree 등이 있다. 

 

왼쪽의 균형을 이루지 않았던 트리가 트리의 높이 균형을 맞추면 오른쪽 트리 형태로 변한다.