Jump to content
  • Advertisement
Sign in to follow this  
JohnnyCasil

23 Tree Implementation

This topic is 4527 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I have been working at this problem for some time now and I am wondering if any of you sages out there have any insight for me. I have to implement a 23 Tree using an array as the backing data structure. I have already impelemented a working 23 Tree using linked nodes, so I understand the theory behind them. The problem I am having is with the promotion of the values into the higher nodes. I currently have an array of a class I call TwoThreeEntry. TwoThreeEntry is just a POD type that contains the node's min value, max value, and a boolean indicating whether or not it is filled. I understand that when using an array like this I can find a parent's children by calculating their offsets, and I have that working as well. Now, when I am inserting a value, as you know if the node is filled I have to promote that value into a higher node. This is where I am having trouble wrapping my head around the array version of it, because using linked nodes was cake. If I promote a value into a node that isn't filled, it makes sense to me that I can just shift the values of the child nodes into their appropriate places, but when I promote a node into a filled node that I have to promote again, I am failing to see an simple solution to how to rearrange the nodes. I'm not asking anyone to write the code for me, and frankly I don't want you to, I am just asking for any insight into this problem. I've been working at for so long now and I just can't seem to find a simple solution, the sad thing is I have a feeling it'll be something simple I just overlooked.

Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!