avl trees an avl tree is another balanced binary search tree named after their inventorsadelson-velskii and landisthey were the first dynamically balanced trees to be proposed like red-black treesthey are not perfectly balancedbut pairs of subtrees differ in height by at most maintaining an (lognsearch time addition and deletion operations also take (logntime definition of an avl tree an avl tree is binary search tree which has the following properties the sub-trees of every node differ in height by at most one every sub-tree is an avl tree balance requirement for an avl treethe left and right sub-trees differ by at most in height you need to be careful with this definitionit permits some apparently unbalanced treesfor examplehere are some treestree avl treeyes examination shows that each left sub-tree has height greater than each right subtree