Jump to content

View more

View more

Image of the Day

雑魚は多めにして、爽快感重視にしつつ・・・(´・ω・`)
早いとこ、ベースを作って、完成にもっていかないとね。
タイトルもまだ迷ってるだよなぁ。 
#indiedev  #indiegame #screenshotsaturday https://t.co/IwVbswGrhe
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct 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.