Binary tree
≈ 12 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. That is, it is a k-ary tree where . A recursive definition using set theory is that a binary tree is a triple , where L and R are binary trees or the empty set and S is a singleton (a single–element set) containing the root.
From a graph theory perspective, binary trees as defined here are arborescences. A binary tree may thus be also called a bifurcating arborescence, a term which appears in some early programming books before the modern computer science terminology prevailed.
It is also possible to interpret a binary tree as an undirected, rather than directed graph, in which case a binary tree is an ordered, rooted tree. Some authors use rooted binary tree instead of binary tree to emphasize the fact that the tree is rooted, but as defined above, a binary tree is always rooted.
In mathematics, what is termed binary tree can vary significantly from author to author. Some use the definition commonly used in computer science, but others define it as every non-leaf having exactly two children and don't necessarily label the children as left and right either.
In computing, binary trees can be used in two very different ways: * First, as a means of accessing nodes based on some value or label associated with each node.…
In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. That is, it is a k-ary tree where . A recursive definition using set theory is that a binary tree is a triple , where L and R are binary trees or the empty set and S is a singleton (a single–element set) containing the root.
From a graph theory perspective, binary trees as defined here are arborescences. A binary tree may thus be also called a bifurcating arborescence, a term which appears in some early programming books before the modern computer science terminology prevailed.
It is also possible to interpret a binary tree as an undirected, rather than directed graph, in which case a binary tree is an ordered, rooted tree. Some authors use rooted binary tree instead of binary tree to emphasize the fact that the tree is rooted, but as defined above, a binary tree is always rooted.
In mathematics, what is termed binary tree can vary significantly from author to author. Some use the definition commonly used in computer science, but others define it as every non-leaf having exactly two children and don't necessarily label the children as left and right either.
In computing, binary trees can be used in two very different ways: First, as a means of accessing nodes based on some value or label associated with each node. Binary trees labelled this way are used to implement binary search trees and binary heaps, and are used for efficient searching and sorting.
The designation of non-root nodes as left or right child even when there is only one child present matters in some of these applications, in particular, it is significant in binary search trees. However, the arrangement of particular nodes into the tree is not part of the conceptual information.
For example, in a normal binary search tree the placement of nodes depends almost entirely on the order in which they were added, and can be re-arranged (for example by balancing) without changing the meaning. Second, as a representation of data with a relevant bifurcating structure.
In such cases, the particular arrangement of nodes under and/or to the left or right of other nodes is part of the information (that is, changing it would change the meaning). Common examples occur with Huffman coding and cladograms. The everyday division of documents into chapters, sections, paragraphs, and so on is an analogous example with n-ary rather than binary trees.
The number of nodes in a full binary tree is at least 2h+1 and at most 2^{h+1}-1 (i.e., the number of nodes in a perfect binary tree), where is the height of the tree. A tree consisting of only a root node has a height of 0. The least number of nodes is obtained by adding only two children nodes per adding height so 2h+1 (1 for counting the root node).
The maximum number of nodes is obtained by fully filling nodes at each level, i.e., it is a perfect tree. For a perfect tree, the number of nodes is 1 + 2 + 4 + \ldots + 2^h = 2^{h + 1} - 1 , where the last equality is from the geometric series sum.
The number of leaf nodes in a perfect binary tree is l = (n + 1) / 2 (where is the number of nodes in the tree) because n={{2}^{h+1}}-1 (by using the above property) and the number of leaves is 2^h so n=2\cdot {{2}^{h}}-1=2l-1\to l=\left( n+1 \right)/2 . It also means that n = 2l - 1 .
In terms of the tree height , l = (2^{h+1}-1 + 1) / 2 = 2^h . For any non-empty binary tree with l leaf nodes and i_2 nodes of degree 2 (internal nodes with two child nodes), l = i_2 + 1 . The proof is the following.
For a perfect binary tree, the total number of nodes is n = 2^{h+1}-1 (a perfect binary tree is also a full binary tree) and l = 2^h , so i = n - l = (2^{h+1}-1) - 2^h = 2^h - 1 = l - 1 \to l = i + 1 . To make a full binary tree from a perfect binary tree, a pair of two sibling nodes are removed one by one.
This results in "two leaf nodes removed" and "one internal node removed" and "the removed internal node becoming a leaf node", so one leaf node and one internal node is removed per removing two sibling nodes. As a result, l = i + 1 also holds for a full binary tree.
To make a binary tree with a leaf node without its sibling, a single leaf node is removed from a full binary tree, then "one leaf node removed" and "one internal nodes with two children removed" so l = i + 1 also holds. This relation now covers all non-empty binary trees.
With given nodes, the minimum possible tree height is h_{\min} = \log_2 (n+1)-1 with which the tree is a balanced full tree or perfect tree. With a given height , the number of nodes can't exceed the 2^{h+1}-1 as the number of nodes in a perfect tree. Thus n \leq 2^{h + 1} - 1 \to h \geq \log _2 (n + 1) - 1 .
A binary tree with leaves has at least the height h_m = \log_2 (l) . With a given height , the number of leaves at that height can't exceed 2^h as the number of leaves at the height in a perfect tree. Thus l \leq 2^h \to h \geq \log_2 (l) . In a non-empty binary tree, if is the total number of nodes and is the total number of edges, then e = n - 1 .
This is obvious because each node requires one edge except for the root node. The number of null links (i.e., absent children of the nodes) in a binary tree of nodes is . The number of internal nodes in a complete binary tree of nodes is \lfloor n/2\rfloor .
((X*X)*X)*X,\qquad (X*(X*X))*X,\qquad (X*X)*(X*X),\qquad X*((X*X)*X),\qquad X*(X*(X*X)). The correspondence to binary trees should be obvious, and the addition of redundant parentheses (around an already parenthesized expression or around the full expression) is disallowed (or at least not counted as producing a new possibility). There is a unique binary tree of size 0 (consisting of a single leaf), and any other binary tree is characterized by the pair of its left and right children; if these have sizes i and j respectively, the full tree has size .
Therefore, the number C_n of binary trees of size n has the following recursive description C_0=1 , and \textstyle C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i} for any positive integer n. It follows that C_n is the Catalan number of index n. The above parenthesized strings should not be confused with the set of words of length 2n in the Dyck language, which consist only of parentheses in such a way that they are properly balanced. The number of such strings satisfies the same recursive description (each Dyck word of length 2n is determined by the Dyck subword enclosed by the initial '(' and its matching ')' together with the Dyck subword remaining after that closing parenthesis, whose lengths 2i and 2j satisfy ); this number is therefore also the Catalan number C_n . So there are also five Dyck words of length 6: These Dyck words do not correspond to binary trees in the same way.
Instead, they are related by the following recursively defined bijection: the Dyck word equal to the empty string corresponds to the binary tree of size 0 with only one leaf. Any other Dyck word can be written as ( w_1 ) w_2 , where w_1 , w_2 are themselves (possibly empty) Dyck words and where the two written parentheses are matched.
The bijection is then defined by letting the words w_1 and w_2 correspond to the binary trees that are the left and right children of the root. A bijective correspondence can also be defined as follows: enclose the Dyck word in an extra pair of parentheses, so that the result can be interpreted as a Lisp list expression (with the empty list () as only occurring atom); then the dotted-pair expression for that proper list is a fully parenthesized expression (with NIL as symbol and '.' as operator) describing the corresponding binary tree (which is, in fact, the internal representation of the proper list).
The ability to represent binary trees as strings of symbols and parentheses implies that binary trees can represent the elements of a free magma on a singleton set. type chr_tree = Empty | Node of char * chr_tree * chr_tree A succinct data structure is one which occupies close to minimum possible space, as established by information theoretical lower bounds. The number of different binary trees on n nodes is \mathrm{C}_{n} , the n th Catalan number (assuming we view trees with identical structure as identical).
For large n , this is about 4^{n} ; thus we need at least about \log_{2}4^{n} = 2n bits to encode it. A succinct binary tree therefore would occupy bits (with 'o()' being the Little-o notation). One simple representation which meets this bound is to visit the nodes of the tree in preorder, outputting "1" for an internal node and "0" for a leaf.
If the tree contains data, we can simply simultaneously store it in a consecutive array in preorder. This function accomplishes this: function EncodeSuccinct(node n, bitstring structure, array data) { if n = nil then append 0 to structure; else append 1 to structure; append n.data to data; EncodeSuccinct(n.left, structure, data); EncodeSuccinct(n.right, structure, data); } The string structure has only 2n + 1 bits in the end, where n is the number of (internal) nodes; we don't even have to store its length.
To show that no information is lost, we can convert the output back to the original tree like this: function DecodeSuccinct(bitstring structure, array data) { remove first bit of structure and put it in b if b = 1 then create a new node n remove first element of data and put it in n.data n.left = DecodeSuccinct(structure, data) n.right = DecodeSuccinct(structure, data) return n else return nil } More sophisticated succinct representations allow not only compact storage of trees but even useful operations on those trees directly while they're still in their succinct form. In a complete binary tree, a node's breadth-index (i − (2 d − 1)) can be used as traversal instructions from the root.
Reading bitwise from left to right, starting at bit d − 1, where d is the node's distance from the root (d = ⌊log (i+1)⌋) and the node in question is not the root itself (d > 0). When the breadth-index is masked at bit d − 1, the bit values and mean to step either left or right, respectively.
The process continues by successively checking the next bit to the right until there are no more. The rightmost bit indicates the final traversal from the desired node's parent to the node itself. There is a time-space trade-off between iterating a complete binary tree this way versus each node having pointer(s) to its sibling(s).
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378025742 under CC BY-SA 4.0; modifications have been made.