Tree의 개념
자료구조를 공부하다 보면 후반부에 등장하는 것이 Tree 입니다.
자료구조의 생김새가 마치 나무 같다고 해서 이름 붙여진 것으로 보이는데요.
즉, List 처럼 선형 구조가 아니라 Tree는 비선형 구조로써
- 원소들 간에 계층 관계를 가지는 “계층형 자료구조”
- 상위 원소에서 하위 원소로 내려가면서 확장되는 “나무 모양의 구조”
라고 할 수 있습니다.
Tree와 관련된 용어
트리(binary tree)의 예시. 루트 노드를 기점으로 하위 계층의 것들을 서브 트리라고 통칭하게 된다.
위와 같은 형태를 가지고 있는 Tree 자료구조에 관한 용어들에 대해 살펴보자면,
- 루트(Root) 노드 : 노드 중에서 최상위에 있는 노드
- 루트 노드를 제외한 나머지 노드들도 각각 하나의 Tree가 될 수 있고 그것들을 SubTree라고 부른다.
위 그림에서 살펴볼 수 있는 사항들은 다음과 같습니다.
- 루트 노드(시작 노드) : 1
- 노드(Node) : 1,2,3,4,5
- 간선(Edge) : 1-2, 1-3, 2-4, 2-5
- 형제 노드(Sibling node) : 트리의 같은 레벨선상에 있는 노드들이 서로 형제입니다.
- 즉, 1번 부모에게서 나온 2번, 3번끼리 형제 노드입니다.
- 2번 부모에게서 나온 4, 5번끼리 형제 노드입니다.
- 조상 노드(Ancestor node) : 간선을 따라 루트 노드까지 가는 경로상에 있는 모든 노드들
- 즉, 5번의 조상 노드는 2번, 1번 입니다.
- 서브 트리(SubTree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리.
- 즉, 1번 부모 노드를 기준으로 서브 트리는 2-4,5 와 3번 노드 이렇게 2개 입니다.
- 즉, 큰 트리는 작은 트리들의 모음으로 구성되어 있다고 할 수 있습니다.
- 노드가 한 개더라도 트리라고 할 수 있습니다.
- 자손 노드(Descendent node)
- 즉, 2번의 자손 노드는 4번과 5번 입니다.
- child node 라고도 부릅니다.
- 차수(degree) : 노드에 연결된 자식 노드의 수
- 1의 차수 = 2
- 2의 차수 = 2
- Tree의 차수 : Tree 내에 있는 노드들의 차수 중 가장 큰 값
- 위 그림의 트리는 차수가 2가 최대이므로, Tree의 차수가 2 입니다.
- 단말 노드(leaf node) : 차수가 0인 노드, 즉 자식 노드가 없는 노드
- 위 그림에서 3, 4, 5번 노드입니다.
- 높이(level) : 루트에서 해당 노드에 이르기까지의 간선 수
- 위 그림에서 2번 노드는 높이(레벨)가 1 입니다.
- 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값을 말합니다.
- 위 그림에서 4번 혹은 5번 노드의 높이가 2로 가장 크므로 트리의 높이는 2 입니다.