AVL Tree

[audinue]

The next exam for my Data Structure Subject is AVL tree, but until now I still don't get what the hell is it..

AVL Tree, what is it for anyway?
Any applications maybe? Anyone know?

http://en.wikipedia.org/wiki/AVL_tree

http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html

Thanks in advance.

[twomers]

http://www.eternallyconfuzzled.com/t...w_tut_avl.aspx Source 'n' all. Say thanks to Prelude.

[audinue]

New programmers who are introduced to binary search trees quickly learn that if items are inserted in certain orders, the performance of the tree degenerates into that of a glorified linked list. Many brain cells have been devoted to the task of finding efficient ways to avoid these worst cases. Many exceedingly clever solutions have been developed, but only a handful have made it into public knowledge and even fewer into common use. Of those solutions, height balanced trees are the most common, and the AVL tree is probably the oldest of the height balanced trees.

So it's a extended binary search tree useless

[SlyMaelstrom]

So it's a extended binary search tree useless

Actually, it's a balanced binary search tree that essentially renders a plain binary search tree useless as most trees lose their height balance relatively quickly. Almost all real tree implementations should utilize some form of height checking and balancing.