트리
트리란 노드라고 하는 정보 항목이 간선으로 연결되어 계층적 구조를 이루는 비선형 자료구조로서 다음 조건을 만족하는 하나 이상의 노드로 구성된 유한집합 T를 의미합니다.
조건 1. T의 원소 가운데 단 하나의 루트 노드가 존재한다.
조건 2. 루트 노드를 제외한 나머지 노드를 n개의 서로 분리된 부분 집합 T1, T2, T3... Tn으로 나누어지며 각 Ti는 트리가 된다. 이때 Ti를 T의 서브트리라고 합니다.
위사진으로 트리의 용어를 살펴봅시다.
차수 : 노드의 서브트리의 개수를 그 노드의 차수 또는 분기수라고 합니다. a의 차수는 3이고, c의 차수는 0f의 차수는 2입니다.
리프 노트 : 차수가 0인 노드를 리프 노드 또는 단말 노드 라고 합니다. 위 그림을 보면 C J K L M N이 해당됩니다.
부모노드 자식노드 형제 노드 : 어떤 노드 x의 서브트리 들의 루트 노드들을 x의 자식 노드라고 하고 x는 이 자식 노드의 부모 노드라고 합니다.
위 그림을 보면 a의 자식노드는 B C D이고 B C D의 부모노드는 a가 됩니다. 또한 같은 부모노드를 갖는 노드를 형제노드라고 합니다.
위 그림에서 B C D가 A라는 같은 부모 노드를 가지고 있기 때문에 B C D는 형제노드입니다.
조상, 후손 : 부모와 자식의 관계를 좀 더 확장시킨 개념으로 한 노드의 조상이라 하면 해당 노드에서부터 루트 노드에 이르는 경로상에 있는 모든 노드를 의미하며, M의 조상은 G D A입니다. 반대로 어떤 노드 x로부터 단말 노드에 이르는 경로상에 있는 모든 노드를 x의 후손이라 하며 B의 후손은 E F J K L입니다.
트리의 차수 : 그 트리 내의 노드의 차수 중에서 최대 차수를 의미하며 트리의 차수는 3입니다.
레벨 : 노드의 레벨이란 루트 노드로부터의 거리를 의미합니다. 여기서 루트노드는 A이고 B의 경우 루트노드와의 거리가 1이기 때문에 레벨이 1입니다. 그리고 E의 경우 루트노드부터의 거리가 2이기 때문에 레벨이 2입니다.
높이/ 깊이 : 트리의 높이랑 깊이는 최대 레벨의 1을 더한것으로 여기서 최대 레벨은 3이고 거기에 1를 더하면 4가 됩니다.
숲: 숲이란 n개의 분리된 트리의 집합으로 트리에서 루트노드를 제거하면 숲이 됩니다. 따라서 위그림 같은 경우 a를 제거하면
이렇게 숲이 됩니다.
순서트리
순서트리 : 노드의 배열 순서 특히 레벨이 같은 노드의 좌우 위치가 중요한 의미를 같은 트리이며 그렇지 않은 트리는 비순서트리라고 합니다.
닮음 : 구조는 동일하나 노드의 내용이 다른 트리
대등한 트리 : 구조가 동일하고 내용까지 동일한 트리
순서트리와 비순서트리 예시
위 순서트리를 보면 a가 제일 위에 있고 그다음 왼쪽아래부터 오른쪽 순으로 b c d e f g h 이렇게 있는 걸 볼 수 있습니다. 반면에 비순서트리는 그냥 아무렇게 노드가 있다고 보면 됩니다.
이진트리
이진트리란 각 노드의 차수가 2 이하인 순서트리입니다.
이진트리는 일반트리와 다르게 노드가 없어도 됩니다. 그리고 자식의 순서를 구분하여 왼쪽 서브트리와 오른쪽 서브트리로 나눕니다.
이진트리는 스레드 이진트리, 힙 , 이진 탐색 트리와 같이 다양한 형태로 응용됩니다.
이진트리는 다음과 같은 특성이 있습니다.
레벨 i에서 최대 노드의 수는 2의 i제곱입니다. 단 i는 공집합보다 크거나 같아야 됩니다.
높이가 h인 이진트리가 가질 수 있는 최대 노드의 수는 2의 h제곱 - 1입니다. 단 h는 1보다 크거나 같아야 됩니다.
모든 이진트리에 대해 단말 노드의 수를 n0 차수가 2인 노드수를 n2라고 하면 n0 = n2 + 1입니다.
이진트리는 4가지 종류가 있습니다.
포화 이진 트리 : 모든 리프 노드의 레벨이 같은 전 이진 트리
전 이진 트리 : 모든 노드의 차수가 0이거나 2인 이진트리
완전 이진트리 : 트리의 최대 레벨이 l일때 레벨 l-1까지는 포화 이진 트리를 형성하고 마지막 레벨 l에서는 왼쪽에서부터 중간에 빈자리 없이 리프 노드들로 채워진 트리
균형진 이진 트리 : 모든 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이의 차이가 많아야 1인 이진 트리
'과학 > 알고리즘' 카테고리의 다른 글
| (알고리즘 -4) 알고리즘의 설계 (0) | 2023.04.01 |
|---|---|
| (알고리즘 -3) 기본 자료구조 그래프 (0) | 2023.04.01 |
| (알고리즘 -1) 알고리즘 과 기본자료구조 배열 연결리스트 스택 큐 코드 (2) | 2023.03.20 |
