[HUFS/자료구조] #8 트리

트리(Tree)

계층적인 자료의 표현에 적합한 자료 구조 ex) 조직도, 가계도

지금까지 배운 선형 자료 구조들과 다르게 비선형 자료 구조

 

나무를 뒤집어 놓은 것처럼 계층적 자료 표현

상위 루트 노드는 단 하나이며 부모-자식 관계를 형성하며 내려간다

노드의 ‘부모/자식/형제’ 관계와 ‘조상(부모 이상)/자손’ 관계가 정의된다

계층에 따라 위부터 레벨이 나눠지며 트리의 높이는 최고 레벨 값이다

더 이상 자식이 없는 노드는 단말 노드이며 그렇지 않은 노드는 비단말 노드이다

자식 노드의 수가 해당 노드의 차수이며 트리의 차수는 노드 차수들 중 최대 차수이다

이러한 노드 구조들을 통틀어 포레스트(forest)라고 한다

 

트리의 표현 방법 / 연결 리스트를 활용해 노드를 링크로 연결하는 트리도 가능하다

이진 트리

모든 노드가 2개의 서브 트리를 가지거나 공집합인 트리이다

서브트리는 공집합일 수 있으며 이진 트리는 순환적으로 정의된다

 

트리의 각 레벨에 노드가 꽉 차있다면 포화 이진 트리이다

 

포화 이진 트리의 경우 노드의 번호

포화 이진트리 / h-1까지는 꽉 찬 완전 이진트리 / 그 외 기타 이진트리

* 단, 완전 이진트리의 경우 마지막 레벨 h에서는 노드가 좌측부터 순서대로 채워진다!

 

이진 트리의 성질 1

이진 트리의 성질 2

배열 표현법: 노드에 붙인 번호대로 배열에 차례대로 넣어준다 (경사 이진 트리 주의)

링크 표현법: 이중 연결 리스트에 자식 노드 정보를 저장해 링크로 연결

순회(traversal)

순회는 트리에 속하는 모든 노드를 한 번씩 방문하는 것이며,

선형 자료구조는 순회가 단순하지만 트리의 순회는 다양한 방법이 있다

 

이진트리의 기본 순회는 순서에 따라 전위/중위/후위로 나뉜다

전위 순회 예시 / 노드의 레벨 계산, 구조화된 문서 출력에 사용

중위 순회 예시 / 정렬에 사용

후위 순회 예시 / 폴더 용량 계산에 사용

방문 순서 전체 예시

레벨 순회는 노드를 레벨 순으로 검사한다

 

큐를 사용해 구현하며 순환을 사용하지 않는다

레벨 순회 알고리즘

이진 트리 연산: 노드 수 / 단말 노드 수

이진 트리 연산: 트리의 높이

테스트 프로그램

모르스 코드로 결정 트리를 응용해보자

 

모르스 부호의 인코딩과 디코딩

결정트리를 통한 디코딩과 시간 복잡도

힙 트리

힙(Heap)이란 완전이진트리를 기반으로 가장 큰(또는 작은) 값을 빠르게 찾도록 만들어진 자료 구조이다

 

최대 힙 / 최소 힙의 정의

힙의 예시 -> 이런 상태를 유지하면 힙 트리

힙의 삽입 연산 -> Upheap

힙의 삭제 연산 -> Downheap

배열을 이용한 힙의 구현 1

배열을 이용한 힙의 구현 2

최대 힙 클래스

최대 힙 삽입 연산

최대 힙 삭제 연산

테스트 프로그램

힙의 복잡도 최악의 경우

허프만 코드로 힙 트리를 응용해보자

 

텍스트에 나타난 문자들의 빈도수를 표로 기록해 내용을 압축한다!

빈도수가 높은 문자에 가변길이코드의 작은 비트 수를 할당한다  

최소 힙을 사용해 허프만 코드를 생성

허프만 코딩 트리 생성 프로그램