What is exactly the definition of a complete binary tree?

In summary, a complete binary tree is a binary tree where all nodes on every level, except possibly the deepest, are filled and all nodes on the deepest level are as far left as possible. There is some ambiguity in the definition, with some sources also requiring every internal node to have exactly two children. However, it is generally agreed that a complete binary tree has a minimum of 2h and a maximum of 2h+1-1 nodes at height h. Ultimately, the definition used may depend on the specific problem or context.
  • #1
Eus
94
0
Hi Ho! ^_^

Actually, what is the definition of a complete binary tree?
I have searched the Internet and come up with several definition. This problem is confusing enough.

According to http://planetmath.org/encyclopedia/CompleteBinaryTree.html ,
"A complete binary tree is a binary tree with the additional property that every node must have exactly two children if an internal node, and zero children if a leaf node."

Moreover, in http://www.nist.gov/dads/HTML/completeBinaryTree.html,
"A binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible."

Furthermore, my lecture note says,
"A Complete Binary Tree is a Binary Tree with leaves on either a single level or on two adjacent levels such that the leaves on the bottommost level are placed as far left as possible"

Well, I don't know where I can find the right definition of a complete binary tree. Could you please help me?

Any help would be appreciated ^^
Thank you very much! ^^v
 
Last edited by a moderator:
Mathematics news on Phys.org
  • #2
I didn't know what a binary tree was until I saw this post, but I looked through some books on Amazon, and even they give (substantially) different definitions. I also checked several sites, and there is most agreement on:
1) All nodes of the deepest level being as far left as possible.
2) All levels except possibly the deepest being completely filled (having the maximum number of nodes).
What isn't clear is whether every internal node must have exactly two branches (or children).
Theorem. A complete binary tree of height h > 0 contains at least 2h and at most 2h+1 - 1 nodes.
-http://www.brpreiss.com/books/opus4/html/page355.html
I found this theorem elsewhere. Of course, I also found a problem:
Prove the following statement using mathematical induction: A complete binary tree of height h has 2^{h+1} - 1 nodes.
-source
I also found this elsewhere. The point of finding them was that 1) if every internal node must have exactly two branches, then the total number of nodes would always be odd (perhaps with the empty node or node that's just the root as exceptions). So if the total number of nodes can be even, then the internal nodes (on the second deepest level) don't need to have exactly two branches. 2) To show why I think the "right" definition is whichever definition you use. 3) Eh, it was interesting to learn about.
Maybe there's more consensus then there seems to be and someone who knows the subject better can let you know what it is. But if no one else replies, I would go with the definition that best suits your problem or try to find out from your book, problem, or teacher if you're expected to use a certain definition. Good luck.
 
  • #3
a complete binary tree is complete on all levels except maybe the last in which case the nodes must be to the left...always go to mathworld.com to check for definitions. That is to say that its filled up on everylevel.
NOTE in mathematics that is the worst definition possible but in lamens its teh easiest explanation to understand

x
x x
x x x x
x x x x

the last 2 definitions imply this though through strange wording
The Lecture Notes: what its saying is that the leaves can be on the 2nd lowest level
but all the leaves on the bottom must be towards the left as the diagram above.
Really weird wording
the Nist def'n" is basically waht I said with math terms.

The Planet def'n i belivee is wrong
 
  • #4
If you go to the NIST website and look up "full binary tree" you'll get the definition given by PlanteMath for "complete binary tree." As far as I know, there is indeed some ambiguity here. It is possible to see in texts "full" and "complete" using the definition that is given to the other term by NIST. It is also possible to see a source defining "complete" as NIST defines "full" (as in the previous case) but does not define "full" at all (not as in the previous case), as does PlanetMath.
 
  • #5
Thank you very much for the information, guys! ^_^

Hi Ho! ^_^

Thank you very much for your precious information, guys! ^_^
I really appreciate them! ^^v

See you later, guys! ^_^
 

Related to What is exactly the definition of a complete binary tree?

1. What is a complete binary tree?

A complete binary tree is a type of binary tree data structure in which every level, except possibly the last, is completely filled with nodes. The last level is filled from left to right.

2. How is a complete binary tree different from a regular binary tree?

A complete binary tree differs from a regular binary tree in that the latter does not necessarily have to be completely filled at every level. In a regular binary tree, the nodes can be arranged in any order, while in a complete binary tree, the nodes are arranged from left to right.

3. What are the properties of a complete binary tree?

The properties of a complete binary tree include:

  • Every level, except possibly the last, is completely filled
  • The last level is filled from left to right
  • All nodes have either 0 or 2 children
  • If a node has a left child, it must also have a right child
  • The height of a complete binary tree is log(n), where n is the number of nodes in the tree

4. How is a complete binary tree useful in computer science?

A complete binary tree is useful in computer science because it allows for efficient storage and retrieval of data. It is a balanced data structure, meaning that the height of the tree is minimized, making operations such as searching and sorting more efficient.

5. Can a binary tree be both complete and balanced?

Yes, a binary tree can be both complete and balanced. A complete binary tree is always balanced, but a balanced binary tree is not necessarily complete. A balanced binary tree has the property that the height of the left and right subtrees of any node differ by at most one.

Similar threads

Replies
4
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Programming and Computer Science
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Programming and Computer Science
Replies
13
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
3K
  • Programming and Computer Science
Replies
9
Views
2K
Back
Top