“완전한 바이너리 트리”,“엄격한 바이너리 트리”,“전체 바이너리 트리”의 차이점은 무엇입니까?
나는 아래 나무의 용어에 대해 혼란스럽고 나무를 연구하고 있는데이 나무들을 구별 할 수 없습니다.
a) 완전한 이진 트리
b) 엄격한 이진 트리
c) 전체 이진 트리
이 나무들을 구별 할 수 있도록 도와주세요. 데이터 구조에서 이러한 트리가 언제 어디서 사용됩니까?
완전한 이진 트리 (때로는 적절한 이진 트리 또는 2- 트리 또는 엄격하게 이진 트리)는 잎을 제외한 모든 노드에 두 개의 자식이있는 트리입니다.
따라서 자식이 하나 뿐인 노드가 없습니다. 엄격한 이진 트리와 동일하게 나타납니다.
다음은 google의 전체 / 엄격 바이너리 트리 이미지입니다.
완전한 이진 트리는 마지막 수준을 제외한 모든 수준이 완전히 채워지고 모든 노드가 가능한 한 왼쪽에있는 이진 트리입니다.
균형 잡힌 나무를 의미하는 것 같습니다.
다음은 완전한 이진 트리의 이미지입니다. Google의 전체 트리 부분은 보너스입니다.
완벽한 나무 :
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ / \ / \ / \
x x x x x x x x
완전한 나무 :
x
/ \
/ \
x x
/ \ / \
x x x x
/ \ /
x x x
엄격한 / 전체 트리 :
x
/ \
/ \
x x
/ \
x x
/ \
x x
STRICT와 FULL BINARY TREE에는 차이가 있습니다.
1) FULL BINARY TREE : 정확히 (2 ^ h) -1 요소를 포함하는 높이 h의 이진 트리를 전체 이진 트리 라고합니다 . (참조 : Pg 427, C ++의 데이터 구조, 알고리즘 및 응용 [University Press], Sartaj Sahni의 Second Edition).
또는 다른 말로
FULL BINARY TREE에서 각 노드에는 정확히 0 개 또는 2 개의 자식이 있으며 모든 리프 노드는 동일한 수준에 있습니다.
예를 들어 : 다음은 FULL BINARY TREE입니다.
18
/ \
15 30
/ \ / \
40 50 100 40
2) STRICT BINARY TREE : 각 노드에는 정확히 0 개 또는 2 개의 자식이 있습니다.
예 : 다음은 STRICT BINARY TREE입니다.
18
/ \
15 30
/ \
40 50
나는 Complete Binary Tree의 정의에 혼동이 없다고 생각하지만, 여전히 게시물의 완전성을 위해 Complete Binary Tree가 무엇인지 말하고 싶습니다.
3) 완전한 이진 트리 : 마지막 수준을 제외한 모든 수준이 완전히 채워지고 마지막 수준에 가능한 한 모든 키가 남아 있으면 이진 트리는 완전한 이진 트리입니다.
예 : 다음은 완전한 이진 트리입니다.
18
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
참고 : 다음은 완전한 이진 트리이기도합니다.
18
/ \
15 30
/ \ / \
40 50 100 40
면책 조항 -일부 정의의 주요 소스는 위키피디아이며 내 답변을 개선하기위한 제안을 환영합니다.
이 게시물에는 허용되는 답변이 있고 좋은 답변이지만 여전히 혼란 스러웠으며 이러한 용어의 차이점에 대해 더 많은 설명을 추가하고 싶습니다.
(1) FULL BINARY TREE- 풀 바이너리 트리는 잎을 제외한 모든 노드에 2 개의 자식이있는 바이너리 트리로, 엄격하게 바이너리 트리 라고도 합니다 .
위의 두 가지는 전체 또는 엄격 이진 트리의 예입니다.
(2) 완전한 이진 트리- 이제 완전한 이진 트리의 정의는 매우 모호합니다 .- 완전한 이진 트리는 마지막을 제외한 모든 레벨 이 완전히 채워지고 모든 노드가 다음과 같은 이진 트리입니다. 최대한 왼쪽으로. 마지막 레벨 h에서 가능한 한 가장 왼쪽에있는 1 ~ 2h 노드를 가질 수 있습니다.
기울임 꼴로 표시된 선을 확인하십시오.
모호성은 이탤릭체로 된 줄에 있습니다. "마지막 레벨을 제외하고"는 마지막 레벨도 완전히 채워질 수 있음을 의미합니다. 즉,이 예외가 항상 충족 될 필요는 없습니다. 예외가 유지되지 않으면 내가 게시 한 두 번째 이미지와 똑같으며 완벽한 이진 트리 라고도합니다 . 따라서 완벽한 이진 트리도 완전하고 완전하지만 그 반대는 아닙니다.
ALMOST COMPLETE BINARY TREE- 완전한 이진 트리 정의의 예외가 유지되면 거의 완전한 이진 트리 또는 거의 완전한 이진 트리라고합니다. 그것은 완전한 이진 트리의 한 유형일 뿐이지 만 더 명확하게 만들기 위해서는 별도의 정의가 필요합니다.
따라서 거의 완전한 이진 트리는 다음과 같이 보일 것입니다. 이미지에서 노드가 가능한 한 멀리 왼쪽에 있으므로 완전한 이진 트리의 하위 집합에 가깝습니다. 더 엄격하게 거의 모든 이진 트리는 완전한 이진 트리입니다. 나무이지만 그 반대는 아닙니다. :
위의 답변에서 결론을 내리면 완전 / 엄격, 완전 및 완벽한 바이너리 트리의 정확한 차이점은 다음과 같습니다.
Full / Strictly binary tree :-리프 노드를 제외한 모든 노드에는 두 개의 자식이 있습니다.
완전한 바이너리 트리 :-마지막 레벨을 제외한 모든 레벨이 완전히 채워지고 모든 노드가 정렬됩니다.
완벽한 이진 트리 :-리프 노드를 제외한 모든 노드에는 두 개의 자식이 있으며 모든 수준 (마지막 수준도)이 완전히 채워집니다.
노드가 트리 방식으로 그려진 이진 트리를 고려하십시오. 이제 노드 번호를 위에서 아래로, 왼쪽에서 오른쪽으로 시작합니다. 완전한 트리에는 다음과 같은 속성이 있습니다.
n에 자식이 있으면 n보다 작은 번호의 모든 노드에는 자식이 두 개 있습니다.
n에 자식이 하나 있으면 왼쪽 자식이어야하며 n 미만의 모든 노드에는 자식이 두 개 있어야합니다. 또한 n보다 큰 번호의 노드에는 자식이 없습니다.
n에 자식이 없으면 n보다 큰 번호의 노드에는 자식이 없습니다.
완전한 이진 트리를 사용하여 힙을 나타낼 수 있습니다. 간격없이 연속 메모리에서 쉽게 표현할 수 있습니다 (즉, 끝에 존재할 수있는 공간을 절약하기 위해 모든 배열 요소가 사용됨).
Full binary tree are a complete binary tree but reverse is not possible, and if the depth of the binary is n the no. of nodes in the full binary tree is ( 2^n-1 ). It is not necessary in the binary tree that it have two child but in the full binary it every node have no or two child.
To start with basics, it is very important to understand binary tree itself to understand different types of it.
A tree is a binary tree if and only if :-
– It has a root node , which may not have any child nodes (0 childnodes, NULL tree)
–Root node may have 1 or 2 child nodes . Each such node forms abinary tree itself
–Number of child nodes can be 0 ,1 ,2.......not more than 2
–There is a unique path from the root to every other node
Example :
X
/ \
X X
/ \
X X
Coming to your inquired terminologies:
A binary tree is a complete binary tree ( of height h , we take root node as 0 ) if and only if :-
Level 0 to h-1 represent a full binary tree of height h-1
– One or more nodes in level h-1 may have 0, or 1 child nodes
If j,k are nodes in level h-1, then j has more child nodes than k if and only if j is to the left of k , i.e. the last level (h) can be missing leaf nodes, however the ones present must be shifted to the left
Example :
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
A binary tree is a strictly binary tree if and only if :-
Each node has exactly two child nodes or no nodes
Example :
X
/ \
X X
/ \
X X
/ \ / \
X X X X
A binary tree is a full binary tree if and only if :-
Each non leaf node has exactly two child nodes
All leaf nodes are at the same level
Example :
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
/ \ / \ / \ / \ / \ / \ / \ / \
X X X X X X X X X X X X X X X X
You should also know what a perfect binary tree is?
A binary tree is a perfect binary tree if and only if :-
– is a full binary tree
– All leaf nodes are at the same level
Example :
X
/ \
/ \
/ \
X X
/ \ / \
X X X X
/ \ / \ / \ / \
X X X X X X X X
/ \ / \ / \ / \ / \ / \ / \ / \
X X X X X X X X X X X X X X X X
Well, I am sorry I cannot post images as I do not have 10 reputation. Hope this helps you and others!
In my limited experience with binary tree, I think:
- Strictly Binary Tree:Every node except the leaf nodes have two children or only have a root node.
- Full Binary Tree: A binary tree of H strictly(or exactly) containing 2^H -1 nodes , it's clear that which every level has the most nodes.
- Complete Binary Tree: It is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Let us consider a binary tree of height 'h'. A binary tree is called a complete binary tree if all the leaves are present at height 'h' or 'h-1' without any missing numbers in the sequence.
1
/ \
2 3
/ \
4 5
완전한 이진 트리입니다.
1
/ \
2 3
/ /
4 6
시퀀스에서 5 번 노드가 누락되어 완전한 이진 트리가 아닙니다.
'programing' 카테고리의 다른 글
| Java 8, Streams에서 중복 요소 찾기 (0) | 2020.11.06 |
|---|---|
| Chrome 48 이상에서 웹 보안 비활성화 (0) | 2020.11.06 |
| IntelliJ IDEA에서 라이브러리 (android-support-v7-appcompat)를 어떻게 추가합니까? (0) | 2020.11.06 |
| iOS7에서 탭시 UIButton이 강조 표시되지 않음 (0) | 2020.11.06 |
| github wiki 페이지에서 "spoiler"텍스트를 만드는 방법은 무엇입니까? (0) | 2020.11.06 |