트리
사이클이 없는 그래프
정점의 개수 V
간선의 개수 V-1
루트 있는 트리
부모(Parent)
그래프가 있으면 루트에 가까운 것이 부모
루트는 부모가 없다.
자식(Children)
부모 아래에 달려있는 노드
가장 아래층에 있는 노드 => 단말 정점 (Terminal Node) (Leaf Node)
형제(Sibiling)
같은 부모를 가지면 형제
깊이(Depth)
루트에서 부터의 거리 (루트의 깊이를 0으로 하나 1로 하나의 차이가 있다)
높이(Height)
깊이 중에서 가장 큰 값
조상, 자손(Ancestor, Descendent)
p->q로 갈 수 있을 때(형제 위치로는 갈 수 없음)
p가 q보다 루트에 가까우면
p는 q의 조상
q는 p의 자손
이진 트리(Binary Tree)
자식을 최대 2개만 가지고 있는 트리
트리의 표현
1. 그래프와 같은 방식으로 저장할 수 있다.
2. 트리의 모든 노드는 루트를 제외하고 모두 부모를 가지므로 부모만 저장하는 방식
2.의 장점 => 부모를 찾는데 O(1)만큼 걸린다.
2의 단점 => 자식을 찾는데 O(V)만큼 걸린다.
3. 이진트리의 경우 배열로 표현할 수 있다.
부모를 x로 자식을 2x, 2x+1로 설정해서 배열로 저장
3의 단점 => 한쪽으로만 연결된 트리를 예로 들 경우 8개를 저장하기 위해 256개의 저장공간이 필요함
이진 트리가 꽉 차는 방식으로 차도록 해결할 수 있는 문제는 이런 방식으로 사용하면 아주 좋음