데이터 구조의 이진 트리: 속성, 유형, 표현 및 이점

다른 유형의 데이터 구조 중에는 대부분의 다른 유형보다 더 많이 사용되는 이진 트리가 있습니다. 가장 주목할만한 응용 프로그램에는 P2P 프로그래밍, 검색, 암호화, 다른 것보다 높은 대역폭을 가진 네트워크 라우터 및 3D 비디오 게임이 있습니다. 이제 데이터 과학에서 이진 트리가 무엇인지, 유형이 무엇인지, 어떻게 표현되는지 자세히 논의할 것입니다.

이진 트리란 무엇입니까?

이전에 일반 트리에 대해 작업한 적이 있거나 기본 트리에 대해 알고 있는 경우 다른 노드가 이러한 트리에서 가질 수 있는 자식 수에 대해 제한이 없음을 알 수 있습니다. 이진 트리는 이러한 의미에서 약간 다릅니다. 이진 트리의 모든 부모 또는 노드에는 최대 두 개의 자식만 있을 수 있습니다.

이진 트리의 모든 노드에는 세 가지 기본 구성 요소가 있습니다.

• 데이터 요소
• 올바른 참조
• 왼쪽 참조

트리의 맨 위에 있는 노드를 루트 노드라고 합니다. 부모 노드는 자식이 있는 노드입니다. 자식 노드와 부모 노드는 참조를 통해 서로 연결됩니다. 자식이 없는 노드를 리프 노드라고 합니다.

이진 트리의 노드에는 자식이 하나, 두 개 또는 전혀 없을 수 있다는 것이 분명합니다. 이진 트리는 큐, 배열, 스택 및 연결 목록과 같은 선형 데이터 구조가 아닙니다. 대신 계층적 데이터 구조입니다.

확인: 초보자를 위한 데이터 과학 프로젝트 아이디어

이진 트리에서 노드의 중요한 속성

이러한 속성을 더 잘 이해하면 이진 트리에 대한 논의를 최대한 활용하는 데 도움이 됩니다. 서로 다른 노드의 깊이는 루트와 특정 노드를 연결하는 경로에 존재하는 노드의 수로 정의됩니다. 이것이 루트 노드의 깊이가 0인 이유입니다. 반면에 이진 트리에서 다른 노드의 높이는 특정 노드와 루트 노드를 연결하는 경로에 있는 노드의 수입니다. 이것이 리프 노드의 높이가 0인 이유입니다.

분명히 알 수 있듯이 노드의 깊이는 루트 노드에서 시작하여 해당 노드까지 내려가는 방식으로 측정됩니다. 반면에 높이를 계산할 때 문제의 노드에서 시작한 다음 루트 노드로 이동합니다. 두 경우 모두 0에서 시작합니다. 높이와 깊이를 1에서 측정하고 0에서 측정하지 않는 사람이 있습니다. 이는 잘못된 것이 아니며 다른 사람들이 선호하는 것입니다.

이제 노드의 최대 깊이는 이진 트리의 깊이로 정의됩니다. 마찬가지로 노드의 최대 높이는 이진 트리의 높이로 정의됩니다. 따라서 이진 트리의 높이와 깊이는 항상 동일합니다.

자세히 알아보기: Python의 데이터 구조 및 알고리즘

이진 검색 트리란 무엇입니까?

이진 탐색 트리는 다른 모든 유형의 이진 트리 중에서 가장 일반적입니다. 다른 형태의 이진 트리보다 더 유용하고 다른 속성을 제공하는 특수 이진 트리입니다. 이진 검색 트리 또는 BST가 정확히 무엇입니까? 이름에서 알 수 있듯이 이진 검색 트리는 트리에서 데이터를 검색하는 데 사용됩니다.

BST는 효율적인 검색을 용이하게 하는 속성과 함께 제공됩니다. BST는 오른쪽 서브 트리의 노드와 왼쪽 서브 트리의 노드보다 각각 작은 노드와 큰 노드의 키를 갖는 이진 트리입니다.

이진 트리의 표현

1. 연결 표현

연결 표현의 이진 트리는 연결 목록으로 메모리에 저장됩니다. 이 목록에는 인접하거나 인접한 메모리 위치에 저장되지 않고 트리와 관련된 부모-자식 관계를 통해 서로 연결된 노드가 있습니다.

이 표현에서 각 노드에는 세 가지 다른 부분이 있습니다.

• 오른쪽 노드를 가리키는 포인터,
• 왼쪽 노드를 가리키는 포인터,
• 데이터 요소.

이것은 더 일반적인 표현입니다. 모든 이진 트리는 루트 노드의 방향을 가리키는 루트 포인터로 구성됩니다. null 또는 0을 가리키는 루트 노드를 보면 빈 이진 트리를 다루고 있음을 알아야 합니다. 오른쪽 및 왼쪽 포인터는 트리의 오른쪽 및 왼쪽 자식 주소를 저장합니다.

2. 순차적 표현

연결된 표현보다 간단하지만 비효율성으로 인해 둘 중 덜 선호되는 이진 트리 표현이 됩니다. 비효율성은 다른 트리 요소를 저장하는 데 필요한 공간의 양에 있습니다. 순차 표현은 트리 요소의 저장을 위해 배열을 사용합니다.

이진 트리의 노드 수는 사용 중인 배열의 크기를 정의합니다. 이진 트리의 루트 노드는 배열의 첫 번째 인덱스에 있습니다. 특정 노드가 저장되는 인덱스는 노드의 오른쪽 및 왼쪽 자식이 저장될 인덱스를 정의합니다. 빈 트리는 첫 번째 인덱스로 null 또는 0을 갖습니다.

이진 트리의 유형

1. 전체 이진 트리: 전체 이진 트리는 노드에 두 개의 자식이 있거나 없는 이진 트리입니다. 다시 말해, 이진 트리는 잎을 제외하고 다른 모든 노드에 두 개의 자식이 있을 때 완전한 이진 트리가 됩니다.
2. 완전한 이진 트리: 완전한 이진 트리는 서로 다른 모든 수준이 완전히 채워진 트리입니다. 이에 대한 유일한 예외는 키가 주로 왼쪽에 있는 마지막 레벨일 수 있습니다. 이진 힙은 종종 완전한 이진 트리의 예로 사용됩니다.
3. 완전 이진 트리: 완전 이진 트리는 잎이 같은 수준에 있고 내부 노드에 두 개의 자식이 있는 이진 트리입니다. 완벽한 이진 트리의 일반적인 예는 조상 가계도입니다.
4. 병리학 적 퇴화 이진 트리: 퇴화 트리는 내부 노드에 하나의 자식이 있는 이진 트리입니다. 성능 수준은 연결 목록과 유사합니다. 이진 트리 유형에 대해 자세히 알아보세요.

읽기: R에서 가장 일반적으로 사용되는 6가지 데이터 구조

이진 트리의 이점

1. 데이터를 계층적으로 저장하는 이상적인 방법
2. 주어진 데이터 세트에 존재하는 구조적 관계 반영
3. 연결 목록 및 배열보다 빠르게 삽입 및 삭제
4. 데이터를 보유하고 이동하는 유연한 방법
5. 가능한 한 많은 노드를 저장하는 데 사용됩니다.
6. 요소에 액세스할 때 연결 목록보다 빠르고 배열보다 느립니다.

결론

이 블로그에서는 데이터 구조의 이진 트리가 무엇인지 설명하고 유형, 표현 및 이점에 대해서도 설명했습니다. 트리의 두 가지 주요 용도는 데이터를 검색하고 저장하는 것이므로 데이터 과학 및 관련 분야 연구에 필수적입니다.

데이터 구조, 데이터 과학의 이진 트리에 대해 알아보려면 작업 전문가를 위해 만들어졌으며 10개 이상의 사례 연구 및 프로젝트, 실용적인 실습 워크샵, 업계 전문가와의 멘토링, 업계 멘토와의 1:1 학습, 일류 기업과의 400시간 이상의 학습 및 취업 지원.