Binary tree 4321 224884563 2008-07-10T20:59:56Z AnotherPerson 2 7154352 updated _sentinel_ link to point to article _Sentinel node_ instead of _Sentinel (computer science)_ which redirects there {{distinguish|B-tree}} In [[computer science]], a '''binary tree''' (sometimes known as a '''dual-limbed arborgraph''') is a [[Tree (data structure)|tree data structure]] in which each node has at most two [[child node|children]]. Typically the child nodes are called ''left'' and ''right''. Binary trees are commonly used to implement [[binary search tree]]s and [[binary heap]]s. [[Image:binary tree.svg|right|192|thumb|A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is neither a sorted nor a balanced binary tree]] ==Definitions for rooted trees== * A '''directed edge''' refers to the link from the [[Parent node|parent]] to the [[Child node|child]] (the arrows in the picture of the tree). * The [[root node]] of a tree is the [[node (computer science)|node]] with no parents. There is at most one root node in a rooted tree. * A [[leaf node]] has no children. * The '''depth''' of a node n is the length of the path from the root to the node. The set of all nodes at a given depth is sometimes called a '''level''' of the tree. The root node is at depth zero. * The '''height''' of a tree is the depth of its furthest leaf. A tree with only a root node has a height of zero. * '''Siblings''' are nodes that share the same parent node. * If a path exists from node p to node q, where node p is closer to the root node than q, then p is an '''ancestor''' of q and q is a '''descendant''' of p. * The '''size''' of a node is the number of descendants it has including itself. *'''In-degree''' of a [[Vertex (graph theory)]] is the number of edges arriving at that vertex. * '''Out-degree''' of a vertex is the number of edges leaving that vertex. *Root is the only node in the tree with in-Degree=0. ==Types of binary trees== * A '''rooted binary tree''' is a '''rooted''' [[Tree data structure|tree]] in which every node has at most two children. * A '''full binary tree''' (sometimes '''proper binary tree''' or '''2-tree''') is a tree in which every node has zero or two children. * A '''perfect binary tree''' (sometimes '''complete binary tree''') is a ''full binary tree'' in which all ''leaves'' are at the same ''depth''. <!--"doubt please give correct perfect definition and example for full complete btree and also for height and depth--> * An '''infinite complete binary tree''' is a tree with <math>{\aleph_0}</math> levels, where for each level d the number of existing nodes at level d is equal to 2<sup>d</sup>. The cardinal number of the set of all nodes is <math>{\aleph_0}</math>. The cardinal number of the set of all paths is <math>2^{\aleph_0}</math>. * A '''balanced binary tree''' is where the depth of all the ''leaves'' differs by at most 1. Balanced trees 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 <math>log_2(n)</math> where <math>n</math> is the number of nodes on the balanced tree. Example 1: balanced tree with 1 node, <math>log_2(1) = 0</math> (depth = 0). Example 2: balanced tree with 3 nodes, <math>log_2(3)=1.59</math> (depth=1). Example 3: balanced tree with 5 nodes, <math>log_2(5)=2.32</math> (depth of tree is 2 nodes). * A '''rooted complete binary tree''' can be identified with a [[free magma]]. * An '''almost complete binary tree''' is a tree in which each node that has a right child also has a left child. Having a left child does not require a node to have a right child. Stated alternately, an ''almost complete binary tree'' is a tree where for a right child, there is always a left child, but for a left child there may not be a right child. * 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. * The number of nodes ''<math>n</math>'' in a perfect binary tree can be found using this formula: ''<math>n = 2^{h+1}-1</math>'' where ''<math>h</math>'' is the height of the tree. * The number of leaf nodes ''<math>n</math>'' in a perfect binary tree can be found using this formula: ''<math>n = 2^h</math>'' where ''<math>h</math>'' is the height of the tree. * The number of nodes ''<math>n</math>'' in a complete binary tree is minimum: ''<math>n = 2^h</math>'' and maximum: ''<math>n = 2^{h+1}-1</math>'' where ''<math>h</math>'' is the height of the tree. * The number of NULL links in a Complete Binary Tree of n-node is (n+1). * The number of leaf node in a Complete Binary Tree of n-node is <math>UpperBound(n/2)</math>. - Note that this terminology often varies in the literature, especially with respect to the meaning "complete" and "full". ==Definition in graph theory== [[Graph theory|Graph theorists]] use the following definition: A binary tree is a [[connected graph|connected]] [[acyclic graph]] such that the degree of each [[vertex (graph theory)|vertex]] is no more than 3. It can be shown that in any binary tree, there are exactly two more nodes of degree one than there are of degree three, but there can be any number of nodes of degree two. A '''rooted binary tree''' is such a graph that has one of its vertices of degree no more than 2 singled out as the root. With the root thus chosen, each vertex will have a uniquely defined parent, and up to two children; however, so far there is insufficient information to distinguish a left or right child. If we drop the connectedness requirement, allowing multiple [[connected component (graph theory)|connected components]] in the graph, we call such a structure a forest. Another way of defining binary trees is a recursive definition on directed graphs. A binary tree is either: * A single vertex. * A graph formed by taking two binary trees, adding a vertex, and adding an edge directed from the new vertex to the root of each binary tree. This also does not establish the order of children, but does fix a specific root node. ==Combinatorics== The groupings of pairs of nodes in a tree can be represented as pairs of letters, surrounded by parenthesis. Thus, ''(a b)'' denotes the binary tree whose left subtree is ''a'' and whose right subtree is ''b''. Strings of balanced pairs of parenthesis may therefore be used to denote binary trees in general. The set of all possible strings consisting entirely of balanced parentheses is known as the [[Dyck language]]. Given ''n'' nodes, the total number of ways in which these nodes can be arranged into a binary tree is given by the [[Catalan number]] <math>C_n</math>. For example, <math>C_2=2</math> declares that ''(a 0)'' and ''(0 a)'' are the only binary trees possible that have two nodes, and <math>C_3=5</math> declares that ''((a 0) 0)'', ''(0 a) 0)'', ''(0 (a 0))'', ''(0 (0 a))'', and ''(a b)'' are the only five binary trees possible that have 3 nodes. Here ''0'' represents a subtree that is not present. The ability to represent binary trees as strings of symbols and parentheses implies that binary trees can represent the elements of a [[magma (algebra)|magma]]. Conversely, the set of all possible binary trees, together with the natural operation of attaching trees to one-another, forms a magma, the [[free magma]]. Given a string representing a binary tree, the operators to obtain the left and right subtrees are sometimes referred to as [[car and cdr]]. == Methods for storing binary trees ==<!-- This section is linked from [[Ahnentafel]] --> Binary trees can be constructed from [[programming language]] primitives in several ways. In a language with [[record (computer science)|records]] and [[Reference (computer science)|reference]]s, 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 special [[Sentinel node|sentinel node]]. Binary trees can also be stored as an [[implicit data structure]] in [[array]]s, and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an index ''i'', its children are found at indices <math>2i + 1</math> and <math>2i +2</math>, while its parent (if any) is found at index ''<math>\left \lfloor \frac{i-1}{2} \right \rfloor</math>'' (assuming the root has index zero). This method benefits from more compact storage and better [[locality of reference]], particularly during a preorder traversal. However, it is expensive to grow and wastes space proportional to 2<sup>''h''</sup> - ''n'' for a tree of height ''h'' with ''n'' nodes. <center>[[Image:Binary tree in array.svg|300px|A small complete binary tree stored in an array]]</center> In languages with [[tagged union]]s such as [[ML programming language|ML]], a tree node is often a tagged union of two types of nodes, one of which is a 3-tuple, 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. == Methods of iterating over binary trees == Often, one wishes to visit each of the nodes in a tree and examine the value there. There are several common orders in which the nodes can be visited, and each has useful properties that are exploited in algorithms based on binary trees. === Pre-order, in-order, and post-order traversal. === {{Main|Tree traversal}} 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. If the root node is visited before its subtrees, this is preorder; if after, postorder; if between, in-order. In-order traversal is useful in [[binary search tree]]s, where this traversal visits the nodes in increasing order. === Depth-first order === In depth-first order, we always attempt to visit the node farthest from the root 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. See [[depth-first search]] for more information. === Breadth-first order === 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. See [[Breadth-first search]] for more information. === Level-order traversal === Traversal where levels are visited successively, starting with level 0 (the root node), and nodes are visited from left to right on each level. == Encodings == === Succinct encodings === A [[succinct data structure]] is one which takes the absolute minimum possible space, as established by [[information theory|information theoretical]] lower bounds. The number of different binary trees on <math>n</math> nodes is <math>\mathrm{C}_{n}</math>, the <math>n</math>th [[Catalan number]] (assuming we view trees with identical ''structure'' as identical). For large <math>n</math>, this is about <math>4^{n}</math>; thus we need at least about <math>\log_{2}4^{n} = 2n</math> bits to encode it. A succinct binary tree therefore would occupy only 2 bits per node. 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. [http://theory.csail.mit.edu/classes/6.897/spring03/scribe_notes/L12/lecture12.pdf] 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 <math>2n + 1</math> bits in the end, where <math>n</math> 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 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. === Encoding ''n''-ary trees as binary trees === There is a one-to-one mapping between general ordered trees and binary trees, which in particular is used by [[Lisp programming language|Lisp]] to represent general ordered trees as binary trees. Each node ''N'' in the ordered tree corresponds to a node ''N' '' in the binary tree; the ''left'' child of ''N' '' is the node corresponding to the first child of ''N'', and the ''right'' child of ''N' '' is the node corresponding to ''N'' 's next sibling --- that is, the next node in order among the children of the parent of ''N''. This binary tree representation of a general order tree, is sometimes also referred to as a [[First-Child/Next-Sibling]] binary tree, or a [[Doubly-Chained Tree]], or a [[Filial-Heir chain]]. One way of thinking about this is that each node's children are in a [[linked list]], chained together with their ''right'' fields, and the node only has a pointer to the beginning or head of this list, through its ''left'' field. For example, in the tree on the left, A has the 6 children {B,C,D,E,F,G}. It can be converted into the binary tree on the right. <center> [[Image:nary to binary tree conversion.png|An example of converting an n-ary tree to a binary tree]] </center> The binary tree can be thought of as the original tree tilted sideways, with the black left edges representing ''first child'' and the blue right edges representing ''next sibling''. The leaves of the tree on the left would be written in Lisp as: :(((M N) H I) C D ((O) (P)) F (L)) which would be implemented in memory as the binary tree on the right, without any letters on those nodes that have a left child ==See also== * [[(a,b) tree]] * [[2-3 tree]] * [[2-3-4 tree]] * [[AA tree]] * [[AVL tree]] * [[B-tree]] * [[Binary search trees]] * [[Binary space partitioning]] * [[Red-black tree]] * [[Threaded binary tree]] * [[Kraft's inequality]] * [[Recursion (computer science)]] == References == * [[Donald Knuth]]. ''The art of computer programming vol 1. Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, especially subsections 2.3.1&ndash;2.3.2 (pp.318&ndash;348). * [[Kenneth A Berman]], [[Jerome L Paul]]. ''Algorithms: Parallel, Sequential and Distributed''. Course Technology, 2005. ISBN 0-534-42057-5. Chapter 4. (pp.113&ndash;166). ==External links== [[Category:Binary trees|*]] [[bg:Двоично дърво]] [[cs:Binární strom]] [[de:Binärbaum]] [[es:Árbol binario]] [[fr:Arbre binaire]] [[ko:이진 트리]] [[id:Pohon biner]] [[is:Tvíundartré]] [[it:Albero binario]] [[he:עץ בינארי]] [[ja:二分木]] [[pl:Drzewo binarne]] [[pt:Árvore binária]] [[ro:Arbore binar]] [[ru:Двоичное дерево]] [[sk:Binárny strom]] [[sl:Dvojiško drevo]] [[sr:Бинарно стабло]] [[fi:Binääripuu]] [[sv:Binärträd]] [[uk:Бінарне дерево]] [[zh:二叉树]]