New to AVL tree implementation.

Posted by nn on Stack Overflow See other posts from Stack Overflow or by nn
Published on 2010-06-01T12:40:33Z Indexed on 2010/06/01 12:43 UTC
Read the original article Hit count: 346

Filed under:
|
|
|
|

I am writing a sliding window compression algorithm (LZ77) that searches for phrases in a "moving" dictionary.

So far I have written a BST where each node is stored in an array and it's index in the array is also the value of the starting position in the window itself.

I am now looking at transforming the BST to an AVL tree. I am a little confused at the sample implementations I have seen. Some only appear to store the balance factors whereas others store the height of each tree.

Are there any performance advantage/disadvantages of storing the height and/or balance factor for each node? Apologies if this is a very simple question, but I'm still not visualizing how I want to restructure my BST to implement height balancing.

Thanks.

© Stack Overflow or respective owner

Related posts about c

    Related posts about algorithm