Top-down insertion and deletion for 2-3 tree possible?,
Prime Members - Reputation: 1720
Posted 04 December 2012 - 03:04 AM
Is it possible to insert to or delete from a 2-3 tree in a top-down fashion, like it is with 2-4 trees?
I am trying to learn about red black trees, but I decided I would implement one that corresponds with 2-3 trees instead of 2-4 trees.
Recursive insertion is implemented, but I just can't figure out how to do it top-down, iteratively, and without using a stack of ancestors.
I know in the case of 2-4 trees, top-down insertion is done by splitting 4-nodes before reaching the leaf to guarantee a leaf that is 2-node or 3-node, but this doesn't seem to work with 2-3 trees because of the lower number of keys allowed.
I suspect 2-3 trees can't be inserted into in a top-down fashion. What do you think?