/* attempt to deal with prototype, bootstrap, jquery conflicts */ /* for dropdown menus */

Jump to content

Image of the Day

Day 17 -- a bunch more tools join the table :) #blender3d #screenshotsaturday #itssaturdaysomewhere #lowpoly #3D https://t.co/CYJucn0Lfv
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net's newsletters to receive the latest updates and exclusive content.


Sign up now

Top-down insertion and deletion for 2-3 tree possible?

4: Adsense

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


  • You cannot reply to this topic
No replies to this topic

#1 ultramailman   Prime Members   

1720
Like
0Likes
Like

Posted 04 December 2012 - 03:04 AM

Hello
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?




Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.