2-3 Tree

 2-3 TREE

Let we understand 2-3 tree by some points:

📢 It is a basically a B Tree of order 3.

📢 It has maximum 2 children and maximum 2 key values.

📢 It is a search tree.

📢 To keep the height of a binary search tree a 2-3 tree were developed.

📢 A 2-3 tree is a binary search tree that can have the following nodes

    1. Leaf Nodes

    2. 2- Nodes

    3. 3-Nodes

LET WE DISCUSS SOME PROPERTIES OF 2-3 TREE :

💧 Each node with children has either 2 children & 1- parent.

💧 Each node with children has either 3 children & 2- parent.

💧 Leaf node have no children & one or two parents.

💧 All leaf nodes are at the same level of the tree because it is balance.

💧 Elements of tree are arrange in ascending order.

Let we understand by taking an example:

Insert following elements into a empty 2-3 tree such as

46 ,68 , 36 , 18 , 10 , 9 , 5 , 49 

1. INSERT 46

2. INSERT 68

3. INSERT 36

4. INSERT 18

5. INSERT 10

6. INSERT 9

7. INSERT 5

8. INSERT 49

FINALLY WE GET

ALGORITHM FOR INSERTING ELEMENT IN 2-3 TREE:

STEP 1: If the tree is empty , create a node and put value into the node.

STEP 2: Otherwise find the leaf node where the value belongs.

STEP 3: If the leaf node has only one value put the new value into the node.

STEP 4: If the leaf node has more than two values ,split the node and promote the middle of the three vertex to the parents.

STEP 5: if the parent has more than two values continue to split and promote and create a new root node if necessary.