COSC$2007$ Lab $6-2-3$ Trees

Rules of a $2-3$ Tree:

$-$ All of the internal nodes can be classified as either a $2-$node or a $3-$node

$-$ All leaf nodes exist on the same level of the tree $($the bottom$)$

$-$ The data is always kept in sorted order

$2-$node

A $2-$node will always have a parent node which contains a single element and has $2$ children. A $3-$node will always have a parent node which contains $2$ elements and has $3$ children.

Please refer to course content regarding the algorithms for insertion and deletion of nodes in a $2-3$ tree. You should complete and understand those sections before attempting this lab.

$1.$ Draw the resulting $\backslash (2-3\backslash )$ tree from the following series of insertions: $\backslash (90,45,62,74,16,3\backslash ),86,94,22,60,72,31,88.$

$2.$ Delete the node containing $62$ from the tree you have built in question $1$ and draw the resulting tree. Explain the algorithm's process to replace that node.

$3.$ What is the efficiency of finding the maximum, minimum, and middle elements in a $2-3$ tree? Briefly explain why. Will the middle element $($or elements$)$ always be found in the root node?

$4.$ Does inserting an element and then immediately deleting it always result in the original tree $($before the element was inserted$)?$ Explain why or why not.