In the previous article we’ve reviewed Randomized Binary Search Trees. Today we are going to review the implementation of AVL Trees. They must be the first type of Balanced Binary Search Trees. They were invented by two Soviet inventors, G. M. Adelson-Velskii and E. M. Landis in 1962. There are plenty of AVL trees implementations, but, to my mind, none of them is good enough when you try to make sense of it all from scratch. They say that AVL trees are simpler than Red-Black trees, but when looking at the code, we can not believe it. Thus, I have decided to explain the structure of AVL trees step by step. I’ll also provide the code in C++.AVL Tree Notion First of all, an AVL Tree is a Binary Search Tree (BST), the keys of which meet standard requirements: a key of any tree node is not less than the key in the left subtree of the given node and not more than any key in the right subtree of this node. This means that in order to find the necessary key in an AVL tree, we can use a standard algorithm. For simplicity, we will consider that all keys

Source: AVL Trees

### Like this:

Like Loading...

*Related*