트리란?
노드로 이루어진 계층적인 자료구조로 사이클이 없는 그래프의 일종
트리에는 하나의 루트 노드가 있으며, 루트 노드는 자식 노드를 가지게 되고 그 자식 노드들은 그들의 자식 노드를 가지는 구조의 자료구조이다.
트리에 관한 용어들
루트 노드(root node): 부모 노드가 없는 중심이 되는 노드로 트리에 단 한 개만 존재한다.
ex) 위 트리에서 루트 노드는 1번 노드이다.
서브 트리(subtree): 루트 노드를 제외한 나머지 노드
ex) 2, 3, ..., 9, 10번 노드들이 서브 트리이다.
리프 노드(leaf node): 자식 노드를 가지고 있지 않은 트리의 말단에 있는 노드
ex) 위 트리에서 리프 노드는 7, 8, 9, 10번 노드이다.
부모 노드(parent node): 어떤 노드와 간선으로 연결되어 있고 위에 있는 노드
ex) 2번 노드는 5번 노드의 부모 노드이다.
자식 노드(children node): 어떤 노드와 간선으로 연결되어 있고 그 아래에 있는 노드
ex) 2번 노드의 자식 노드는 5번 노드이다.
형제 노드(sibling): 같은 부모 노드를 가지는 노드
ex) 8, 9번 노드는 5번 노드를 부모로 하는 형제 노드이다.
노드의 크기(size): 자신을 포함한 모든 자식 노드들의 개수
노드의 차수(degree): 어떤 노드가 가지고 있는 자식 노드의 개수
ex) 4번 노드의 차수는 1이다.
노드의 깊이(depth): 루트 노드에서 어떤 노드까지 도달하기 위해 거치는 정점의 개수
ex) 6번 노드의 깊이는 3이다.
트리의 레벨(level): 트리의 각 층에 번호를 매긴 것이다. 루트의 레벨은 1이다.
ex) 6번 노드의 레벨은 3이다.
트리의 높이(height): 가장 깊이가 깊은 노드의 깊이
ex) 트리의 높이는 4이다.
트리의 특징
트리는 1개의 루트 노드를 가지고 루트 노드를 제외한 모든 노드들은 1개의 부모 노드를 가진다.
트리는 사이클이 없는 그래프이기 때문에 노드의 개수가 $N$개인 트리의 간선은 항상 $N-1$개이다.
또한 임의의 두 노드를 연결하는 경로는 반드시 1개 뿐이다.
이진 트리
모든 노드의 차수가 2 이하인, 즉 모든 노드가 자식 노드를 최대 2개 가지고 있는 트리
포화 이진트리: 각 레벨에 노드가 꽉 차있는 이진트리로, 높이가 $k$인 이진트리는 $2^{k}-1$개의 노드를 가진다.
완전 이진트리: 높이가 $k$인 트리에서 레벨 1부터 $k-1$까지는 노드가 꽉 차있고, 레벨 $k$에서는 왼쪽에서 오른쪽으로 노드가 순서대로 채워져 있는 트리
트리의 표현
완전 이진트리를 배열로 나타낼 수 있다. 트리의 각 노드를 순서대로 배열에 저장하는 방법이다. 루트 노드를 1번 노드라고 하고 그 자식 노드를 2, 3번 노드라고 하면 배열의 1번째에 1번 노드에 대한 정보, 2번째에 2번 노드에 대한 정보를 저장하는 방법으로 배열에 나타낼 수 있다. 그러면 $i$번 노드의 자식 노드는 $2i$, $2i+1$번 노드가 된다.