AVL Insert Algorithm

[guerreiro]

I'm a c++ newbie and now I have a quest to complete: Make an AVL tree that the data is only added.
I know how to read, because an AVL tree is a binary seach tree and I implemented it already, but I don't know how to make the 'insert' algorithm.
Searching Google I only found fuzzy things and strange implementations. All I know is that I need to make node rotations and the node have the following fields: key, value, left and right childs and the height of the subtree.
I only need a method to insert a node to the tree, whitout that type parameters like AVLTree<key_type, value_type>, because the type of the key is char* and the value is int
And sorry for the erros above, my Engilish is worse than my C++! :)

[K0T4K0t4]

http://en.wikipedia.org/wiki/AVL_tree#Insertion
that has the basic algorithm layout for insertion and deletion. If you have a good understanding of how trees work and how you construct nodes for them it shouldn't be too implement. Specifics on how it will be done is going to be based on how you implemented the AVL. If you cant figure it out from that then post your AVL tree implementation so we can give you a better idea of exactly how you'd do it.

Also you can you the boost library to do avl tress pretty easily since they have everything already implemented and overloaded so you just have to call the functions. More info on it can be found at
http://www.boost.org/doc/libs/1_37_0/doc/html/boost/intrusive/avltree.html

[guerreiro]

Thank you K0T4K0t4, I'm pretty sure I can do this!
I also found this website: http://www.cs.usfca.edu/~galles/visualization/AVLtree.html, that is very interesting because it shows how the AVL tree works animating the operations and showing the explanation of each step on the top left corner of the screen.