Given a 2-3 tree, How can we find a possible insertion order?

so say you are given a 2-3 tree, complete with nodes and a couple of levels. How could you find one of the several possible insertion orders/sequences that give you the resulting tree?

No need for code, just a paper task. I'm certain (praying) it isn't a case of simple trial and error.

A similar question was asked here, but no reply

2-3 tree insertion

Answers


I'm new to this subject, but I'll take a crack at it.

All we have to do is find a way to take one step backward. That is, to choose a value that may have been the last one added, and deduce what the previous tree must have been.

A new value is added to a leaf; either the leaf had one value (and now has two), or it had two and the new value caused a split. A split will propagate up the tree until it stops either by creating a 3-node or a new root 2-node.

So here's a way to choose a value that may have been the last one added. If there are any two-value nodes in the tree, pick one of the lowest ones; either value in that node may have been the last one. If there are no two-value nodes in the tree, then any value in the tree may the value in the root node must have been the last one.

(That's not exhaustive, there are other possibilities, but we're trying to find a candidate, not all candidates.)

Once you've chosen a value, removing it by unsplitting down to a leaf is pretty straightforward.

Does that suffice, or should I explain in more detail?


Need Your Help

Weblogic hangs after request is processed by application at DynaQueue.getW

weblogic12c solaris-10

On a Weblogic 12c / Solaris 10 production system, the time to process a request is about 5 sec. The time taken by the application itself deployed on Weblogic is less than 200ms and after that the

Trying to create a system to merge two lists of "buzz words" together, forming every possibility for domain availability checking?

list dns

My problem originates from me trying to create names for all my crazy (brilliant?) ideas for business and products, which then need to have their purchasing availability checked for .com domain nam...