Archived

This topic is now archived and is closed to further replies.

Mucman

interesting exam quesiton I had!

Recommended Posts

I thought this was a good question about real word data structures (as far as I know) Explain the advantages and disadvantages of implementing an AVL tree contigously(staticly) or dynamicly. I had troubles finding the disadvantage for a dynamic AVL tree except maybe the space required for all the pointers... What are your opinions? btw, I am not given the answers to our finals so I don''t know what the actual answer is. "You won''t get wise with the sleep still in your eyes." - Neil Peart

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
One disadvantage of allocating it dynamically would be the extra time it takes to allocate the space on the heap as opposed to just sticking it on the stack. Of course the disadvantage of allocating it staticaly would be just that, it''s static and if you need to add things as you go you''re out of luck.

Share this post


Link to post
Share on other sites
Here''s my opinion.

Statically:

Good: no time for allocation calls. no allocation failures.
Bad: fixed maximum size for your avl tree. more complicated memory management logic for inserting and deleting nodes.

Dynamically:

Good: Easy to add / delete nodes. Can expand size of tree up to available memory.

Bad: Have to deal with allocation failure. More overhead for alloaction calls.

Share this post


Link to post
Share on other sites
Would search and sorting times be different for the two? They are both balanced BST''s so search times would be quick for both, but assuming the dynamic implementaion is recursive would it then be a tad slower? I say assuming recursion because we only learned how to implement trees using recursion.

"You won''t get wise with the sleep still in your eyes." - Neil Peart

Share this post


Link to post
Share on other sites
I agree, immediately after reading dynamic, I thought speed hit for allocation. Then I became really curious, so I looked it up in an old book I have (Data Structures and Algorithm Analysis in Java, Weiss). This seems to confirm that and got me thinking a little more. An AVL has some rigorous requirements, and by doing it dynamically, you have to modify new insertions fairly constantly, with becomes costly, as an insertion has "to update all the balancing information for the nodes on the path back to the root...". If it was static, and was AVL, then it would have to already match the AVL spec, and so then you couldn''t really mess it up as much, so an insertion would be less costly and quicker on static trees, right? I am pretty sure about the first part...this secondary theory could quite well be completly wrong though.

--OctDev

Share this post


Link to post
Share on other sites
I believe another answer might be; dynamically allocated objects tends to cause heap fragmentation and reduce locality of reference whereas statically allocated objects increase locality of reference and increase cache coherency.

Share this post


Link to post
Share on other sites