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

UIImagePickerController custom overlay and tap-to-focus

iphone uiimagepickercontroller

Is it possible to display a tap-to-focus blue box when a custom overlay is used in a UIImagePickerView and when showsCameraControl attribute is set to FALSE?

Button setOnClickListener on for loop

android buttonclick

I have 10 buttons and i want to set OnClickListener for all that buttons. Also with clicking on any button app will go another activity. I only post the buttons' definitions on the activity class....

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.