[자료구조] 이진 트리, 이진 탐색 트리(BST)
이전글에서 설명했듯이 트리는 계층 구조를 표현할 수 있는 자료구조이다.
이러한 트리에는 여러가지 종류가 있는데 이진 트리(Binary Tree), 이진 탐색 트리(BST), AVL Tree, Red Black Tree등이 있다.
이진 트리(Binary Tree)
우선, 이진 트리는 위에 첨부한 이미지와 같이 각 노드의 자녀 노드 수가 최대 2개인 트리를 의미한다.
이진 트리안에서 형태에 따라 분류가 나뉘어지고 한다.
예를 들어, 모든 노드에 자녀 노드가 없거나 두개인 트리를 정 이진 트리라고 부른다.
또한, 완진 이진 트리(complete binary tree)라는 것도 존재한다. 완전 이진 트리란, 마지막 레벨을 제외한 모든 레벨에서 노드가 빠짐없이 채워져 있고, 마지막 레벨은 왼쪽부터 빠짐없이 노드가 채워져있는 트리를 의미한다.
모든 레벨에 대해 노드가 꽉 차있는 이진 트리는 포화 이진 트리라고 하며, 위에 첨부한 이미지는 완전 이진 트리이자 포화 이진 트리라고 할 수 있다. 예를 들어, 8번 노드가 없다면 왼쪽부터 꽉 채워져있는 형태가 아니기 때문에 포화 이진 트리가 아니게 되는 것이다.
이진 탐색 트리(binary search tree)
이진 탐색 트리란 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고, 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가지는 트리를 의미한다.
그렇기에 이진 탐색 트리의 최소값은 트리의 가장 왼쪽에 존재할 것이며, 반면에 이진 탐색 트리의 최대값은 트리의 가장 오른쪽에 위치할 것이다.
이진 탐색 트리의 성능
이진 탐색 트리는 보통 재귀적으로 왼쪽 서브 트리부터 순회하며, 노드를 방문하고, 재귀적으로 오른쪽 서브트리를 순회하는 방식을 사용한다. 그렇기에 이진 탐색 트리의 성능은 해당 트리의 높이에 따라 좌지우지된다고 할 수 있다.
예를 들어, 오름 차순 혹은 내림 차순으로 정렬된 데이터를 이용해 이진 탐색 트리를 만든다고 해보자.
오름 차순으로 정렬된 데이터를 이진 탐색 트리에 삽입하는 경우, 새로운 값은 항상 현재 트리의 가장 큰 값보다 크기 때문에 항상 오른쪽에 삽입될 것이다. 이로인해 트리는 한 쪽으로만 자라나게 되고, 트리의 높이는 전체 노드의 갯수와 같아지게 된다.
이런식으로 편향된 트리는 탐색, 삽인, 삭제 연산에서 모두 O(n)의 성능을 가지게 될 것이다.
물론, 편향되지 않고 균형잡힌 이진 탐색 트리라면 logN의 높이를 가지기 때문에 훨씬 좋은 성능을 지닐 것이며, 그렇기 때문에 이진 탐색 트리에서는 균형이 중요하다.
여기서 균형이란, 왼쪽 노드의 높이와 오른쪽 노드의 높이 차가 크지 않은 상태, 트리의 양쪽에 노드들이 균형있게 분표되어 있는 경우를 의미한다.