2-3 Trees

-

 Some properties:

  • Multiway/M-way search tree
  • Degree : 3 (maximum no. of children)
  • All leaf at same level
  • Every node must have at least ceil(n/2 here 3/2) children
  • Also call B-Tree of degree 3
  • Can't have duplicate element

Representation:

  • l contain all the element smaller than k1
  • m contain all the element b/w k1 and k2
  • n contain all the element greater than n
  • k1 < k2 for every node

Applications:

  • Used as example during study B-Tree and B+ Tree
  • Used internally in DBMS    

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