- 비선형구조로서, 정점(Vertex)과 선분(Arc)으로 이루어진 그래프의 특수한 경우이다.
- 트리는 어떠한 두 정점 사이에도 사이클(Cycle)이 존재하지 않는 연결그래프로써 임의의 두 노드 사이의 경로는 오직 하나만 존재한다.
- 트리의 알고리즘은 순환적(Recursive)이며, 트리 T에서 임의의 한 Edge를 제거하면 트리 T는 더 이상 연결되지 못한다.
특징
- 트리의 루트를 제거하면 Forest(사이클은 없지만 연결되지 않은 무방향 그래프)가 된다.
- 루트가 아닌 노드의 부모 노드는 유일하게 결정된다. 즉, 트리에서 루트를 제외한 나머지 모든 노드들은 선행자가 하나만 존재한다.
- 트리 구조에서 간선 수 e와 노드 수 n의 관계는 항상 e = n+1이다.
- 이진트리에서는 서브트리를 왼쪽 자식과 오른쪽 자식의 순서로 구분한다.
이진트리
- 트리의 모든 노드들이 2개 이하의 자식 노드를 갖는 트리이다. 즉, 이진트리의 모든 노드는 자식이 전혀 없는 단말 노드이거나, 자식이 하나만 있거나 혹은, 자식이 2개가 있다.
- 일반트리는 한 개 이상의 노드를 갖는 유한 집합이지만, 이진트리는 노드가 0개일 수 있다.
- n개의 노드를 갖는 이진트리라면 항상 n+1개의 null링크가 존재한다.
- 깊이가 k인 2진 트리가 가질 수 있는 노드 수는 k ~ -1 이다.
특징
- 이진트리의 각 노드는 왼쪽과 오른쪽 서브트리를 갖는 위치가 중요한 의미를 가진 순서트리(Ordered Tree)의 일종이다.
- 이진트리를 배열 A[1...n]에 저장하면 I번째 노드의 부모노드 위치는 이고 왼쪽 자식노드의 위치는 2*i번째, 오른쪽 자식노드의 위치는 2*i+1이다.
- 이진트리를 연결구조로 표현하면 각 노드에 대하여 자식노드의 위치는 쉽게 알 수 있지만 부모노드의 위치는 찾기 어렵다.
- 트리의 차수가 증가할수록 널 링크 점유율이 증가하므로 기억 공간이 낭비된다. 따라서 기억 공간 낭비를 최소화하고 삽입 삭제가 용이한 이진트리를 구성하는 것이 효율적이다.
종류
