• Advertisement
Sign in to follow this  

23 Tree Implementation

This topic is 4345 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