trees search trees are of great importance in algorithm design they support almost all the useful operationsand the logarithmic average cost is very small nonrecursive implementations of search trees are somewhat fasterbut the recursive versions are sleekermore elegantand easier to understand and debug the problem with search trees is that their performance depends heavily on the input being random if this is not the casethe running time increases significantlyto the point where search trees become expensive linked lists we saw several ways to deal with this problem avl trees work by insisting that all nodesleft and right subtrees differ in heights by at most one this ensures that the tree cannot get too deep the operations that do not change the treeas insertion doescan all use the standard binary search tree code operations that change the tree must restore the tree this can be somewhat complicatedespecially in the case of deletion we showed how to restore the tree after insertions in (log ntime we also examined the splay tree nodes in splay trees can get arbitrarily deepbut after every access the tree is adjusted in somewhat mysterious manner the net effect is that any sequence of operations takes ( log ntimewhich is the same as balanced tree would take -trees are balanced -way (as opposed to -way or binarytreeswhich are well suited for disksa special case is the - tree ( )which is another way to implement balanced search trees in practicethe running time of all the balanced-tree schemeswhile slightly faster for searchingis worse (by constant factorfor insertions and deletions than the simple binary search treebut this is generally acceptable in view of the protection being given against easily obtained worst-case input discusses some additional search tree data structures and provides detailed implementations final noteby inserting elements into search tree and then performing an inorder traversalwe obtain the elements in sorted order this gives an ( log nalgorithm to sortwhich is worst-case bound if any sophisticated search tree is used we shall see better ways in but none that have lower time bound exercises for the tree in figure which node is the rootb which nodes are leaves for each node in the tree of figure name the parent node list the children list the siblings compute the depth compute the height what is the depth of the tree in figure show that in binary tree of nodesthere are nullptr links representing children