[Java] 트리

Do it! 자료구조와 함께 배우는 알고리즘 입문 읽고 정리

 

10-1 트리

- 트리란?

데이터 사이의 계층 관계를 나타내는 자료구조

 

- 트리 관련 용어

트리는 노드와 가지로 구성

(1) 루트: 트리의 가장 윗부분에 위치하는 노드

(2) 리프: 트리의 가장 아랫부분에 위치하는 노드

(3) 안쪽 노드: 루트를 포함하여 리프를 제외한 노드

(4) 자식: 어떤 노드로부터 가지로 연결된 아래쪽 노드

(5) 부모: 어떤 노드에서 가지로 연결된 위쪽 노드

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

(7) 조상: 어떤 노드에서 가지로 연결된 위쪽 노드들

(8) 자손: 어떤 노드에서 가지로 연결된 아래쪽 노드들

(9) 레벨: 루트로부터 얼마나 떨어져 있는지에 대한 값

(10) 차수: 노드가 갖는 자식의 수

(11) 높이: 루트로부터 가장 멀리 떨어진 리프까지의 거리

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

(13) 널 트리: 노드, 가지가 없는 트리

(14) 순서 트리와 무순서 트리: 형제 노드의 순서가 있는지 없는지에 따라 트리를 두 종류로 분류

 

- 순서 트리 탐색

(1) 너비 우선 탐색

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

 

(2) 깊이 우선 탐색

깊이 우선 탐색은 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법이다. 리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우 부모에게 돌아간다.

 

10-2 이진트리와 이진검색트리

- 이진트리

노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리라고 한다. 각 노드의 자식은 2명 이하만 유지해야 한다.

 

- 완전이진트리

루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리라고 한다.

(1) 마지막 레벨을 제외한 레벨은 노드를 가득 채운다.

(2) 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없다.