7-1 트리

01. 트리

- 검색의 편리함

- 논리적 계층

- 계급적 특성

 

 

02. 용어와 논리적 표현 방법

트리의 구성

- 노드: 트리의 항목 / 트리에 저장되는 데이터의 묶음

- 부모노드-자식 노드 : 상하 계층구조가 있고 직접적으로 연결된 노드로서 상위계층의 부모노드와 하위계층의 자식 노드

 

루트노드 : 트리의 최상위 노드 (부모가 없는 노드)

서브트리 : 부모 노드를 삭제하면 생기는 트리들

리프노드 : 트리의 맨 끝(바닥)에 있으면서, 자신의 서브트리를 갖지 않는 노드

 

 

진입/진출 차수

- 루트 노드 : 진입차수 = 0 

- 루트를 제외한 모든 노드의 진입 차수 : 1

- 리프 노드 : 진출 차수 = 0

** 진출 차수 : 자식노드에게 가는 링크

 

- 노드의 레벨 : 루트로부터 그 노드까지 이어진선(경로)의 길이(개수)

- 트리의 높이 : 루트로부터 가장 멀리 있는 노드까지 이어진 선(경로)의 길이에 1을 더한 값

높이 4

 

03. 이진 트리

이진 트리의 정의

- 모든 노드의 차수가 2 이하인 트리

- 수학적으로 이진트리의 구성에 관한 이론을 정리하기 쉽고, 컴퓨터 내부에서 구현하기도 효율적임

- 모든 노드가 2개 이하의 자식노드를 가지므로 일바넝을 잃지 않고 '오른쪽', '왼쪽'이라는 방향 개념을 부여할 수 도 있음

→ 오른쪽 노드, 왼쪽 노드의 개념적 접근도 있음

 

 

 

포화 이진 트리의 정의

 

- 이진 트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리

 

완전 이진 트리의 정의

- 높이가 k인 이진 트리가 '0레벨'부터 'k-2레벨'까지 다 채우고, 

마지막 'k-1 레벨'에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진 트리