By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
431,871 Members | 2,464 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 431,871 IT Pros & Developers. It's quick & easy.

AVL (Height Balanced) Tree

P: 54
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)?
Nov 19 '10 #1
Share this Question
Share on Google+
1 Reply


100+
P: 256
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).
Nov 19 '10 #2

Post your reply

Sign in to post your reply or Sign up for a free account.