트리(Tree)

- 트리 (Tree)

계층적 관계를 표현하는 비선형 자료 구조, 연결된 비순환 무방향성 그래프

트리 내에 다른 하위 트리가 있고 그 하위 트리안에는 또 다른 하위 트리가 있는 재귀적 자료 구조

 

 

- 기본 용어

 1. 노드 (Node) : 트리를 구성하고 있는 기본 요소, 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음

 2. 간선 (Edge) : 노드와 노드 간의 연결선

 3. 루트 노드 (Root Node) : 트리 구조에서 부모가 없는 최상위 노드

 4. 부모 노드 (Parent Node) : 자식 노드를 가진 노드

 5. 자식 노드 (Child Node) : 부모 노드의 하위 노드

 6. 형제 노드 (Sibling Node) : 같은 부모를 가지는 노드

 7. 외부 노드 (External Node, Outer Node), 단말 노드 (Terminal Node), 리프 노드 (Leaf Node) : 자식 노드가 없는 노드

 8. 내부 노드 (Internal Node, Inner Node), 비 단말 노드 (Non - terminal Node), 가지 노드 (Branch Node) : 자식 노드 하나 이상 가진 노드

 9. 깊이 (Depth) : 루트에서 어떤 노드까지의 간선 수 (루트 노드의 깊이  = 0, D의 깊이 = 2 ) (= Level)

 10. 높이 (Height) : 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수 (리프 노드의 높이  = 0 , A 노드의 높이 = 3)

 

- 특징

 1. 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있다

 2. 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료 구조이다

 3. 트리 내에 또 다른 트리가 있는 재귀적 자료 구조이다

 4. Loop를 갖지 않고, 연결된 무방향 그래프 구조

 5. 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며, 모든 자식 노드는 하나의 부모 노드만 갖는다

 6. 노드가 n개인 트리는 항상 n - 1개의 간선을 가진다