트리
트리는 재귀로 정의된 자기 참조 자료구조이다. 쉽게 말하면, 트리는 자식도 트리고 또 그 자식도 트리다. 즉 여러 개의 트리가 쌓아 올려져 큰 트리가 된다. 흔히 서브트리로 구성된다고 표현한다.
트리의 각 명칭
트리는 항상 루트에서부터 시작된다. 루트는 자식 노드를 가지며, 간선으로 연결되어 있다. 자식 노드의 개수는 차수라고 하며, 크기는 자신을 포함한 모든 자식 노드의 개수다. 높이는 현재 위치에서부터 리프까지의 거리, 깊이는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브 트리 구성을 띈다. 레벨은 0에서부터 시작한다. 트리는 항상 단방향이기 때문에 간선의 화살표는 생략 가능하다. 일반적으로 간선의 방향은 위에서 아래로 향한다.
그래프 vs 트리
트리는 순환 구조를 갖지 않는 그래프다. 핵심은 순환 구조가 아니라는 데 있다. 트리는 특수한 형태의 그래프의 일종이며, 크게 그래프의 범주에 포함된다. 하지만 트리는 그래프와 달리 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없다. 이외에도 단방향, 양방향을 모두 가리킬 수 있는 그래프와 달리, 트리는 부모 노드에서 자식 노드를 가리키는 단방향뿐이다. 그뿐만 아니라 트리는 하나의 부모 노드를 갖는다는 차이점이 있으며 루트 또한 하나여야 한다.
이진트리
트리 중에서도 가장 널리 사용되는 트리 자료구조는 이진 트리와 이진 탐색 트리(Binary Serrch Tree, BST)다. 먼저, 각 노드가 m개 이하의 자식을 갖고 있으면, m-ary 트리(다항 트리, 다진 트리)라고 한다. 여기서 m = 2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별히 이진 트리라고 구분해서 부른다. 이진 트리는 왼쪽, 오른쪽, 최대 2개의 자식을 갖는 매우 단순한 형태로, 다진 트리에 비해 훨씬 간결할 뿐만 아니라 여러 가지 알고리즘을 구현하는 일도 좀더 간단하게 처리할 수 있어서, 대체로 트리라고 하면 특별한 경우가 아니고서는 대부분 이진 트리를 일컫는다.
이젠 이진트리 유형을 살펴보자. 나중에 여러 문제에서 다양한 트리의 유형을 접하게 될 텐데 명칭을 정확하게 숙지하지 않으면, 문제를 풀이하면서 다룰 여러 명칭들 때문에 혼란을 겪을 수 있다.
- 정 이진 트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
- 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
- 포화 이진 트리(Perfect Binary Tree) : 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다. 문자 그대로, 가장 완벽한 유형의 트리다.
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]