BINARY TREE

You are not Member of this Project.
Project Owner : Shyam.C
Created Date : Wed, 14/03/2012 - 22:45
Project Description :

 

In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as "left" and "right". Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child.

Binary trees are used to implement binary search trees and binary heaps.

 

 

Definitions for rooted trees

  • 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.
  • 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 depth (or height) of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a depth of zero.
  • Siblings are nodes that share the same parent node.
  • A node p is an ancestor of a node q if it exists on the path from the root to node q. The node q is then termed as 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.
  • The root is the only node in the tree with In-degree = 0.
  • All the leaf nodes have Out-degree = 0.

 

Types of binary trees

  • rooted binary tree is a tree with a root node in which every node has at most two children.
  • full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children. Sometimes a full tree is ambiguously defined as a perfect tree.
  • perfect binary tree is a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children.[1] (This is ambiguously also called acomplete binary tree.)
  • complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.[2]
  • An infinite complete binary tree is a tree with a countably infinite number of levels, in which every node has two children, so that there are 2d nodes at level d. The set of all nodes is countably infinite, but the set of all infinite paths from the root is uncountable: it has the cardinality of the continuum. These paths corresponding by an order preserving bijection to the points of the Cantor set, or (through the example of the Stern–Brocot tree) to the set of positive irrational numbers.
  • balanced binary tree is commonly defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1,[3] although in general it is a binary tree where no leaf is much farther away from the root than any other leaf. (Different balancing schemes allow different definitions of "much farther"[4]). Binary trees that are balanced according to this definition 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).
  • rooted complete binary tree can be identified with a free magma.
  • 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.

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

 

 

Properties of binary trees

  • 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 depth of the tree.
  • The number of nodes n in a complete binary tree is at least n = 2^{h} and at most n = 2^{h+1}-1 where h is the depth of the tree.
  • The number of leaf nodes L in a perfect binary tree can be found using this formula: L = 2^h where h is the depth of the tree.
  • The number of nodes n in a perfect binary tree can also be found using this formula: n = 2L-1 where L is the number of leaf nodes in the tree.
  • The number of null links (absent children of nodes) in a complete binary tree of n nodes is (n+1).
  • The number nL of internal nodes (non-leaf nodes) in a Complete Binary Tree of n nodes is ⌊n/2⌋.
  • For any non-empty binary tree with n0 leaf nodes and n2 nodes of degree 2, n0 = n2 + 1.[5]
Proof:
Let n = the total number of nodes
B = number of branches
n0n1n2 represent the number of nodes with no children, a single child, and two children respectively.
B = n - 1 (since all nodes except the root node come from a single branch)
B = n1 + 2*n2
n = n1+ 2*n2 + 1
n = n0 + n1 + n2
n1+ 2*n2 + 1 = n0 + n1 + n2 ==> n0 = n2 + 1

Definition in graph theory

For each binary tree data structure, there is equivalent rooted binary tree 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 three. It can be shown that in any binary tree of two or more nodes, 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 two 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 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:

This also does not establish the order of children, but does fix a specific root node.

 

 

Methods for storing binary trees

Binary trees can be constructed from programming language primitives in several ways.

 

Encoding general 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. To convert a general ordered tree to binary tree, we only need to represent the general tree in left child-sibling way. The result of this representation will be automatically binary tree, if viewed from a different perspective. 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 left child-right sibling binary tree (LCRS 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.

An example of converting an n-ary tree to a binary tree

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.

 

You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.