Added to Favorites

Related Searches

Nearby Words

In computer science, a binary tree is a tree data structure in which each node has at most two children. Typically the child nodes are called left and right. Binary trees are commonly used to implement binary search trees and binary heaps.

- A directed edge refers to the link from the parent to the child (the arrows in the picture of the tree).
- The root node of a tree is the 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 node is the number of edges arriving at that node.
- Out-degree of a node is the number of edges leaving that node.
- Root is the only node in the tree with In-degree = 0

- A rooted binary tree is a rooted 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 or same Level.

- An infinite complete binary tree is a tree with $\{aleph\_0\}$ levels, where for each level d the number of existing nodes at level d is equal to 2
^{d}. The cardinal number of the set of all nodes is $\{aleph\_0\}$. The cardinal number of the set of all paths is $2^\{aleph\_0\}$. - 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 $log\_2(n)$ where $n$ is the number of nodes on the balanced tree. Example 1: balanced tree with 1 node, $log\_2(1)\; =\; 0$ (depth = 0). Example 2: balanced tree with 3 nodes, $log\_2(3)=1.59$ (depth=1). Example 3: balanced tree with 5 nodes, $log\_2(5)=2.32$ (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 $n$ in a perfect binary tree can be found using this formula: $n\; =\; 2^\{h+1\}-1$ where $h$ is the height of the tree.
- The number of leaf nodes $n$ in a perfect binary tree can be found using this formula: $n\; =\; 2^h$ where $h$ is the height of the tree.
- The number of nodes $n$ in a complete binary tree is minimum: $n\; =\; 2^h$ and maximum: $n\; =\; 2^\{h+1\}-1$ where $h$ 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 $UpperBound(n/2)$.

- Note that this terminology often varies in the literature, especially with respect to the meaning "complete" and "full".

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 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.

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 $C\_n$. For example, $C\_2=2$ declares that (a 0) and (0 a) are the only binary trees possible that have two nodes, and $C\_3=5$ 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. 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.

Binary trees can also be stored as an implicit data structure in arrays, 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 $2i\; +\; 1$(for the left child) and $2i\; +2$(for the right), while its parent (if any) is found at index $left\; lfloor\; frac\{i-1\}\{2\}\; right\; rfloor$ (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^{h} - n for a tree of height h with n nodes.

In languages with tagged unions such as ML, 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.

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 trees, where this traversal visits the nodes in increasing order.

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.

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.

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:

- (((N O) I J) C D ((P) (Q)) F (M))

which would be implemented in memory as the binary tree on the right, without any letters on those nodes that have a left child

- (a,b) tree
- 2-3 tree
- 2-3-4 tree
- AA tree
- AVL tree
- B-tree
- Binary search tree
- Binary space partitioning
- Red-black tree
- Threaded binary tree
- Kraft's inequality
- Recursion (computer science)

- 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–2.3.2 (pp.318–348).
- Kenneth A Berman, Jerome L Paul. Algorithms: Parallel, Sequential and Distributed. Course Technology, 2005. ISBN 0-534-42057-5. Chapter 4. (pp.113–166).

- flash actionscript 3 opensource implementation of binary tree — opensource library

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday October 09, 2008 at 13:30:48 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Thursday October 09, 2008 at 13:30:48 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.