트리

트리란?

공집합이거나 r이 노드이고, S가 서로 분리된 트리의 집합일 때, 어떤 트리도 r을 포함하지 않는 쌍 (r, S) 이다.

노드 r : 트리의 루트

 

<용어 정리>

degree : subtree 집합의 크기. 즉, 자식노드 개수. degree가 0인 노드 == leaf node
루트경로 : 루트로부터 해당 노드까지 유일한 경로
루트-리프경로 : 루트에서 리프에 이르는 경로
경로의 길이 : 부모자식 쌍의 개수. 즉, 노드개수 -1
트리 경로길이 : 모든 노드의 깊이의 합
공백트리 : 유일하게 크기 0인 트리
단독트리 : 크기가 1인트리
트리 높이 : 최장 루트경로 길이
노드 깊이 : 노드까지의 루트경로 길이
트리 너비 : 최대 레벨 크기
레벨 : 주어진 깊이에서의 모든 노드
노드 차수 : 자식들 개수
트리 차수 : 최대 노드 차수
포화 트리 : 모든 리프가 같은 레벨이고, 모든 노드가 동일차수 가짐. 즉, 각 노드 차수 == 트리 차수
내부 노드 : 리프가 아닌 노드
외부 노드 : 리프 노드가 '데이터가 없는 더미 노드로 사용'될 경우
내부 경로 길이 : 내부 노드에만 적용되는 경로 길이
외부 경로 길이 : 어떤 레벨에서 외부 노드의 개수와 레벨을 곱한 값으로 주어지는 가중치의 합계

 

허프만 코드 트리

많이 출몰하는 단어(글자)는 이진수로 나타낼 때 길이를 짧게 하도록

 

 

 

 

 

 

동등 무순서 트리

트리 높이가 같고, 각 레벨에서의 노드 차수의 빈도수가 같은 경우

 

결정 트리

여러 대안들의 시퀀스를 분석하는 데 사용되는 무순서 트리

각 내부 노드 : 결정 내려지는 단계, 서브트리 : 그 단계에서의 대안

 

순서 트리

공집합이거나 r이 노드이고, S가 서로 분리된 트리의 시퀀일 때, 어떤 트리도 r을 포함하지 않는 쌍 (r, S) 이다.

순서트리 != 정렬트리

동등 무순서 트리처럼 생겼어도 서로 다른 트리라고 봄.

ex) 호출 트리

 

순회 알고리즘

레벨 순서 순회

<단계>

1. 큐 초기화하고

2. 루트 큐에 넣고

3. 밑 단계를 계속 반복하는데,

4. 큐에 있는 애 삭제하고 걔 방문하고 그 자식을 큐에 넣음

구조 : 레벨 0 -> 레벨 1 -> 레벨 2 -> ... 이런 식으로 순회하게 됨

 

전위 순회

루트 방문하고 그 왼쪽 자식 방문. 걔가 왼쪽 자식 있으면 또 그거 방문. 또..

만약 왼쪽 자식이 더이상 없으면 그 부모노드에 달려있는 나머지 자식노드들을 왼쪽부터 순서대로 방문하고

부모노드의 부모노드로 이동해서 그 자식노드 남은 거 순회

 

후위 순회

우선 가장 왼쪽 자식노드 방문하고 그 옆 자식노드들 방문하고 부모노드로 감. 여기서도 반복

 

완전 순서 트리

최하위 레벨 노드 중 오른쪽 몇 개의 원소 없는 거만 빼면 포화트리랑 같은 트리

장점 : 미사용 원소 없이 배열에 저장 가능, 배열 크기 : 트리에 있는 노드 개수

 

선형화(직렬화)

트리를 메모리나 디스크에 저장하는 법.

모든 순회 알고리즘을 선형화에 적용 가능.

자연 매핑 : 레벨 순서 순회를 사용해 선형화하는 과정

 

자연 인덱스 번호(노드 인덱스)

트리 레벨순서순회에 따라 순서적으로 매겨져있는 번호