트리

이름과 비슷하게 나무를 닮은 자료구조입니다 나무는 뿌리에서부터 가지들이 뻗어 나와서 분기되고 가지 끝에는 잎이 달리듯이 트리라는 자료구조는 계층적인 관계를 한 자료의 표현에 매우 유용하게 사용됩니다. 예를 들어 회사의 조직 체계를 트리로 표현하면 사장은 뿌리에 해당하고, 사장 밑에 있는 각 부서의 부장은 뿌리에서 뻗어 나온 가지에 해당합니다.

나무의 달린 잎들의 순서를 매기기 어려운 것처럼 트리에 저장된 자료도 일렬로 나열하기 어렵고, 따라서 트리는 비선형 구조 입니다. 컴퓨터에서도 계층적인 관계를 표현하기 위해 트리가 다양하게 활용됩니다. 운영체제에서의 폴더 구조 표현, 효율적인 탐색을 위해 탐색트리, 우선순위 큐를 위한 힙 트리, 인공지능에서 의사결정 구조를 표현하기 위한 결정트리 등의 트리의 응용분야는 광범위합니다.

트리용어

트리에서 각각의 요소를 노드 노드 사이의 연결 관계를 간선 또는 예지 라고 합니다
조직도에서 "사장"과 같이 계층구조의 최상위 노드를 루트(root)라 부르고, 나머지 노드들은 서브트리 라 부릅니다 트리에서 모든 노드는 자신을 루트로 하는 하나의 서브를 트리를 대표합니다. 트리는 순환적으로 정의되는 자료구조 입니다.
트리의 노드 사이에는 인간의 관계와 같이 부모 ,자식 ,형제 ,조상 및 자손의 관계가 존재합니다. 예를 들어 , 간선으로 직접 연결된 노드 사이에 상위노드를 부모, 하위노드를 자식으로 부르는 식입니다 자식이 없으면 단말이고 있으면 비 단말 노드입니다.
노드가 가지고 있는 자식의 수를 차수 라 합니다 예를 들어, 단말 노드의 차수는 항상 0입니다. 또한 트리에 포함된 모든 노드의 차수 중에서 가장 큰 수를 트리의 차수라 고합니다.
트리의 각층에 번호를 매긴 것을 레벨이라고 합니다. 보통 루트의 레벨은 1이고 한 층 씩 내려갈수록 1씩 증가합니다. 트리가 가지고 있는 최대 레벨을 트리의 높이라고 합니다.

트리의 표현

트리는 여러 방법으로 표현할 수 있지만, 가장 일반적인 방법은 노드와 간선을 이용하는 것입니다. 노드는 자료를 저장하는 데이터 필드와 자식들을 가리키는 링크 필드를 갖는데, 이때 링크의 수는 그 노드의 차수(자식의 수)가 됩니다. N-링크표현으로 불리는 이 방법은 간단해 보이지만 자식의 수에 제한이 없는 일반트리를 나타내는 데는 문제가 있습니다. 노드마다 자식 수가 다를 것이므로 링크를 저장할 배열의 크기를 고정할 수 없습니다.

노드를 약간 변형하면 두 개의 링크만으로 일반 트리를 표현할 수도 있습니다. 링크하나는 왼쪽 자식을 가리키고, 아른 하나는 오른쪽 형제를 가리키는 것입니다. 노드에는 자신의 정보와 자신의 첫 번째 자식과 다음 형제의 위치만을 저장합니다.

중첩된 집합

트리가 서브 트리들의 집합이라는 것을 잘 표현됩니다.

루트와 서브 트리를 중첩된 괄호로 묶어 표현할 수도 있습니다

들여 쓰기로도 트리를 표현할 수 있는데 자료가 계층적인 구조를 갖는 것을 잘 나타냅니다. 윈도우 탐색기에서 폴더와 파일을 나타내기 위해 이 방법을 사용합니다.

이진트리

자식의 수를 최대 2개로 제한한 트리입니다. 모든 노드는 왼쪽 자식을 루트로 하는 왼쪽 서브트리와 오른쪽 자식을 루트로 하는 오른쪽 서브트리를 갖는데 만약 자식이 없으면 서브트리는 공집합입니다 자식들 사이에는 순서가 있는데 왼쪽 자식과 오른쪽 자식은 반드시 구별되어야 합니다.

이진트리의 종류

포화 이진트리

모든 레벨에 노드가 꽉 차 있는 이진트리를 말합니다 포화 이진트리는 높이를 알면 등비수열의 법칙과 같이 전체 노드의 수를 바로 계산할 수 있습니다.

이 식을 더 간단하게 바꾸면 2^(높이) −1 식으로 간단하게 할 수 있습니다

이 포화 이진트리를 식으로 바꾸면 2³⁺¹)-1 로 계산을 해보시면 8-1 = 7 전체 노드수는 7입니다

완전 이진 트리

높이가 k인 트리에서 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k는 왼쪽부터 노드가 순서대로 채워져 있는 이진 트리를 말합니다. 마지막 레벨은 노드가 꽉 차 있지 않아도 되지만 중간에 빈 곳이 있으면 안 됩니다.

균형 이진트리

이진 트리에 좌우 "균형"의 개념을 적용할 수 있습니다. 균형 이진 트리 또는 높이 균형 이진트리는 모든 노드에서 좌우 서브 트리의 높이 차이가 1 이하인 트리를 말합니다.

이진트리의 성질

트리에서 루트를 제외한 모든 노드는 부모로 가는 하나의 간선을 갖습니다. 따라서 n개의 노드를 가진 트리는 반드시 n-1개의 간선을 갖습니다.

높이가 h인 이진트리는 최소 h개의 노드를 가져야 하는데 한 레벨에 적어도 하나의 노드는 있어야 하기 때문입니다

또한 높이가 h이면 최대 2^h -1 개의 노드를 갖는다는 것을 알 수 있는데, 포화 이진트리가 같은 높이에서 노드의 수가 최대인 트리이기 때문입니다.

경사 이진트리인 경우 높이=노드수 포화 이진트리인경우 최소 높이 = (log₂(노드수+1)) = (log₂(7+1)) = log₂(8) = log₂(2³) = 3log₂(2) = 3 <- 최소 높이

배열 표현법

이진트리를 포화 이진트리의 일부라고 생각하면 배열 구조로 트리를 표현할 수 있습니다.

링크 표현법

단말 노드부터 시작해 서브 트리를 순차적으로 병합하는데 마지막에 생성되는 루트 노드가 전체 트리를 대표합니다.

이진트리의 순회

트리를 순회한다는 것은 트리의 모든 노드를 한 번씩 방문하는 것을 말합니다 선형 자료구조에서는 자료가 일렬로 저장되어 있어서 순회가 매우 단순합니다. 순서대로 방문하면 되기 때문입니다 그러나 트리에서는 노드가 일렬로 나열도어 있지 않기 때문에 여러 가지 '순서'로 노드를 방문할 수 있어 순회 방법이 다양합니다.

표준 순회

전위 순회(preorder traversal): VLR
중위 순회(inorder traversal): LVR
후위순회(postorder traversal): LRV

전위순회

전위순회는 루트 노드를 먼저 탐색하고, 자식 노드를 탐색하는 방식입니다.

중위 순회

중위순회는 왼쪽 자식 노드를 탐색하고, 루트 노드를 탐색하고, 오른쪽 자식 노드를 탐색하는 방식입니다.

후위순회

후위순회는 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식입니다.

레벨 순회

레벨순회는 루트 노드를 먼저 탐색하고, 그다음 레벨의 노드를 탐색하는 방식입니다. queue를 하나 선언해 두고, 루트 노드를 넣어준 다음, queue에 넣어준 노드를 하나씩 탐색하면서 자식 노드를 queue에 넣습니다. queue가 비어있을 때까지 반복합니다.

이진트리 노드 갯수 구하기 = (왼쪽 서브 트리 +오른쪽 서브트리 +1)

이진트리 높이 구하기 = 왼쪽 서브트리의 높이와 오른쪽 서브 트리의 높이 중에서 큰 값에 1을 더한 값

이진 탐색 트리

대부분의 탐색은 컴퓨터에서 가장 중요한 작업 중 하나입니다. 탐색을 위해서는 찾을 자료를 식별할 수 있는 유일한 값이 필요한데 이것을 키(key)라고 합니다 사람을 탐색할 때 전화번호나 주민등록번호를 사용한다면 그것이 탐색 키가 됩니다. 탐색에 트리 구조를 이용할 수도 있는데 이진 탐색 트리는 효율적인 탐색을 위한 이진트리 기반의 자료 구조입니다.