데이터 구조에서 이진 트리의 5가지 유형 설명

이진 트리는 최대 2개의 자식이 있는 각 노드를 포함하는 비선형 트리 데이터 구조입니다. 이진 이름은 숫자 2를 암시하므로 모든 이진 트리는 왼쪽 및 오른쪽 자식을 가질 수 있습니다.

포인터는 일반적으로 트리의 루트로 알려진 최상위 노드에 대한 이진 트리를 나타냅니다. 이진 트리의 모든 노드에는 데이터, 왼쪽 자식에 대한 포인터 및 오른쪽 자식에 대한 포인터가 포함됩니다. 포인터는 이진 트리를 구현하는 데 사용됩니다. 루트 포인터는 트리의 첫 번째 노드를 나타냅니다. 이진 트리를 생성하려면 먼저 노드를 생성해야 합니다.

데이터 구조에서 이진 트리가 무엇인지 숙지한 후 이진 트리에서 수행되는 기본 작업도 알아야 합니다.요소 삽입, 요소 제거, 요소 검색, 이진 트리 순회와 같은 기능을 수행할 수 있습니다.

데이터 구조의 모든이진 트리는 컴퓨팅에서 두 가지 다른 방식으로 사용됩니다.첫째, 각 노드와 연결된 특정 레이블 또는 값에 따라 노드에 액세스하는 데 사용됩니다. 둘째, 관련 분기 구조가 있는 데이터 표현으로 사용됩니다.

다양한이진 트리 유형을 살펴보기 전에 먼저 이진 트리에서 사용되는 용어에 익숙해지도록 합시다 .

노드: 이진 트리에 데이터 값을 보유합니다.

루트: 이진 트리의 최상위 노드를 트리의 루트라고 합니다.

크기: 이진 트리의 노드 수를 나타냅니다.

부모 노드: 자식이 있는 이진 트리의 노드입니다.

자식 노드: 이진 트리의 루트에서 멀어지는 부모 노드에서 시작되는 노드입니다.

내부 노드: 이진 트리에서 자식이 하나 이상 있는 노드입니다.

리프 노드: 자식이 없는 노드입니다.또는 외부 노드입니다.

노드 트리의 깊이: 특정 노드의 컨텍스트에서 계산됩니다.특정 노드에서 루트까지의 에지 수라고 합니다.

트리의 내부 경로 길이: 이진 트리의 모든 내부 노드 수준의 합을 나타냅니다.

트리의 외부 경로 길이: 이진 트리의 모든 외부 노드 수준의 합으로 정의됩니다.

트리의 노드 높이: 특정 노드에서 이진 트리의 가장 깊은 리프 노드까지의 간선 수입니다.루트의 높이는 항상 이진 트리의 다른 노드보다 높습니다.

이제이진 트리의 5가지 유형에 대해 자세히 알아보겠습니다 .

이진 트리의 유형

1. 풀 이진 트리

데이터 구조의 이 이진 트리는 적절한 이진 트리 및 엄격한 이진 트리라는 이름으로도 알려져 있습니다.데이터 구조에서 가장 기본적인 이진 트리 유형 중 하나입니다 . 전체 이진 트리는 각 노드에 자식이 두 개 있거나 전혀 없는 이진 트리로 정의됩니다.

또는 리프 노드를 제외한 모든 노드가 두 개의 자식으로 구성되는 이진 트리로 특징지어집니다. 루트 노드의 주소가 저장된 노드를 루트의 자식 노드라고 합니다. 자식이 없는 노드를 리프 노드라고 합니다.

트리가 이진 트리인지 확인하려면 모든 노드를 이동해야 합니다. 노드에 자식이 하나 있으면 코드는 "False"를 반환합니다. 모든 노드에 자식이 0개 또는 2개 있으면 "True"를 반환합니다.

전체 이진 트리의 속성은 다음과 같습니다.

• 리프 노드의 수는 내부 노드의 수 + 1과 같습니다. 예를 들어 내부 노드의 수가 4인 경우 리프 노드의 수는 5입니다.
• 최대 노드 수와 이진 트리의 노드 수는 동일합니다. 2h+1 -1로 표시됩니다.
• 전체 이진 트리의 최소 노드 수는 2h-1입니다.
• 전체 이진 트리의 최소 높이는 log 2 (n+1) – 1입니다.
• 전체 이진 트리의 최대 높이는 h = (n+1)/2입니다.

2. 완벽한 이진 트리

완벽한 이진 트리는 모든 노드가 0 또는 2개의 자식을 가져야 하고 각 리프 노드의 수준이 동일해야 하는이진 트리 유형 중 하나입니다.즉,데이터 구조에서 완벽한 이진 트리는 모든 내부 노드가 두 개의 가지를 가지고 있고 가지가 없는 노드(리프 노드)가 동일한 수준에 존재하는 트리로 정의됩니다.

이 문맥에서 노드의 레벨은 루트 노드로부터의 거리 또는 높이입니다. 완벽한 이진 트리는 마지막 레벨도 완전히 점유된 완전한 이진 트리로 간주할 수 있습니다.

세계 최고의 대학에서 온라인으로데이터 과학 과정을배우십시오. PG 프로그램, 고급 인증 프로그램 또는 석사 프로그램을 취득하여 경력을 빠르게 쌓으십시오.

3. 완전한 이진 트리

완전한 이진 트리는 트리의 모든 수준이 완전히 채워진 데이터 구조의 이진 트리 유형 중 하나입니다.이진 트리의 마지막 수준은 완전히 채워질 수도 있고 채워지지 않을 수도 있습니다. 그러나 모든 노드는 노드의 마지막 레벨에서 가장 왼쪽 위치에 있어야 합니다. 노드는 왼쪽부터 포함되어야 합니다.

그들은 노드 수와 트리 높이 사이의 최상의 비율을 제공하기 때문에이진 트리의 필수 유형 중 하나입니다 .

완전한 이진 트리의 주요 속성은 다음과 같습니다.

• 최대 노드 수는 2h +1 – 1입니다.
• 최소 노드 수는 2 시간 입니다 .
• 최소 높이는 log 2 (n+1) – 1입니다.

4. 균형 이진 트리

균형 이진 트리에서 트리의 높이는 총 노드 수의 로그 2 입니다. 트리의 높이가 h이고 트리의 총 노드 수가 n이라고 가정합니다. 높이를 계산하는 방정식은 h = log(n)입니다. 오른쪽 하위 트리와 왼쪽 하위 트리의 최대 높이 차이는 "1"이어야 합니다.

차이는 0 및 -1과 같은 다른 값을 가질 수 있습니다. 이러한 유형의 이진 트리를 AVL 트리라고도 합니다.균형 이진 트리의 잘 알려진 예 중 하나는 Red-Black 트리입니다.

다음 코드를 구현하여 균형 이진 트리를 실행할 수 있습니다.

개인 클래스 노드 {

개인 정수 값;

개인 노드 왼쪽;

개인 노드 권리;

}

공개 부울 isBalanced(노드 n) {

if (balancedtreeHeight(n) > -1)

true를 반환합니다.

거짓을 반환합니다.

}

public int balancetreeHeight(노드 n) {

경우 (n == null)

0을 반환합니다.

int h1 = balancetreeHeight(n.right);

int h2 = balancetreeHeight(n.left);

if (h1 == -1 || h2 == -1)

-1 반환;

if (Math.abs(h1 – h2) > 1)

-1 반환;

만약 (h1 > h2)

반환 h1 + 1;

반환 h2 + 1;

}

US 확인 - 데이터 과학 프로그램

5. 이진 트리 퇴화

Degenerate 이진 트리는 덜 자주 사용되는이진 검색 트리 유형 중 하나입니다 .이것은 각 노드가 하나의 자식, 즉 왼쪽 또는 오른쪽 자식만 갖는 이진 트리입니다. 어떤 노드도 왼쪽과 오른쪽 자식을 모두 가질 수 없습니다.

인기 있는 US - 데이터 과학 기사 읽기

결론

다양한 응용 프로그램에 사용하려면데이터 구조에서 이진 트리가 무엇인지 이해하는 것이 필수적입니다 .이진 트리에서 다양한 기능을 구현하면 데이터를 효율적으로 구성하고 저장하는 데 도움이 될 수 있습니다.

여러 유형의 이진 트리를 연구하면 시간 복잡도에서 작업을 보다 효과적으로 수행하는 데 도움이 됩니다.이진 트리 데이터 구조를 포함한 데이터 과학 기초는 데이터 과학 여정을 쉽게 시작하는 데 도움이 됩니다.그 후 고급 데이터 과학 프로젝트에 참여하여 기술과 포트폴리오를 향상시킬 수 있습니다.

upGrad에서 기계 학습 여정 시작하기

데이터 과학을 배우고 싶다면 upGrad의 데이터 과학 석사 과정을 이수할 수 있습니다. 이 24개월 과정에서는 Python, ML 모델 배포, Spark를 사용한 BD 처리, 예측 분석 및 통계, 지도 및 비지도 ML 모델과 같은 기술을 배웁니다. 이 과정은 다양한 영역의 야심 찬 관리자, MBA 졸업생, 엔지니어 및 전문가에게 적합합니다.

이 과정을 마치면 데이터 엔지니어, 빅 데이터 분석가, 기계 학습 엔지니어 및 데이터 과학자로 일할 수 있습니다.