trees actually proved this in any eventthis phenomenon appears to be mostly theoretical noveltybecause the effect does not show up at all for small treesandstranger stillif ( insert/remove pairs are usedthen the tree seems to gain balancethe main point of this discussion is that deciding what "averagemeans is generally extremely difficult and can require assumptions that may or may not be valid in the absence of deletionsor when lazy deletion is usedwe can conclude that the average running times of the operations above are (log nexcept for strange cases like the one discussed abovethis result is very consistent with observed behavior if the input comes into tree presortedthen series of inserts will take quadratic time and give very expensive implementation of linked listsince the tree will consist only of nodes with no left children one solution to the problem is to insist on an extra structural condition called balanceno node is allowed to get too deep there are quite few general algorithms to implement balanced trees most are quite bit more complicated than standard binary search treeand all take longer on average for updates they dohoweverprovide protection against the embarrassingly simple cases belowwe will sketch one of the oldest forms of balanced search treesthe avl tree second method is to forgo the balance condition and allow the tree to be arbitrarily deepbut after every operationa restructuring rule is applied that tends to make future operations efficient these types of data structures are generally classified as self-adjusting in the case of binary search treewe can no longer guarantee an (log nbound on any single operation but can show that any sequence of operations takes total time ( log nin the worst case this is generally sufficient protection against bad worst case the data structure we will discuss is known as splay treeits analysis is fairly intricate and is discussed in avl trees an avl (adelson-velskii and landistree is binary search tree with balance condition the balance condition must be easy to maintainand it ensures that the depth of the tree is (log nthe simplest idea is to require that the left and right subtrees have the same height as figure showsthis idea does not force the tree to be shallow figure bad binary tree requiring balance at the root is not enough