# trees

## Binomial Trees

Binomial Trees are one of  the type of trees that are defined  recursively.A Binomial tree of order 0 is a single node and a binomial tree of order n has a root node whose children are roots of binomial trees of order n-1,n-2,n-3,n-4,……3,2,1,0.

### Properties of Binomial Tree

• There are 2n nodes in a binomial tree of order where n is the order and degree of tree(Fig 1).
• Deleting roots yield binomial trees Bn-1,Bn-2,….0.
• Bhas  nodes at depth d.

Fig 1 : Binomial Tree

### Binomial Tree of height/order(n)=0

When height =0 then single node will be present in Binomial tree(Fig 2).

Fig 2 : Binomial Tree of Order 0

### Binomial Tree at height (n)=1

When n=1 then 2=nodes will be present in the tree(Fig 3).

Fig 3 : Binomial Tree of order 1

### Binomial Tree of order=2

When n=2 then 2= 4 nodes will be present in the tree.The subtree is binomially  attached to the root node(Fig 4).

Fig 4 : Binomial Tree of order 2

### Binomial Tree of order 3

If order of tree is 3,then 23  nodes are present in the Binomial tree.The root is connected to subtrees of order 0(green color),1(red) and 2(black)  (Fig 5).

Fig 5 : Binomial Tree of order 3

### Bn  has   nodes at depth d.

If we have a binomial tree of order n,then we can trace the number of nodes at any depth by  .For e.g the no of nodes of binomial tree of order 4 at depth 2 will be 6.(Fig 6).In fig 7,number of nodes at level 2 is 6 and is shown by red highlighted area.

Fig 6 : Binomial Tree of order 4

Short URL: http://tinyit.cc/f8eed0
May 30, 2014 |
Tags:

## Deletion In B-Trees

In order to delete elements from B-Tree we need to ensure that their properties(Refer : http://letslearncs.com/b-trees/ does not get violated.It should remain a binary search tree and number of pointers must be according to the order and keys should be one less than the order in each and every node.

Example

Consider a B-tree of Fig 1.Say we want to delete 2,21,10,3 and 4 step by step from the tree.

Fig 1 : B-Tree

Delete 2

• 2 is present in node b.Deletion of 2 do not violate any property of B-tree,so we delete 2 directly from node b.(Fig 2)

Fig 2 : Delete 2

Delete 21

• Deletion of 21 cannot be done directly.It causes node e to underflow so elements are redistributed among c,g and e(Fig 3).
• 10 remains in c.
• 12 is stored in g and 13 is stored in e.

Fig 3 : Delete 21

Delete 10

• Deletion of 10 again cannot be done directly.It causes node c to underflow which further causes parent node g to combine with f and a and tree shrinks by one level.3,7 and 9 are stored in a,1 in b,4 and 5 in d,8 in h ,12 and 13 in e (Fig 4).

Fig 4 : Delete 10

Delete 3

• Deletion of 3 causes 4 to move in a (Fig 5).

Fig 5 : Delete 3

Delete 4

• Deletion of needs redistribution of the keys in the subtrees of 4; however, nodes b and d do not have enough keys to redistribute without causing an underflow. Thus, nodes b and d are combined together(Fig 6).

Fig 6 : Delete 4

Short URL: http://tinyit.cc/8bdf8c
|
Tags:

## B-Trees

The B-tree is a generalization of a binary search tree  in which a node can have more than two children .The B-tree is optimized for systems that read and write large blocks of data.It has following properties

• The data items are stored at leaves.
• Every node has between M/2 and M children where M is a positive integer greater than 1.
• M is the order as well as height of tree.
• The non leaf nodes store up to M-1 keys.
• The root is either a leaf or has between two and M children.
• All leaves are at the same depth and have between [L/2] and L children.

## Insertion in B-Tree

The insertion in b-tree is done such that they satisfy all the properties listed above.

Example

Consider a B-Tree of order 4 and we need to insert 5,3,21,9,1,13,2,7,10,12,4,8.Each node can have at most 4 pointers and 3 keys (M-1) or  at least 2 pointers and 1 key.Since it is a binary search tree the keys of left subtree will be less than the root value and keys of right subtree will be greater than root value.

• Create a node a and insert 5.(Fig 1)
• Insert 3 to the left of 5 (3<5).
• Insert 21 to the right of 5(21 >5).
• In order to insert 9 split node a into b and c as 9 cannot be accommodated in node a(Max keys =3).The left pointer  of 9 points to  3 and 5  ((3 ,5) <9)and the right pointer points to 21(21 >9),

Fig 1 : Insertion in B-Tree

• Insert 1 in node b (1<3)(Fig 2).
• Insert 13 in node c(13>9 and 13 <21).
• 2 cannot be directly inserted in node b
• In order to insert 2 split b into b and d.
• 3 gets stored in  node a.
• Store 1 and 2 in node b.
• Store 5 in node d.

Fig 2 : Insert 1,13,2

• Insert 7 in node dÂ .(7 >5 and 7<9)(Fig 3)
• Insert 10 in node c(10 >9 and 10 <13).
• Now 12 cannot be directly inserted in node c.
• Split c into c and e.
• 12 is then inserted in node Â c.
• 21 is stored in e.

Fig 3 : Insert 7,10,12

• Insert 4 in node d(4 >3 and 4 <5).(Fig 4)
• 8 cannot be inserted in d directly.
• Split d into f and g
• Split f into f and h.
• 8 is inserted in h.

Fig 4 : Insert 4,8

Short URL: http://tinyit.cc/edff9d
May 29, 2014 |
Tags:

## Traversal in Binary Trees

Traversal means to move across/visit each and every node in the tree.There are three techniques to traverse a Binary Tree :

• Preorder
• Inorder
• Postorder

### Preorder traversal

In preorder traversal,firstly  the root is traversed then left subtree and in the last right subtree(Fig 1).

Fig 1 : Technique of Pre-Order Traversal

### Example

Consider the following binary tree(Fig 2) :

Fig 2 : Pre-Order Traversal

Fig 3 : Traversal of nodes

Root is traversed in the beginning so 10 is visited at the first.After this left sub-tree is traversed. (Fig 3).  In the left subtree 22 is the root of 44 and 25,so 22 is visited after 10 followed by left child i.e.44.25 is the right child and  is the root node of 17 and 88.44 is followed by 25 then 17 and 88.After visiting left sub-tree traversal of right subtree is done.13 is visited and followed by left child i.e.46.

### Inorder Traversal

In In-order traversal,left subtree is traversed in the  beginning  followed by  root  which is further followed by  right sub-tree(Fig 4).

Fig 4 : Technique of In-order traversal

### Example

Consider the following binary tree(Fig 5) :

Fig 5 : In-Order Traversal

Fig 6 : Traversal of nodes

### Post Order Traversal

In post-order traversal left subtree is traversed first followed by right subtree and further followed by root.

Fig 7 : Technique of Post-Order traversal

Consider the following binary tree(Fig 5) :

Fig 8 : Post-order Traversal

Fig 9 : Post-Order Traversal

Short URL: http://tinyit.cc/4e9e08
May 7, 2014 |
Tags:

## Representation of Binary Trees in Memory

Binary trees in memory can be represented by

• Array

### Representation through Arrays

Binary Trees can be represented using 1-D array in memory(Fig 1).The rule to store binary tree in array are :

1. The values of binary tree is stored in an array called as tree.
2. The root of the tree is stored at first location i.e. at  tree[0](0 index).
3. The left child of tree is stored at  2i +1 and right child is stored at  2i+2 location.
4. The maximum size of the array tree is given as  2d+1-1, where d is the depth of the tree.
5. An empty tree or sub-tree is specified using NULL. If tree[0] = NULL, then it means that tree is empty.

Fig 1 : Array Representation of Binary Tree

In linked list representation,every node of the tree has three parts : the data/root element,the pointer to the left node and the pointer to the right node(Fig 2).In C,tree is built using structures by the following way :

```struct node
{
struct node* left;
int data;
struct node* right;
};```

Fig 2 : Linked List Representation of Binary Tree

Short URL: http://tinyit.cc/bfc8
May 6, 2014 |
Tags:

## Binary Trees

Binary Trees are the data structure defined by collection of elements called nodes.They are one of the efficient data structures for searching and insertion operations.The topmost node of binary tree is known as ROOT node  pointed by ROOT pointer.Root node has  left child/successor and  right child/successor pointed by left and right pointers(Fig 1).

Fig 1 : A Binary Tree

The left child further may or may not have successors and the right child may/may not have further successors.If nodes are split into further nodes then a tree is formed known as subtree of root.The left node of root(divided into further nodes) are collectively called as left subtree and right node(divided into further nodes) are called as right subtree(Fig 2).Every node in a binary tree has 0,1 or at most 2 successors.The node which does not have any successor is called as leaf node or terminal node.

Fig 2 : A Binary Tree

### Terms associated with Binary Tree

• Sibling -  If T is a tree and N is any node that has left child/successor S1 and right successor S2,then N is the parent of S1 and S2.S1 and S2 are called as siblings(Fig 3).Every node other than the root node has a parent.Thus all nodes  which are at same level and have same parent are known as siblings.In Fig 3, 2 and 3 are siblings and 1 is the parent of 2 and 3.

Fig 3 : Tree

• Level Number : It is the level of the node.The root node is at level 0 and its successors are at one level higher than previous i.e at level 1.The further successors of left and right child are at again one level higher i.e.at 2.Thus level number of all child nodes are +1 level of their parent level.

Fig 4 : Levels in binary tree

• Degree – It is equal to number of children that a node has.It can be 0,1 or 2 in case of binary tree.The degree of leaf nodes is 0.The degree of nodes in Fig 4 is as given below:

Fig 5 : Degree of nodes

•  In-Degree – It is the number of edges arriving at that node.The in-degree of root node is 0 as no edge arrives at root node.
• Out-degree – It is the number of edges that exits from that node.
• Leaf node – It is the terminal node having no children.
• Directed edge - Line drawn from node to any of the successor is known as directed edge.A binary tree of N nodes has exactly N-1 edges.
• Path –  A sequence of consecutive edges is known as Path.
• Ancestor nodes – All the nodes along the path from the root node to that node.
• Descendant nodes – All the nodes along the path from  that node to leaf node.
• Depth – It is the length of path from root node to node N.A binary tree of height has at least h nodes and at most 2h -1 nodes  .   For  e.g In Fig 4 height of tree is 4 and it can have  24 -1 =15 nodes at the max.

n = 2h -1
n + 1 =2h
log(n+1) = log(2h)
log2(n+1) = h

n is the number of nodes and h is the height of tree. The height of binary tree is at least n and at most log2(n+1).

Short URL: http://tinyit.cc/4ef084
May 2, 2014 |
Tags: