balancing binary search trees if the items are added to binary search tree in random orderthe tree tends to be fairly well balanced with height not much more than log howeverthere are many situations where the added items are not in random ordersuch as when adding new student ids in the extreme case of the new items being added in ascending orderthe tree will be one long branch off to the rightwith height log if all the items to be inserted into binary search tree are already sortedit is straightforward to build perfectly balanced binary tree from them one simply has to recursively build binary tree with the middle ( medianitem as the rootthe left subtree made up of the smaller itemsand the right subtree made up of the larger items this idea can be used to rebalance any existing binary search treebecause the existing tree can easily be output into sorted array as discussed in section exercisewrite an algorithm that rebalances binary search tree in this wayand work out its time complexity another way to avoid unbalanced binary search trees is to rebalance them from time to time using tree rotations such tree rotations are best understood as followsany binary search tree containing at least two nodes can clearly be drawn in one of the two formswhere and are the required two nodes to be rotatedand ac and are binary search sub-trees (any of which may be emptythe two forms are related by left and right tree rotations which clearly preserve the binary search tree property in this caseany nodes in sub-tree would be shifted up the tree by right rotationand any nodes in sub-tree would be shifted up the tree by left rotation for exampleif the left form had consisting of two nodesand and consisting of one nodethe height of the tree would be reduced by one and become perfectly balanced by right tree rotation typicallysuch tree rotations would need to be applied to many different sub-trees of full tree to make it perfectly balanced for exampleif the left form had consisting of two nodesand and consisting of one nodethe tree would be balanced by first performing left rotation of the - - sub-treefollowed by right rotation of the whole tree in practicefinding suitable sequences of appropriate tree rotations to rebalance an arbitrary binary search tree is not straightforwardbut it is possible to formulate systematic balancing algorithms that are more efficient than outputting the whole tree and rebuilding it self-balancing avl trees self-balancing binary search trees avoid the problem of unbalanced trees by automatically rebalancing the tree throughout the insertion process to keep the height close to log at each stage obviouslythere will be cost involved in such rebalancingand there will be