트리

트리 관련 용어

트리를 구성하는 요소는 노드와 가지

각각의 노드는 가지를 통해 다른 노드와 연결되어 있다.

 

루트 

트리의 가장 윗부분에 위치하는 노드를 루트라고 한다.

하나의 트리에는 하나의 루트가 있다.

 

리프

트리의 가장 아랫부분에 위치하는 노드를 리프라고 한다.

(가장 아래에 위치한다 = 더 이상 뻗어나갈 수 없는 마지막에 노드가 위치한다.)

 

안쪽 노드

리프를 제외한 노드

 

자식 

어떤 노드로부터 가지로 연결된 아래쪽 노드

 

부모

어떤 노드에서 가지로 연결된 위쪽 노드

 

형제 

같은 부모를 가지는 노드

 

조상

어떤 노드에서 가지로 연결된 위쪽 노드 모두

 

자손

어떤 노드에서 가지로 연결된 아래쪽 노드 모두

 

레벨

루트로부터 얼마나 떨어져 있는지에 대한 값을 레벨이라고 한다.

루트의 레벨은 0, 가지가 하나씩 아래로 뻗어나갈때마다 레벨 1씩 증가

 

차수

노드가 갖는 자식의 수를 차수라고 한다.

 

높이

루트로부터 가장 멀리 떨어진 리프까지의 거리

 

서브 트리

트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리

 

널 트리

노드, 가지가 없는 트리

 

순서 트리와 무순서 트리

형제 노드의 순서를 따지면 순서트리

따지지 않으면 무순서 트리

 

순서트리 탐색방법

1. 너비 우선 탐색

낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려간다.

 

2. 깊이 우선 탐색

깊이 우선 탐색은 리프까지 내려 가면서 검색하는 것을 우선순위로 하는 탐색 방법이다.

리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우에는 부모에게 돌아가고 다시 자식 노드로 내려간다.

 

노드를 지나가는 최댓값 3회

1. 출발하면서 노드를 방문하는 경우

2. 옆에 형제 노드로 지나가면서 방문하는 경우

3. 되돌아오면서 노드를 방문하는 경우

 

 

---

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문 : 자바 편 [시바타 보요, 옮긴이 : 강민 (이지스퍼블리싱)]