balanced search trees in the closing of the previous sectionwe noted that if we could assume random series of insertions and removalsthe standard binary search tree supports (log nexpected running times for the basic map operations howeverwe may only claim (nworst-case timebecause some sequences of operations may lead to an unbalanced tree with height proportional to in the remainder of this we explore four search tree algorithms that provide stronger performance guarantees three of the four data structures (avl treessplay treesand red-black treesare based on augmenting standard binary search tree with occasional operations to reshape the tree and reduce its height the primary operation to rebalance binary search tree is known as rotation during rotationwe "rotatea child to be above its parentas diagrammed in figure figure rotation operation in binary search tree rotation can be performed to transform the left formation into the rightor the right formation into the left note that all keys in subtree have keys less than that of position xall keys in subtree have keys that are between those of positions and yand all keys in subtree have keys that are greater than that of position to maintain the binary search tree property through rotationwe note that if position was left child of position prior to rotation (and therefore the key of is less than the key of )then becomes the right child of after the rotationand vice versa furthermorewe must relink the subtree of items with keys that lie between the keys of the two positions that are being rotated for examplein figure the subtree labeled represents items with keys that are known to be greater than that of position and less than that of position in the first configuration of that figuret is the right subtree of position xin the second configurationit is the left subtree of position because single rotation modifies constant number of parent-child relationshipsit can be implemented in ( time with linked binary tree representation