if val root getval()root setleft(binarysearchtree __insert(root getleft(),val)elseroot setright(binarysearchtree __insert(root getright(),val)return root if items are inserted into binary search tree in ascending order the effect is that execution always progresses from line to and the result on line puts the new value in the right most location of the binary search treesince it is the largest value inserted so far the resulting tree is stick extending down and to the right without any balance to the treeinserting the next bigger value will result in traversing each and every value that has already been inserted to find the location of the new value this means that the first value takes zero comparisons to insertwhile the second requires one comparison to find its final locationthe third value requires two comparisonsand so on the total number of comparisons to build the tree is ( as proved in chap this complexity will be much too slow for any site getting reasonable amount of activity in an hour in additionwhen the height of the binary search tree is nwhere is the number of values in the treethe look upinsertand delete times are (nfor both the worst and average cases when the tree is stick or even close to being stick the efficiency characteristics of binary search tree are no better than that of linked list avl trees binary search tree that stays balanced would provide everything that is required by the website log described in the last section avl trees are binary search trees with additional information to maintain their balance the height of an avl tree is guaranteed to be (log nthus guaranteeing that lookupinsertand delete operations will all complete in (log ntime with these guaranteesan avl tree can be built in ( log ntime from sequence of items moreoveravl treeslike binary search treescan be traversed using an inorder traversalyielding their items in ascending order in (ntime definitions to understand how avl trees worka few definitions are in order height(tree)the height of tree is one plus the maximum height of its subtrees the height of leaf node is one balance(tree)the balance of node in binary tree is height(right subtree)-height(left subtreeavl treean avl tree is binary tree in which the balance of every node in the tree is - or this copy belongs to 'acha