2-3-4 Tree

-

 Generally all the process is same as 2-3 Tree. So here we discuss the differences of 2-3-4 Tree from 2-3 Tree.


  • Every Node must have at least ceil(n/2 here 4/2) children and maximum 4 children that's why is is called 2-3-4 tree b/c it will have 2 or 3 or 4 child of a node.
  • Also called B-Tree of degree 4
  • Every node must be at same level

Representation:


Splitting:

        When we insert element while node is full we will have even(4) number of elements so we can't divide element uniformly for splitting. So either we put more element to right, i.e. right biased or to left i.e. left biased.

    Let we insert 40 in non-empty node: 



Comments

Post a Comment

Popular posts from this blog

Insertion/Deletion in 2-3 Tree

-
Image
Insertion:               Let we create 2-3 tree by inserting elements:                                                                      20, 30, 40, 50, 60, 10, 15, 70, 80                Insert 20,30:               Now we insert these two element in a single node as it can hold 2 elements so,       Insert 40:               Node is already full so split the node             In splitting: We take two nodes left and right and a root node Left node contain smallest element Right node contain greatest element Root node contain middle element and take lest and right as child               So the final tree will be:      Insert 50:               50 is greater than 40 and after 40 a blank space so insert 50 in that blank space:     Insert 60:               60 is greater than 50 but there is no space for 60 so split, after splitting the root element will move to the root that contain 30 b/c there is an empty space in that node, so final tree will be:     Insert 10:               10 is smal
Read more