by successive insertions as we have seen aboveperfectly balanced trees achieve minimal height for given number of nodesand it turns out that the more balanced treethe more ways there are of building it this is demonstrated in the figure below the only way of getting the tree on the left hand side is by inserting into the empty tree in that order the tree on the righthowevercan be reached in two waysinserting in the order or in the order ideallyof courseone would only use well-balanced trees to keep the height minimalbut they do not have to be perfectly balanced to perform better than binary search trees without restrictions carrying out exact tree height calculations is not straightforwardso we will not do that here howeverif we assume that all the possible orders in which set of nodes might be inserted into binary search tree are equally likelythen the average height of binary search tree turns out to be (log nit follows that the average number of comparisons needed to search binary search tree is (log )which is the same complexity we found for binary search of sorted array howeverinserting new node into binary search tree also depends on the tree height and requires (log nstepswhich is better than the (ncomplexity of inserting an item into the appropriate point of sorted array interestinglythe average height of binary search tree is quite bit better than the average height of general binary tree consisting of the same nodes that have not been built into binary search tree the average height of general binary tree is actually onthe reason for that is that there is relatively large proportion of high binary trees that are not valid binary search trees deleting nodes from binary search tree supposefor some reasonan item needs to be removed or deleted from binary search tree it would obviously be rather inefficient if we had to rebuild the remaining search tree again from scratch for items that would require steps of (log ncomplexityand hence have overall time complexity of (nlog nby comparisondeleting an item from sorted array would only have time complexity ( )and we certainly want to do better than that insteadwe need an algorithm that produces an updated binary search tree more efficiently this is more complicated than one might assume at first sightbut it turns out that the following algorithm works as desiredif the node in question is leafjust remove it if only one of the node' subtrees is non-empty'move upthe remaining subtree if the node has two non-empty sub-treesfind the 'left-mostnode occurring in the right sub-tree (this is the smallest item in the right subtreeuse this node to overwrite the