이진 트리의 5가지 유형 설명 [일러스트와 함께]

컴퓨터 과학에서 다양한 데이터 구조는 데이터를 다양한 형식으로 배열하는 데 도움이 됩니다. 그 중 트리는 계층적 트리 구조를 시뮬레이션하는 추상 데이터 구조로 널리 사용됩니다. 트리에는 일반적으로 상위 노드의 하위 노드에 의해 형성된 루트 값과 하위 트리가 있습니다. 트리는 비선형 데이터 구조입니다.

일반적인 트리 데이터 구조는 보유할 수 있는 자식 노드의 수에 제한이 없습니다. 그러나 이것은 이진 트리의 경우가 아닙니다. 이 기사에서는 특정 트리 데이터 구조(이진 트리 및 이진 트리 유형)에 대해 학습합니다 .

이진 트리 데이터 구조란 무엇입니까?

이진 트리는 각 부모에 대해 최대 2개의 자식이 있는 트리 유형 의 비선형 데이터 구조입니다. 이진 트리 의 모든 노드 에는 데이터 요소와 함께 왼쪽 및 오른쪽 참조가 있습니다. 트리 계층 구조의 맨 위에 있는 노드를 루트 노드라고 합니다. 다른 하위 노드를 보유하는 노드가 상위 노드입니다.

부모 노드에는 왼쪽 자식과 오른쪽 자식이라는 두 개의 자식 노드가 있습니다. 해싱, 네트워크 트래픽을 위한 데이터 라우팅, 데이터 압축, 이진 힙 준비 및 이진 검색 트리는 이진 트리를 사용하는 일부 응용 프로그램입니다.

이진 트리 및 이진 트리 유형과 관련된 용어

• 노드: 트리의 종료 지점을 나타냅니다.
• 루트: 트리의 최상위 노드입니다.
• 상위: 자체 하위 노드가 하나 이상 있는 트리의 각 노드(루트 제외)를 상위 노드라고 합니다.
• 자식: 루트에서 멀어질 때 부모 노드에서 바로 나온 노드가 자식 노드입니다.
• 리프 노드: 외부 노드입니다. 자식이 없는 노드입니다.
• 내부 노드: 이름에서 알 수 있듯이 최소한 하나의 자식이 있는 내부 노드입니다.
• 트리의 깊이: 트리의 노드에서 루트까지의 가장자리 수입니다.
• 트리 높이: 노드에서 가장 깊은 잎까지의 가장자리 수입니다. 트리 높이는 루트 높이로도 간주됩니다.

이제 이진 트리 및 이진 트리 유형과 관련된 용어에 익숙해졌으므로 이제 이진 트리 구성 요소 를 이해할 차례 입니다. 이진 구조 및 구성 요소에 대해 자세히 알아보려면 데이터 과학 과정을 확인하십시오.

이진 트리 구성 요소

세 가지 이진 트리 구성 요소 가 있습니다. 모든 이진 트리 노드에는 이러한 세 가지 구성 요소가 연결되어 있습니다. 프로그래머가 다음 세 가지 이진 트리 구성 요소 를 이해하는 것이 필수 개념이 됩니다 .

1. 데이터 요소
2. 왼쪽 하위 트리에 대한 포인터
3. 오른쪽 하위 트리에 대한 포인터

원천

이 세 가지 이진 트리 구성 요소 는 노드를 나타냅니다. 데이터는 중간에 있습니다. 왼쪽 포인터는 자식 노드를 가리키며 왼쪽 하위 트리를 형성합니다. 오른쪽 포인터는 오른쪽에 있는 자식 노드를 가리키며 오른쪽 하위 트리를 만듭니다.

읽기: 데이터 과학을 위한 최고의 추측 질문 및 유익한 방법

이진 트리의 유형

이진 트리 에는 다양한 유형이 있으며 이러한 각 이진 트리 유형 에는 고유한 특성이 있습니다. 다음은 각 이진 트리 유형 에 대한 세부 정보입니다.

1. 전체 이진 트리

자식이 없거나 두 개 있는 특수한 종류의 이진 트리입니다. 이는 해당 바이너리 트리의 모든 노드가 부모 노드의 두 개의 자식 노드를 가지거나 부모 노드 자체가 리프 노드 또는 외부 노드임을 의미합니다.

즉, 전체 이진 트리는 외부 노드를 제외한 모든 노드에 두 개의 자식이 있는 고유한 이진 트리입니다. 단일 자식을 보유하는 경우 이러한 이진 트리는 전체 이진 트리가 아닙니다. 여기서 리프 노드의 수는 내부 노드의 수에 1을 더한 것과 같습니다. 방정식은 L=I+1과 같습니다. 여기서 L은 리프 노드의 수이고 I은 내부 노드의 수입니다.

다음은 전체 이진 트리의 구조입니다.

2. 이진 트리 완성

완전한 이진 트리는 트리의 가장 낮은 수준을 제외하고 모든 트리 수준이 완전히 노드로 채워지는 또 다른 특정 유형의 이진 트리입니다. 또한 이 이진 트리의 마지막 또는 가장 낮은 수준에서 모든 노드는 왼쪽에 있어야 합니다. 다음은 완전한 이진 트리의 구조입니다.

3. 완벽한 이진 트리

모든 내부 노드가 엄격하게 두 개의 자식을 갖고 모든 외부 또는 리프 노드가 트리 내에서 동일한 수준 또는 동일한 깊이에 있는 경우 이진 트리를 '완벽'하다고 합니다. 높이가 'h'인 완벽한 이진 트리에는 2h – 1개의 노드가 있습니다. 다음은 완벽한 이진 트리의 구조입니다.

4. 균형 이진 트리

트리 높이가 O(logN)인 경우 이진 트리는 '균형'이라고 합니다. 여기서 'N'은 노드 수입니다. 균형 이진 트리에서 각 노드의 왼쪽 및 오른쪽 하위 트리의 높이는 최대 1만큼 달라야 합니다. AVL 트리와 레드-블랙 트리는 균형 이진 검색 트리를 생성할 수 있는 데이터 구조의 몇 가지 일반적인 예입니다. 다음은 균형 이진 트리의 예입니다.

5. 이진 트리 퇴화

모든 내부 노드에 하나의 자식만 있는 경우 이진 트리를 퇴화 이진 트리 또는 병적 이진 트리라고 합니다. 이러한 트리는 성능 면에서 연결 목록과 유사합니다. 다음은 퇴화 이진 트리의 예입니다.

이진 트리의 이점

• 이진 트리의 검색 작업은 다른 트리에 비해 빠릅니다.
• 요소를 정렬된 순서로 제공하려면 두 개의 순회만 충분합니다.
• 최대 및 최소 요소를 선택하기 쉽습니다.
• 그래프 순회는 이진 트리도 사용합니다.
• 이진 트리를 사용하여 다른 접미사 및 접두사 식 변환 가능

더 읽어보기: 기계 학습의 의사결정나무: 기능, 분류, 장단점

결론

이진 트리는 데이터 구조에서 가장 널리 사용되는 트리 중 하나입니다. 각 이진 트리 유형 에는 고유한 기능이 있습니다. 이러한 데이터 구조에는 응용 컴퓨터 과학의 특정 요구 사항이 있습니다. 이진 트리 유형에 대한 이 기사가 도움이 되었기를 바랍니다. upGrad는 데이터 과학, 기계 학습, 빅 데이터 등의 다양한 과정을 제공합니다.

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