in chap binary search trees were defined along with recursive insert algorithm the discussion of binary search trees pointed out they have problems in some cases binary search trees can become unbalancedactually quite often when tree is unbalanced the complexity of insertdeleteand lookup operations can get as bad as (nthis problem with unbalanced binary search trees was the motivation for the development of height-balanced avl trees by adelson-velskii and landistwo soviet computer scientistsin avl trees were named for these two inventors their paper on avl trees [ described the first algorithm for maintaining balanced binary search trees balanced binary search trees provide (log ninsertdeleteand lookup operations in additiona balanced binary search tree maintains its items in sorted order an infix traversal of binary search tree will yield its items in ascending order and this traversal can be accomplished in (ntime assuming the tree is already built the hashset and hashmap classes provide very efficient insertdeleteand lookup operations as wellmore efficient than the corresponding binary search tree operations heaps also provide (log ninsert and delete operations but neither hash tables nor heaps maintain their elements as an ordered sequence if you want to perform many insert and delete operations and need to iterate over sequence in ascending or descending orderperhaps many timesthen balanced binary search tree data structure may be more appropriate goals this describes why binary search trees can become unbalanced then it goes on to describe several implementations of two types of height-balanced treesavl trees and splay trees by the end of this you should be able to implement your own avl or splay tree datatypewith either iteratively or recursively implemented operations (cspringer international publishing switzerland lee and hubbarddata structures and algorithms with pythonundergraduate topics in computer sciencedoi -- this copy belongs to 'acha