I have to code Insert/Remove for and AVL tree derived from a BST. I have a fully functional Insert working. Do determine the heights, I call a Height function that recursively calculates the height of each node. Does this violate the constraints on an AVL tree that all functions are to run in O(log n)?
-
-
It's been a long time since I've thought about implementation details of balanced trees (thanks to STL).
Does your Height calculate the height of each node in the entire tree, or does it just calculate the Height of the branch that the new node is on?
Calculating for every node in the tree is O(n), calculating the height for only the branch is likely O(log n).
Comment