다양한 분야에서 널리 쓰이고 있는 자료구조 Tree의 가장 단순한 형태인 Binary Tree에 대해 알아보자.
이진 트리(Binary Tree)는 모든 노드가 2개 이하의 자식 노드를 가지고 있는 자료구조이다.
이진 트리는 데이터 저장 및 검색, 네트워크 라우팅 및 게임 AI를 포함하여 다양한 곳에서 쓰이는 자료구조이다. 또한 검색, 정렬, 그래프 알고리즘과 같은 다양한 알고리즘을 구현하는 데에도 많이 사용된다.
검색과 저장, 삭제의 시간복잡도는 구조에 따라 다르지만 보통 O(logN) 을 기대할 수 있으며, 최악의 경우 O(N) 의 비용이 소요된다.
Binary Tree의 구조
이진 트리는 데이터를 보다 효율적으로 사용할 수 있도록 검색하고 저장하데 특화된 자료구조이다. Parent와 Child로 구성되며 Edge로 연결된다. 또한, Root 부터 Leaf까지 모든 노드가 서로 연결되어 있다.
- 부모(Parent): 노드의 선행 노드를 해당 노드의 부모노드라고 한다. {B} 는 {D, E} 의 부모노드이다.
- 자식(Child): 노드의 바로 후속 노드를 해당 노드의 자식노드라고 한다. {D, E}는 {B} 의 자식노드이다.
- 루트(Root): 트리의 최상위 노드 또는 부모노드가 없는 노드를 루트노드라고 한다. {A} 는 트리의 루트노드이다.
- 잎새(Leaf): 자식노드가 없는 노드를 잎새노드라고 한다. {K, L, M, N, O, P}는 트리의 잎새노드이다.
- 형제(Sibling): 동일한 상위 노드의 하위 노드를 형제노드라고 한다. {D,E} 는 형제노드이다.
- 엣지(Edge): 노드와 노드 사이를 연결하는 선을 엣지라고 한다. 노드와의 관계를 표현한다.
- 레벨(Level): 루트노드에서 해당 노드까지의 경로에 있는 간선의 수이다. 루트노드의 레벨은 0 이다.
- 내부(Internal): 잎새노드를 제외한 모든 노드를 내부노드라고 한다. {K, L, M, N, O, P}를 제외한 모든 노드는 내부노드이다.
- 서브트리(Subtree): 트리에서 일부 자식노드와 부모노드를 묶은 그룹을 서브트리라고 한다. {B}와 {D,E}는 위 트리의 서브트리이다.
트리의 속성 중 가장 중요한 것이 루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다는 것이다. 이 속성 때문에 트리는 다음과 같은 특징을 보인다.
- 서로 다른 두 노드 사이의 경로는 한 개만 존재한다.
- 노드간의 순환은 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 엣지를 하나 자르면 두 개의 트리로 분리된다.
- 엣지의 수(𝐸) = 노드의 수(𝑉) - 1
Binary Tree의 유형
이진 트리는 노드를 어떻게 배치하는지에 따라 연산의 시간복잡도가 달라진다. 아래는 노드의 배치에 따라 구분한 이진 트리의 대표적인 유형들이다.
정이진트리(Full Binary Tree)
완벽한 이진 트리(Perfect Binary Tree)라고도 하는 정이진트리는 마지막 레벨의 노드를 제외한 모든 레벨의 노드들이 꽉 채워진 이진트리이다. 즉, 아래와 같이 모든 잎새노드가 자식이 없으며, 잎새노드를 제외한 모든 노드가 2개의 자식노드를 가지고 있는 이진트리를 의미한다.
위 구조를 보면 알 수 있듯이 정이진트리의 레벨별 노드 갯수는 2^(level) 개 인것을 확인할 수 있다. 즉, 총 노드 갯수는 2^(level-1) 개가 된다.
완전이진트리(Complete Binary Tree)
완전이진트리는 마지막 레벨을 제외한 모든 레벨의 노드가 가득 차 있으며, 마지막 레벨의 노드가 왼쪽으로 기울어져 있는 트리를 말한다. 즉, 정이진트리에서 오른쪽 잎새노드가 비어 있으면 완전이진트리이다.
완전이진트리에서 중요한 점은 모든 자식노드가 왼쪽부터 채워져 있다는 것이다. 그로인해서 Linked List가 아닌 Array로도 표현이 가능하다.
이진트리를 배열로 표현하는 것은 연산을 하는데 있어서 엄청난 이점이 있다. 배열의 인덱스로 노드의 위치를 변경할 수 있기 때문인데, 대표적으로 완전이진트리의 일종으로 우선순위 큐를 위해 만들어진 Heap 자료구조가 있다.
균형이진트리(Balanced Binary Tree)
균형이진트리는 모든 노드에서 좌우 서브트리의 높이 차이가 1이하인 트리를 말한다. 아래 트리를 예로 들어보자.
오른쪽과 왼쪽 서브트리의 높이 차이를 BF(Balance Factor) 라고 하는데, 트리에 삽입/삭제 연산으로 균형이 깨졌을때 노드를 재배치하여 BF를 1이하로 유지한다.
그 이유는 수학적으로 BF가 1 이하일 때 검색, 삽입, 삭제 연산이 O(logN) 의 비용으로 처리 가능하기 때문이다. 이러한 장점으로 데이터베이스 인덱스 테이블의 대부분은 균형이진트리의 일종인 B-Tree 또는 B+ Tree로 구현되어 있다.
기울어진 이진트리(Skewed Binary Tree)
기울어진 이진트리는 모든 자식노드가 한 쪽으로로 기울어진 이진트리이다. 따라서 왼쪽으로 기울어진 이진트리와 오른쪽으로 기울어진 이진트리 두 가지가 존재한다.
이 구조는 이진트리가 가질 수 있는 최악의 구조이다.
Reference
