Types of Binary Trees
- A rooted binary tree is a tree with a root node in which every node has at most two children.
- A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children. Or, perhaps more clearly, every node in a binary tree has exactly 0 or 2 children. Sometimes a full tree is ambiguously defined as a perfect tree.
- A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children. (This is ambiguously also called a complete binary tree.)
- A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
- An infinite complete binary tree is a tree with a countably infinite number of levels, in which every node has two children, so that there are 2d nodes at level d. The set of all nodes is countably infinite, but the set of all infinite paths from the root is uncountable: it has the cardinality of the continuum. These paths corresponding by an order preserving bijection to the points of the Cantor set, or (through the example of the Stern–Brocot tree) to the set of positive irrational numbers.
- A balanced binary tree is commonly defined as a binary tree in which the depth of the two subtrees of every node differ by 1 or less, although in general it is a binary tree where no leaf is much farther away from the root than any other leaf. (Different balancing schemes allow different definitions of "much farther".) Binary trees that are balanced according to this definition have a predictable depth (how many nodes are traversed from the root to a leaf, root counting as node 0 and subsequent as 1, 2, ..., depth). This depth is equal to the integer part of where is the number of nodes on the balanced tree. Example 1: balanced tree with 1 node, (depth = 0). Example 2: balanced tree with 3 nodes, (depth=1). Example 3: balanced tree with 5 nodes, (depth of tree is 2 nodes).
- A degenerate tree is a tree where for each parent node, there is only one associated child node. This means that in a performance measurement, the tree will behave like a linked list data structure.
Note that this terminology often varies in the literature, especially with respect to the meaning of "complete" and "full".
Read more about this topic: Binary Tree
Famous quotes containing the words types of, types and/or trees:
“Science is intimately integrated with the whole social structure and cultural tradition. They mutually support one other—only in certain types of society can science flourish, and conversely without a continuous and healthy development and application of science such a society cannot function properly.”
—Talcott Parsons (1902–1979)
“Our children evaluate themselves based on the opinions we have of them. When we use harsh words, biting comments, and a sarcastic tone of voice, we plant the seeds of self-doubt in their developing minds.... Children who receive a steady diet of these types of messages end up feeling powerless, inadequate, and unimportant. They start to believe that they are bad, and that they can never do enough.”
—Stephanie Martson (20th century)
“Sometimes we see a cloud that’s dragonish,
A vapor sometimes like a bear or lion,
A towered citadel, a pendant rock,
A forked mountain, or blue promontory
With trees upon ‘t that nod unto the world
And mock our eyes with air. Thou hast seen these signs;
They are black vesper’s pageants.”
—William Shakespeare (1564–1616)