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

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

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