트리

<<트리>>

1. 원소 간에 일대다 관계를 맺는 비선형 자료구조

2. 원소 간에 계층 관계를 맺는 계층형 자료구조

3. 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조

4. 그래프 중에서 사이클을 포함하지 않는 연결 그래프

 

<<트리 용어>>

1. 노드 : 트리를 구성하는 원소들

2. 루트 노드: 트리의 시작 노드

3. 간선: 노드를 연결하는 선

4. 부모 노드: 어느 한 노드에 대하여 이 노드의 상위에 연결된 노드

5. 자식 노드: 현재 위치한 노드 아래에 연결된 노드

6. 형제 노드: 같은 부모를 같는 노드

7. 조상 노드: 서브 트리에 있는 하위 레벨의 노드들

8. 자손 노드: 서브 트리에 있는 하위 레벨의 노드들

9. 서브 트리: 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

10. 노드의 차수: 노드에 연결된 자식 노드의 수

11. 트리의 차수: 트리에 있는 노드의 차수 중에서 가장 큰 값

12. 단말 노드(리프 노드): 차수가 0이며 자식 노드가 없는 노드

13. 비단말 노드: 자식을 가지는 노드

14. 레벨: 트리의 각 층에 번호를 매기는 것으로서 루트의 레벨은 0이 되고 한 층씩 내려갈수록 1씩 증가

15. 노드의 높이: 루트에서 해당 노드에 이르는 간선의 수

16. 트리의 높이: 트리에 있는 노드의 높이 중에서 가장 큰 값

17. 포리스트: 트리에서 루트를 제거하여 만든 서브 트리의 집합

 

<<일반 트리>>

각 노드가 가질 수 있는 자식 노드의 개수에 제한이 없는 트리

 

<<이진 트리>>

1. 모든 노드의 자식 노드가 2개 이하인 트리

2. 트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리

3. 이진 트리의 서브 트리들은 모두 이진 트리임

4. 이진 트리는 공백 노드도 자식 노드로 취급함

 

<<포화 이진 트리>>

높이가 h인 이진 트리에서 모든 단말 노드가 레벨 h에 있는 트리

 

<<완전 이진 트리>>

마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차 있고 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리

 

<<편향 이진 트리>>

1. 왼쪽이나 오른쪽 서브 트리만 가지는 트리

2. 왼쪽 편향 이진 트리: 모든 노드가 왼쪽 자식 노드만을 가짐

3. 오른쪽 편향 이진 트리: 모든 노드가 오른쪽 자식 노드만을 가짐

 

<<트리의 표현 방법>>

1. 배열과 같은 순차 구조

2. 링크를 이용한 연결 리스트

 

<<이진 트리 순회>>

1. 전위 순회: 루트 누드 - 왼쪽 서브 트리 - 오른쪽 서브 트리 순으로 방문

2. 중위 순회: 왼쪽 서브 트리 - 루트 노드 - 오른쪽 서브 트리 순으로 방문

3. 후위 순회: 왼쪽 서브 트리 - 오른쪽 서브 트리 - 루트 노드 순으로 방문

 

<<스레드 이진 트리>>

자식 노드가 없는 경우 링크 필드에 NULL 대신 순회 순서상의 다른 노드를 가리키도록 설정하는 것

 

<<스레드>>

1. 트리의 다른 노드에 대한 포인터

2. 트리를 순회하는 정보로 활용

3. 순회 방법에 따른 방문 순서를 유지하는 포인터

 

<<히프>>

1. 여러 값 중에서 가장 크거나 가장 작은 값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조

2. 최대 히프와 최소 히프가 있음

 

<<최대 히프>>

1. 부모 노드의 킷값이 자식 노드의 킷값보다 항상 크거나 같은 크기 관계의 히프

2. 킷값이 가장 큰 노드를 찾기 위한 완전 이진 트리

3. 루트 누드: 킷값이 가장 큰 노드

 

<<최소 히프>>

1. 부모 노드의 킷값이 자식 노드의 킷값보다 항상 작거나 같은 크기 관계의 히프

2. 킷값이 가장 작은 노드를 찾기 위한 완전 이진 트리

3. 루트 노드: 킷값이 가장 작은 노드

 

<<우선순위 큐>>

1. 우선순위를 가진 항목들을 저장하는 큐

2. 데이터가 입력된 순서와는 상관없이 우선순위가 높은 데이터가 가장 먼저 처리

3. 최소 우선순위 큐, 최대 우선순위 큐로 구분됨

4. 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제에서의 작업 스케줄링 등과 같이 컴퓨터의 여러 분야에서 으용

 

<<이진 탐색 트리>>

이진 트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정의한 것

 

<<이진 탐색 트리의 정의>>

1. 모든 노드는 서로 다른 유일한 킷값을 갖춤

2. 임의의 노드 킷값은 왼쪽 서브 트리의 킷값보다 큼

3. 임의의 노드 킷값은 오른쪽 서브 트리의 킷값보다 작음

4. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리임

 

<<선택 트리>>

1. 단말 노드를 제외한 모든 노드가 두 개의 자식 노드 중 작은 값을 갖게 되어 결국 루트 노드는 단말 노드 중에서 최소의 값을 갖게 되는 이진 트리

2. 승자 트리와 패자 트리 두 종류가 있음

 

<<승자 트리>>

1. 부모 노드가 두 자식 노드보다 작은 값을 갖는 완전 이진 트리

2. 가장 작은 킷값을 가진 원소가 승자로 올라가는 토너먼트 경기

3. 트리의 각 내부 노드는 두 자식 노드 원소의 토너먼트 승자

4. 루트 노드는 전체 토너먼트 승자

 

<<패자 트리>>

1. 트리의 각 내부 노드에 승자가 아닌 패자를 저장

2. 루트 노드 위에 0번 노드가 추가된 완전 이진 트리

3. 비단말 노드는 패자이며 승자는 상위 노드로 진출

4. 최상위 0번 노드에는 최종 승자가 저장됨

 

<<포리스트>>

1. n>=0개 이상의 분리된 트리의 집합 

2. 트리에서 루트(혹은 다른 노드)를 제거하면 쉽게 만들어짐