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++!**:)**

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

And sorry for the erros above, my Engilish is worse than my C++!

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

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

Last edited on

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.

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.

Topic archived. No new replies allowed.