이진 트리에 n개의 가중치 리프 노드가 있다고 가정하면 루트 노드에서 각 리프 노드까지의 경로 길이의 합과 해당 노드 가중치의 곱을 이진 트리의 가중치 경로 길이 WPL(가중 경로 길이)이라고 합니다. .

동일한 리프 노드는 서로 다른 이진 트리를 구성합니다.

최소 가중치 경로 길이를 갖는 이진 트리를 허프만 트리(최적 트리라고도 함)라고 합니다.

원칙적으로

프로세스

허프만 코딩(접두사 코딩)

왼쪽<루트<오른쪽

이진 정렬 트리(특수 이진 정렬 트리)의 향상된 버전입니다. 트리를 최대한 짧게 유지하세요!

나무가 정상적으로 자라고 있는지 어떻게 알 수 있나요?

균형 인자 <= 1인 이진 정렬 트리

이진 트리의 최대 깊이와 최소 노드 수의 균형을 유지합니다.

끼워 넣다

프롤로그

중간 주문

후문

한 줄씩 탐색

필요하다

노드 수가 적은 질문의 경우

Prime 알고리즘의 핵심 단계는 다음과 같습니다. 가중치 연결 그래프에서 V는 모든 정점을 포함하는 집합입니다. U는 이미 그래프의 모든 정점 v에서 시작하는 최소 신장 트리의 노드입니다. ={v}, 다음 작업을 반복합니다. 모든 u∈U,w∈V-U의 모든 간선 (u,w)∈E 중에서 가중치가 가장 작은 간선을 찾고 간선 (u,w)를 집합에 추가합니다. 그리고 집합 U에 점 w를 추가합니다. U=V일 때 최소 스패닝 트리가 발견됩니다.

먼저 노드를 결정하고 가장 짧은 경로를 가진 노드를 순서대로 선택합니다.

변의 수가 적은 질문의 경우

기본 아이디어: 엣지 주도. 가중치 연결 그래프에서 U는 모든 간선의 집합이고, N은 정점의 수이며, SU는 이미 최소 스패닝 트리에 있는 간선의 집합입니다. 다음 작업을 반복합니다. 매번 가장 작은 가중치를 갖는 간선 e∈U-SU와 SU의 간선과 순환을 형성하지 않는 간선을 선택하여 SU에 추가합니다. SU의 간선 수가 N-1과 같을 때 최소 스패닝 트리가 발견됩니다.

오른쪽 포인터가 없는 노드의 수는 다음과 같습니다: 잎이 아닌 노드의 루트 노드 수

대칭적인 것을 제외하고 숫자를 세어 항상 왼쪽이 적고 오른쪽이 많거나 왼쪽이 많고 오른쪽이 적은지 확인하세요.

루트 노드는 고유합니다.

하위 트리의 수에는 제한이 없지만 서로 교차하지 않습니다.

자연

완전 이진 트리

완전 이진 트리

완전한 이진 트리여야 합니다.

다겐두이

작은 뿌리 더미

힙 저장

상부 필터

아래로 필터링

정렬되지 않은 배열을 힙으로 변환하는 방법은 무엇입니까?

두 가지 작업

작은 루트 힙을 사용하여 구현 가능

복잡도: O(NlogN)