trees

Binomial Trees

http://install4install.com

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 \tbinom n d nodes at depth d.
Slide1

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

Screen Shot 2014-05-30 at 3.53.29 PM

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

Screen Shot 2014-05-30 at 4.00.23 PM

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

Screen Shot 2014-05-30 at 4.06.02 PM

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

Screen Shot 2014-05-30 at 4.20.33 PM

Fig 5 : Binomial Tree of order 3

 

 

Bn  has  \tbinom n d 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  \tbinom n d.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.

Screen Shot 2014-05-30 at 4.26.02 PM

 

Screen Shot 2014-05-30 at 4.33.36 PM

Fig 6 : Binomial Tree of order 4


Short URL: http://tinyit.cc/f8eed0
By Cusp2207 on May 30, 2014 | Computer Science, Data Structures | A comment?
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.

Screen Shot 2014-05-29 at 4.58.17 PM

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)

 

Screen Shot 2014-05-29 at 5.02.50 PM

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.

 

Screen Shot 2014-05-29 at 5.07.01 PM

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).
Screen Shot 2014-05-29 at 5.15.41 PM

Fig 4 : Delete 10

 

Delete 3

  • Deletion of 3 causes 4 to move in a (Fig 5).
Screen Shot 2014-05-29 at 5.36.18 PM

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).
Screen Shot 2014-05-29 at 5.47.33 PM

Fig 6 : Delete 4


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

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),
Screen Shot 2014-05-29 at 3.54.56 PM

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.

 

Screen Shot 2014-05-29 at 3.55.47 PM

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.

 

Screen Shot 2014-05-29 at 3.56.29 PM

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.
Screen Shot 2014-05-29 at 4.26.04 PM

Fig 4 : Insert 4,8

 


Short URL: http://tinyit.cc/edff9d
By Cusp2207 on May 29, 2014 | Computer Science, Data Structures | 1 comment
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 : Pre-order Traversal

Fig 1 : Technique of Pre-Order Traversal

Example

Consider the following binary tree(Fig 2) :

preorder

Fig 2 : Pre-Order Traversal

Screen Shot 2014-05-06 at 6.05.59 PM

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

Screen Shot 2014-05-06 at 4.28.13 PM

Fig 4 : Technique of In-order traversal

 

Example

Consider the following binary tree(Fig 5) :

inorder

Fig 5 : In-Order Traversal

 

Fig 6 : Traversal in In-Order

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.

Screen Shot 2014-05-06 at 4.40.19 PM

Fig 7 : Technique of Post-Order traversal

 

Consider the following binary tree(Fig 5) :

postorder

Fig 8 : Post-order Traversal

Fig 9 : Post-Order Traversal

Fig 9 : Post-Order Traversal

 


Short URL: http://tinyit.cc/4e9e08

Representation of Binary Trees in Memory

Binary trees in memory can be represented by

  • Array
  • Linked Lists

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.
Screen Shot 2014-05-05 at 4.20.55 PM

Fig 1 : Array Representation of Binary Tree

Screen Shot 2014-05-05 at 4.34.11 PM

Representation through Linked List

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 Trees

Fig 2 : Linked List Representation of Binary Tree

 

 


Short URL: http://tinyit.cc/bfc8

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

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

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.
Screen Shot 2014-05-01 at 3.08.58 PM

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:

 

Screen Shot 2014-05-01 at 3.23.02 PM

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