FACTOID # 24: Looking for table makers? Head to Mississippi, with an overwhlemingly large number of employees in furniture manufacturing.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Binary tree

In computer science, a binary tree (sometimes known as a dual-limbed arborgraph) 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. B-trees are tree data structures that are most commonly found in databases and filesystem implementations. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... A simple example unordered tree In computer science, a tree is a widely-used data structure that emulates a tree structure with a set of linked nodes. ... A child node or descendant node is a node in a tree data structure that is linked to by a parent node. ... A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13 In computer science, a binary search tree (BST) is a binary tree data structure which has the following properties: each node (item in the tree) has a value; a total... Example of a complete binary max heap. ...

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

Contents

Image File history File links Binary_tree. ... Image File history File links Binary_tree. ...

Definitions for rooted trees

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

A parent node (or ancestor node) is a node in a tree data structure that links to one or more child nodes. ... A child node or descendant node is a node in a tree data structure that is linked to by a parent node. ... A root node is a specially chosen node in a tree data structure at which all operations on the tree begin. ... A node is a basic unit used to build data structures, such as linked lists and tree data structures. ... 9, 14, 19, 67 and 76 are leaf nodes. ... This article just presents the basic definitions. ...

Types of binary trees

  • 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.
  • 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 2d. 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 log2(n) where n is the number of nodes on the balanced tree. Example 1: balanced tree with 1 node, log2(1)=0 (depth = 0). Example 2: balanced tree with 3 nodes, log2(3)=1.59 (depth=1). Example 3: balanced tree with 5 nodes, log2(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 = 2h + 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 = 2h where h is the height of the tree.
  • The number of nodes n in a complete binary tree is minimum: n = 2h and maximum: n = 2h + 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". In computer science, a tree is a widely-used computer data structure that emulates a tree structure with a set of linked nodes. ... In abstract algebra, a magma (also called a groupoid) is a particularly basic kind of algebraic structure. ...


Definition in graph theory

Graph theorists use the following definition: A binary tree is a connected acyclic graph such that the degree of each 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. A drawing of a graph. ... In mathematics and computer science, graph theory studies the properties of graphs. ... In mathematics and computer science, graph theory studies the properties of graphs. ... This article just presents the basic definitions. ...


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. In an undirected graph, a connected component or component is a maximal connected subgraph. ...


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. In the theory of formal languages of computer science, mathematics, and linguistics, the Dyck language (Dyck being pronounced deek) is the language consisting of those balanced strings of parentheses [ and ]. It is important in the parsing of expressions that must have a correctly nested sequence of parentheses, such as arithmetic...


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 Cn. For example, C2 = 2 declares that (a 0) and (0 a) are the only binary trees possible that have two nodes, and C3 = 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. In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. ...


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. In abstract algebra, a magma (also called a groupoid) is a particularly basic kind of algebraic structure. ... In abstract algebra, a magma (also called a groupoid) is a particularly basic kind of algebraic structure. ...


Given a string representing a binary tree, the operators to obtain the left and right subtrees are sometimes referred to as car and cdr. Introduced in the Lisp programming language, car (IPA [kar], just like the English word car) and cdr (IPA [kʌ dər] or [ku dər]) are primitive operations upon linked lists composed of cons cells. ...


Methods for storing binary trees

Binary trees can be constructed from programming language primitives in several ways. In a language with records and references, 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. A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ... This article is about the data structure. ... This article is about a general notion of reference in computing. ... A sentinel in computer science refers to a special type of object that represents the end of a data structure. ...


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 and 2i + 2, 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 2h - n for a tree of height h with n nodes. Implicit data structure is a data structure that uses very little memory besides the actual data elements. ... For the DNA microarray in life sciences, see DNA microarray. ... It has been suggested that this article or section be merged with Memory locality. ...

A small complete binary tree stored in an array

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, 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. Image File history File links Binary_tree_in_array. ... In computer science, a tagged union, also called a variant, variant record, discriminated union, or disjoint union, is a data structure used to hold a value that could take on several different, but fixed types. ... ML is a general-purpose functional programming language developed by Robin Milner and others in the late 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM. Historically, ML stands for metalanguage as it was conceived to develop proof tactics in the LCF theorem prover (the language of...


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 article: 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 trees, where this traversal visits the nodes in increasing order. In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. ... A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13 In computer science, a binary search tree (BST) is a binary tree data structure which has the following properties: each node (item in the tree) has a value; a total...


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. Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...


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. In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. ...


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 theoretical lower bounds. The number of different binary trees on n nodes is Cn, the nth Catalan number (assuming we view trees with identical structure as identical). For large n, this is about 4n; thus we need at least about log24n = 2n bits to encode it. A succinct binary tree therefore would occupy only 2 bits per node. In computer science, a succinct data structure for a given data type is a representation of the underlying combinatorial object that uses an amount of space “close” to the information theoretic lower bound together with algorithms that supports navigation and search operations on the data type “quickly”. A natural example... Not to be confused with information technology, information science, or informatics. ... In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. ...


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. [1] 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 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 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. Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...


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. In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ...


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.

An example of converting an n-ary tree to a binary tree An example of n-ary to binary tree conversion, made by Derrick Coetzee in Illustrator for the article binary tree, based strongly on the ASCII diagram previously in that article. ...

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

In computer science, an (a,b) tree is a specific kind of search tree. ... A kind of B-tree that can contain only 2-nodes (a node with 1 element and 2 children) and 3-nodes (a node with 2 elements and 3 children). ... A 2-3-4 tree in computer science is a B-tree of order 4. ... In computer science, AA trees are a form of balanced trees used for storing and retrieving ordered data efficiently. ... An example of an unbalanced non-AVL tree In computer science, an AVL tree is a self-balancing binary search tree, and the first such data structure to be invented. ... B-trees are tree data structures that are most commonly found in databases and filesystem implementations. ... In computer science, a binary search tree (BST) is a binary tree where every node has a value, every nodes left subtree has values less than or equal to the nodes value, and every right subtree has values greater. ... Binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. ... A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. ... A threaded binary tree may be defined as follows: A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the... This article needs to be cleaned up to conform to a higher standard of quality. ... A common method of simplification is to divide a problem into subproblems of the same type. ...

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

Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ...

External links


  Results from FactBites:
 
PlanetMath: binary tree (341 words)
A balanced binary tree is a binary tree that is also a balanced tree.
The two (potential) children of a node in a binary tree are often called the left and right children of that node.
This is version 4 of binary tree, born on 2002-02-25, modified 2004-05-20.
Topic #9: Binary search trees (2726 words)
A tree is defined as a nonempty finite set of labeled nodes such that there is only one node called the root of the tree, and the remaining nodes are partitioned into subtrees.
Consider a binary tree with p as the element to be deleted.
Note that one of the advantages of using this operation is that the only part of the tree to be affected by the operation is the subtree of p (the shaded triangle), which consists of all the nodes inserted after p, falling between the two ropes of p.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m