열혈 자료구조 - 8-1 트리의 개요

트리의 접근과 이해

- 트리는 계층적 관계를 표현하는 자료구조

- 하나의 중심을 기점으로 뻗어나가는 구조

- ex) 조직도, 의사결정 트리

 

트리 관련 용어

- 노드 : 트리의 구성 요소 => A,B,C,D,E,F

- 간선 : 노드와 노드를 연결하는 연결 선

- 루트 노드 : 트리 구조에서 최상위에 존재하는 노드 => A

- 단말 노드 : 아래로 또 다른 노드가 연결되어 있지 않은 노드 => C,D,E,F

- 내부 노드 : 단말 노드를 제외한 모든 노드 => A,B

 

트리의 노드간 관계

- 부모-자식 관계 : 계층적으로 위-아래의 있는 관계

- 형제 관계 : 같은 부모 노드를 가지는 노드 간의 관계

 

서브 트리

- 트리는 또 다른 서브 트리로 구성되어 있고 그 서브 트리는 또 다시 서브트리로 구성되어 있음

- 이 서브트리는 재귀적인 구조를 띄고 있음

 

이진 트리의 이해

- 이진 트리의 조건

    -> 루트 노드를 중심으로 두 개의 서브 트리로 나누어 짐

    -> 나누어진 서브 트리도 모두 이진 트리어야 함

    -> 자식 노드가 없는 단말 노드도 서브 트리가 이진 트리라고 할 수 있는가? => 공집합 노드로 설명 가능

 

공집합 노드

- 노드가 있다고 간주하는 방식

- 공집합도 이진트리에서는 노드로 간주

- 이진 트리는 하나의 노드에 두개의 자식노드를 가지고 있는 트리

- 아래 그림의 좌측 트리처럼 완전하게 두개의 자식 노드를 가지고 있지 않아도 공집합 노드를 넣으면 이진 트리가 될 수있음

 

레벨과 높이

- 루트 노드를 기준으로 레벨 0부터 자식 노드로 가면서 레벨이 증가

- 높이는 최대 레벨의 값과 같음

 

포화 이진 트리, 완전 이진 트리

- 완전 이진 트리 : 위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리

- 포화 이진 트리 : 모든 레벨에 노드가 2개 꽉 차있는 이진 트리

- 포화 이진 트리 ⊂ 완전 이진 트리