Incomputer science, abinary tree is atree data structure in which each node has at most twochildren, referred to as theleft child and theright child. That is, it is ak-ary tree withk = 2. Arecursive definition usingset theory is that a binary tree is atuple (L,S,R), whereL andR are binary trees or theempty set andS is asingleton set containing the root.[1][2]
From agraph theory perspective, binary trees as defined here arearborescences.[3] A binary tree may thus be also called abifurcating arborescence,[3] a term which appears in some early programming books[4] before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as anundirected, rather thandirected graph, in which case a binary tree is anordered,rooted tree.[5] Some authors userooted binary tree instead ofbinary tree to emphasize the fact that the tree is rooted, but as defined above, a binary tree is always rooted.[6]
In mathematics, what is termedbinary tree can vary significantly from author to author. Some use the definition commonly used in computer science,[7] but others define it as every non-leaf having exactly two children and don't necessarily label the children as left and right either.[8]
In computing, binary trees can be used in two very different ways:
 | This articlemay need to be rewritten to comply with Wikipedia'squality standards, as section.You can help. Thetalk page may contain suggestions.(July 2014) |
To define a binary tree, the possibility that only one of the children may be empty must be acknowledged. Anartifact, which in some textbooks is called anextended binary tree, is needed for that purpose. An extended binary tree is thus recursively defined as:[11]
Another way of imagining this construction (and understanding the terminology) is to consider instead of the empty set a different type of node—for instance square nodes if the regular ones are circles.[12]
A binary tree is arooted tree that is also anordered tree (a.k.a. plane tree) in which every node has at most two children. A rooted tree naturally imparts a notion of levels (distance from the root); thus, for every node, a notion of children may be defined as the nodes connected to it a level below. Ordering of these children (e.g., by drawing them on a plane) makes it possible to distinguish a left child from a right child.[13] But this still does not distinguish between a node with left but not a right child from a node with right but no left child.
The necessary distinction can be made by first partitioning the edges; i.e., defining the binary tree as triplet (V, E1, E2), where (V, E1 ∪ E2) is a rooted tree (equivalently arborescence) and E1 ∩ E2 is empty, and also requiring that for allj ∈ { 1, 2 }, every node has at most one Ej child.[14] A more informal way of making the distinction is to say, quoting theEncyclopedia of Mathematics, that "every node has a left child, a right child, neither, or both" and to specify that these "are all different" binary trees.[7]
Tree terminology is not well-standardized and therefore may vary among examples in the available literature.
 | This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved.(July 2014) (Learn how and when to remove this message) |
Incombinatorics, one considers the problem of counting the number of full binary trees of a given size. Here the trees have no values attached to their nodes (this would just multiply the number of possible trees by an easily determined factor), and trees are distinguished only by their structure; however, the left and right child of any node are distinguished (if they are different trees, then interchanging them will produce a tree distinct from the original one). The size of the tree is taken to be the numbern of internal nodes (those with two children); the other nodes are leaf nodes and there aren + 1 of them. The number of such binary trees of sizen is equal to the number of ways of fully parenthesizing a string ofn + 1 symbols (representing leaves) separated byn binary operators (representing internal nodes), to determine the argument subexpressions of each operator. For instance forn = 3 one has to parenthesize a string like, which is possible in five ways:
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 sizesi andj respectively, the full tree has sizei +j + 1. Therefore, the number of binary trees of sizen has the following recursive description, and for any positive integern. It follows that is theCatalan number of indexn.
The above parenthesized strings should not be confused with the set of words of length 2n in theDyck 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 satisfyi +j + 1 =n); this number is therefore also the Catalan number. 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 (), where, are themselves (possibly empty) Dyck words and where the two written parentheses are matched. The bijection is then defined by letting the words and 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 aLisp list expression (with the empty list () as only occurring atom); then thedotted-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 afree magma on a singleton set.
Binary trees can be constructed fromprogramming language primitives in several ways.
In a language withrecords andreferences, binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child. Sometimes it also contains a reference to its unique parent. If a node has fewer than two children, some of the child pointers may be set to a special null value, or to a specialsentinel node.
This method of storing binary trees wastes a fair bit of memory, as the pointers will be null (or point to the sentinel) more than half the time; a more conservative representation alternative isthreaded binary tree.[26]
In languages withtagged unions such asML, a tree node is often a tagged union of two types of nodes, one of which is a 3-tuple of data, left child, and right child, and the other of which is a "leaf" node, which contains no data and functions much like the null value in a language with pointers. For example, the following line of code inOCaml (an ML dialect) defines a binary tree that stores a character in each node.[27]
typechr_tree=Empty|Nodeofchar*chr_tree*chr_tree
Binary trees can also be stored in breadth-first order as animplicit data structure inarrays, and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an indexi, its children are found at indices (for the left child) and (for the right), while its parent (if any) is found at index (assuming the root has index zero). Alternatively, with a 1-indexed array, the implementation is simplified with children found at and, and parent found at.[28]
This method benefits from more compact storage and betterlocality of reference, particularly during a preorder traversal. It is often used forbinary heaps.[29]
Asuccinct data structure is one which occupies close to minimum possible space, as established byinformation theoretical lower bounds. The number of different binary trees on nodes is, thethCatalan number (assuming we view trees with identicalstructure as identical). For large, this is about; thus we need at least about bits to encode it. A succinct binary tree therefore would occupy bits.
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.[30] 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 =nilthen 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 stringstructure has only bits in the end, where 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 ofstructure and put it inbif b = 1then create a new noden remove first element of data and put it in n.data n.left = DecodeSuccinct(structure, data) n.right = DecodeSuccinct(structure, data)return nelsereturn 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.
There is a natural one-to-one correspondence between ordered trees and binary trees. It allows any ordered tree to be uniquely represented as a binary tree, and vice versa:
LetT be a node of an ordered tree, and letB denoteT's image in the corresponding binary tree. ThenB'sleft child representsT's first child, while theB's right child representsT's next sibling.
For example, the ordered tree on the left and the binary tree on the right correspond:
In the pictured binary tree, the black, left, edges representfirst child, while the blue, right, edges representnext sibling.
This representation is called aleft-child right-sibling binary tree.
There are a variety of different operations that can be performed on binary trees. Some aremutator operations, while others simply return useful information about the tree.
Nodes can be inserted into binary trees in between two other nodes or added after aleaf node. In binary trees, a node that is inserted is specified as to whose child it will be.
To add a new node after leaf node A, A assigns the new node as one of its children and the new node assigns node A as its parent.
Insertion oninternal nodes is slightly more complex than on leaf nodes. Say that the internal node is node A and that node B is the child of A. (If the insertion is to insert a right child, then B is the right child of A, and similarly with a left child insertion.) A assigns its child to the new node and the new node assigns its parent to A. Then the new node assigns its child to B and B assigns its parent as the new node.
Deletion is the process whereby a node is removed from the tree. Only certain nodes in a binary tree can be removed unambiguously.[31]
Suppose that the node to delete is node A. If A has no children, deletion is accomplished by setting the child of A's parent tonull. If A has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.
In a binary tree, a node with two children cannot be deleted unambiguously.[31] However, in certain binary trees (includingbinary search trees) these nodescan be deleted, though with a rearrangement of the tree structure.
Pre-order, in-order, and post-order traversal visit each node in a tree by recursively visiting each node in the left and right subtrees of the root. Below are the brief descriptions of above mentioned traversals.
In pre-order, we always visit the current node; next, we recursively traverse the current node's left subtree, and then we recursively traverse the current node's right subtree. The pre-order traversal is atopologically sorted one, because a parent node is processed before any of its child nodes is done.
In in-order, we always recursively traverse the current node's left subtree; next, we visit the current node, and lastly, we recursively traverse the current node's right subtree.
In post-order, we always recursively traverse the current node's left subtree; next, we recursively traverse the current node's right subtree and then visit the current node. Post-order traversal can be useful to get postfix expression of abinary expression tree.[32]
In depth-first order, we always attempt to visit the node farthest from the root node that we can, but with the caveat that it must be a child of a node we have already visited. Unlike a depth-first search on graphs, there is no need to remember all the nodes we have visited, because a tree cannot contain cycles. Pre-order is a special case of this. Seedepth-first search for more information.
Contrasting with depth-first order is breadth-first order, which always attempts to visit the node closest to the root that it has not already visited. Seebreadth-first search for more information. Also called alevel-order traversal.
In a complete binary tree, a node's breadth-index (i − (2d − 1)) can be used as traversal instructions from the root. Reading bitwise from left to right, starting at bitd − 1, whered is the node's distance from the root (d = ⌊log2(i+1)⌋) and the node in question is not the root itself (d > 0). When the breadth-index is masked at bitd − 1, the bit values0 and1 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).
{{cite book}}: CS1 maint: multiple names: authors list (link){{cite book}}: CS1 maint: others (link)
Authority control databases: National |
|---|