데이터 구조의 4가지 유형의 트리 설명: 속성 및 애플리케이션

데이터 구조의 트리란?

트리는 계층적 데이터를 나타내는 데이터 구조 유형입니다. 모서리로 연결된 노드로 구성된 비선형 구조입니다. 선형 데이터 구조에서 연산을 수행하는 다른 유형의 데이터 구조 중에서 데이터 크기가 커질수록 복잡성이 증가합니다. 그러나 트리 데이터 구조 를 사용하면 비선형 데이터에 더 빠르게 액세스할 수 있습니다. 다양한 유형의 데이터 구조 및 이와 관련된 알고리즘의 가용성으로 인해 작업 수행이 쉽고 효율적인 방법이 되었습니다.

데이터 구조의 트리 와 관련된 몇 가지 용어 는 다음과 같습니다.

• 노드 : 노드는 키 또는 값과 해당 자식 노드에 대한 포인터를 포함하는 트리 데이터 구조의 엔터티입니다.
• 자식 노드 : 자식 노드는 모든 노드의 자손입니다.
• 리프 노드: 자식 노드가 없고 트리에서 가장 아래에 있는 노드입니다. 외부 노드라고도 합니다.
• 루트 : 트리의 최상단 지점입니다.
• 내부 노드 : 자식 노드가 하나 이상 있는 노드입니다.
• 에지: 에지는 트리의 두 노드 사이의 연결을 나타냅니다.
• 노드 높이: 노드에서 가장 깊은 잎까지의 가장자리 수.
• 노드의 깊이 : 루트에서 노드까지의 가장자리 수입니다.
• 트리 높이 : 루트 노드의 높이.
• 노드 정도 : 해당 노드에 대한 총 분기 수입니다.
• 숲: 분리된 나무의 집합입니다.

나무의 종류

1. 이진 트리

이진 트리는 모든 상위 노드에 최대 두 개의 하위 노드가 있는 트리 데이터 구조 유형입니다 . 이름에서 알 수 있듯이 바이너리는 2를 의미하므로 각 노드는 0, 1 또는 2개의 노드를 가질 수 있습니다. 이진 트리 데이터 구조 는 그림 1에 나와 있습니다. 트리 의 노드 1에는 각 자식 노드에 대해 하나씩 두 개의 포인터가 있습니다. 노드 2에는 두 개의 자식 노드에 대해 각각 두 개의 포인터가 있습니다. 반면 노드 3, 5, 6은 리프 노드이므로 왼쪽과 오른쪽 부분 모두에 널 포인터가 있습니다.

그림 1: 이진 트리 표현( https://www.javatpoint.com/binary-tree ).

이진 트리의 속성

• I 의 각 수준에서 노드의 최대 수는 2 i 입니다.
• 그림 1 에서 트리의 높이는 3이며, 이는 최대 노드 수가 (1+2+4+8) = 15임을 의미합니다.

• 높이 h에서 가능한 최대 노드 수는 (20 + 21 + 22+….2h) = 2h+1 -1입니다.

• 높이 h에서 가능한 최소 노드 수는 h+1과 같습니다.

• 최소 노드 수는 최대 높이의 트리를 나타내며 그 반대의 경우도 마찬가지입니다.

이진 트리조차도 다음 유형의 트리로 나눌 수 있습니다.

• 전체 이진 트리: 특수한 유형의 이진 트리입니다. 이 트리 데이터 구조에서 모든 상위 노드 또는 내부 노드에는 두 개의 하위 노드가 있거나 하위 노드가 없습니다.
• 완벽한 이진 트리: 이 유형의 트리 데이터 구조 에서 모든 내부 노드에는 정확히 두 개의 자식 노드가 있고 모든 리프 노드는 동일한 수준에 있습니다.
• 완전 이진 트리: 몇 가지 차이점이 있는 전체 이진 트리와 유사합니다.
• 모든 레벨이 완전히 채워집니다.
• 리프 노드는 트리의 왼쪽으로 기울어져 있습니다.
• 마지막 리프 노드가 올바른 형제를 가질 필요는 없습니다. 즉, 완전한 이진 트리가 완전한 이진 트리일 필요는 없습니다.
• 퇴화 또는 병리학적 트리: 이 트리에는 상위 노드의 왼쪽 또는 오른쪽에 단일 자식이 있습니다.
• 편향된 이진 트리: 트리가 왼쪽 노드 또는 오른쪽 노드에 의해 지배되는 병리학적 또는 퇴화 트리입니다. 따라서 기울어진 이진 트리에는 두 가지 유형, 즉 왼쪽으로 치우친 이진 트리 또는 오른쪽으로 치우친 이진 트리가 있습니다.
• 균형 이진 트리: 각 노드의 왼쪽 및 오른쪽 하위 트리 높이의 차이는 0 또는 1입니다.

2. 이진 검색 트리

이러한 트리 구조는 비선형이며 하나의 노드가 여러 노드에 연결됩니다. 노드는 최대 2개의 자식 노드에 연결할 수 있습니다. 다음과 같은 이유로 이진 검색 트리라고 합니다.

• 각 노드에는 최대 2개의 하위 노드가 있습니다.
• 0(log(n)) 시간에 요소를 검색하는 데 사용할 수 있으므로 검색 트리라고 합니다.

그림: 이진 검색 트리의 예( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

이진 검색 트리의 속성은 다음과 같습니다.

• 왼쪽 하위 트리의 모든 노드 값은 루트 노드 값보다 작아야 합니다.
• 오른쪽 하위 트리의 모든 노드 값은 루트 노드 값보다 커야 합니다.

3. AVL 트리

AVL 트리는 이진 트리의 유형 또는 변형입니다. 이진 검색 트리와 이진 검색 트리의 속성으로 구성됩니다. Adelson Velsky Lindas가 발명한 이 트리는 자체 균형을 유지하므로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 균형을 이루고 있습니다. 이 균형은 균형 요인으로 측정됩니다.

균형 요소:

• 왼쪽 서브트리와 오른쪽 서브트리의 차이입니다.
• 균형 요소의 값은 0, -1 또는 1이어야 합니다. 따라서 AVL 트리의 각 노드는 균형 요소 값, 즉 0, -1 또는 1로 구성되어야 합니다.
• 균형 요소 = (왼쪽 하위 트리의 높이 – 오른쪽 하위 트리의 높이)
• AVL 트리는 각 노드의 균형 요소가 -1에서 1 사이인 경우 균형 트리라고 합니다.

AVL 트리에서 -1이 아닌 다른 노드의 값은 1로 균형을 맞춰야 하는 불균형 트리를 나타냅니다.

• 노드의 균형 계수가 1이면 왼쪽 하위 트리가 오른쪽 하위 트리보다 한 수준 높음을 의미합니다.
• 노드의 균형 계수가 0이면 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 동일함을 의미합니다.
• 노드의 균형 계수가 -1이면 오른쪽 하위 트리가 왼쪽 하위 트리보다 한 수준 높거나 왼쪽 하위 트리가 오른쪽 하위 트리보다 한 수준 낮음을 의미합니다.

4. B-트리

B 트리는 이진 탐색 트리의 보다 일반화된 형태입니다. 높이 균형 m 방법 트리라고도 하며 여기서 m은 트리의 차수입니다. 트리의 각 노드는 둘 이상의 키와 둘 이상의 자식 노드를 가질 수 있습니다. 이진 트리의 경우 리프 노드가 같은 수준에 있지 않을 수 있습니다. 그러나 B Tree의 경우 모든 리프 노드가 동일한 수준에 있어야 합니다.

B-트리의 속성:

• 키는 각 노드 x에 대해 오름차순으로 저장됩니다.
• 부울 값 "x.leaf"는 각 노드에 존재하며 x가 리프인 경우 true입니다.
• 내부 노드는 최대 "n-1" 키를 가져야 합니다. 여기서 n은 트리의 순서입니다. 또한 각 자식에 대한 포인터가 있어야 합니다.
• 모든 노드는 루트 노드를 제외하고 최대 n개의 자식과 최소 n/2개의 자식을 갖습니다.
• 트리의 리프 노드는 동일한 깊이를 갖습니다.
• 루트 노드에는 최소 1개의 키와 최소 2개의 자식이 있습니다.
• n ≥ 1이면 높이가 h이고 최소 차수가 t ≥ 2인 n키 B-트리에 대해 h ≥ logt(n+1)/2입니다.

애플리케이션

• 요소 집합에서 요소를 검색하는 데 이진 검색 트리를 적용할 수 있습니다.
• 힙 트리는 힙 정렬에 사용됩니다.
• 최신 라우터는 라우팅 정보를 저장하기 위해 Tries라는 유형의 트리를 사용합니다.
• B-트리와 T-트리는 대부분 인기 있는 데이터베이스에서 데이터를 저장하는 데 사용됩니다.
• 구문 트리는 작성된 모든 프로그램의 구문을 검증하기 위해 컴파일러에서 사용됩니다.

결론

데이터 구조는 쉬운 관리와 효과적인 처리를 위해 데이터를 저장하는 체계적인 방법을 제공합니다. 다양한 유형의 데이터에 대해 다양한 유형의 데이터 구조가 존재합니다. 저장해야 하는 데이터 유형에 따라 사용자가 선택합니다.

트리는 계층적 유형의 데이터를 저장할 수 있는 데이터 구조 유형입니다. 데이터는 때때로 자식 노드라고 하는 다른 노드에 대한 참조를 저장하는 노드에 저장됩니다.

트리는 자식 노드의 수에 따라 기사에서 언급한 것처럼 다양한 유형으로 분류할 수 있습니다. 트리 유형의 노드 배열에 따라 각 트리 구조에는 연관된 속성이 있습니다. 다양한 종류의 트리에서 수행할 수 있는 다양한 유형의 작업을 통해 이러한 유형의 데이터 구조는 정렬 알고리즘 및 데이터 저장 분야에서 응용 프로그램을 찾았습니다.

upGrad & IIIT-Bangalore가 큐레이팅한 소프트웨어 개발의 이그 제 큐 티브 PG 프로그램 – 풀 스택 개발 전문화는 프로필을 개선하고 프로그래머로서 더 나은 고용 기회를 확보하는 데 도움이 될 수 있습니다.