CODEWITHSUNDEEP
java
Klaus
Klaus

Reputation: 11

Does my height function destroy my O(log N) AVL tree insert and remove? How to implement height?

I have implemented an AVLtree but now that it is finished I thought of something. Basically I compute the height by calculating the height of each subtree each time. algorithm is something like:

if node is null return -1;
else return 1 + max( height(left), height(right))

Ths means when i check if my tree is balanced I use this function. But height this way is LINEAR right? so that means remove and insert will be N log N or N, not log N?

Upvotes: 1

Views: 425

Answers (2)

axtavt
axtavt

Reputation: 242686

The whole point of AVL trees is that you don't need height at all.

Each node stores the difference between heights of left and right subtrees. Since tree is balanced, that difference can be only -1, 0 or 1. During insertion you increase or decrease the difference depending on which subtree you inserted the items, and rebalance the tree if it yields -2 or 2. So, the actual height of subtrees is not used in algorithms at all.

Upvotes: 0

Mike Samuel
Mike Samuel

Reputation: 120496

Yes, that is linear in the number of nodes in the tree.

Can you cache the height with the subtree, so only the portion of the tree that you mutate needs to have height recomputed (mutated nodes and their ancestors)? That should get you back to O(log n) at a cost of O(n) storage.

Upvotes: 2

Related Questions