Da die Loeschen und Einfuegen Operationen in einem binaeren Suchbaum dessen Ausgeglichenheit verletzen koennen, ist es notwendig, den Baum umzuformen. Dazu werden meist sogenannte Rotationen benutzt, die wir jetzt naeher beschreiben wollen.
Das Bild 5 zeigt einen binaeren Suchbaum T mit der Wurzel u und einem linken Unterbaum mit der Wurzel v. Eine einfache Rotation von u nach rechts endet in dem binaeren Suchbaum T' mit der Wurzel v und einem Unterbaum mit der Wurzel u. Gleichermassen sei ein binaerer Suchbaum T' gegeben, mit der Wurzel v und einem rechten Unterbaum mit der Wurzel u. Eine Rotation von v nach links resultiert in T. Diese Rotationen veraendern nur die Position von 2 Knoten, und koennen irgendwo in dem Baum auftreten.
Die wichtige Eigenschaft dieser Rotationenen ist, dass sie die binaere Suchbedingung bewahren. Das heisst, dass vor und nach jeder Rotation jeder Knoten des binaeren Suchbaums durch eine binaere Suche gefunden werden kann. Eine weitere Eigenschaft ist, dass bei diesen Rotationen ausschliesslich zwei Knoten veraendert werden, der Rest des Baumes bleibt unveraendert.
Folgende Ungleichungen muessen laut der binaeren Suchbedingung fuer T gelten (ein Suchschluessel eines Knoten x wird durch S(x), mehrere Suchschluessel durch SS(x) bezeichnet):
SS(1)<S(v)<SS(2)<S(u)<SS(3)
Es ist leicht zu sehen, dass diese Gleichung auch fuer T' gilt.
Diese Transformationen werden ,,einfache Rotationen'' genannt. Um binaere Baeume ausgleichen zu koennen, wird haeufig noch eine Umformung benutzt, die einen Knoten um zwei Stellen bewegt. Dabei gibt es zwei verschiedene Arten. Die eine wird bei unter anderem bei Rot-Schwarz Baeumen benutzt, die zweite findet fast ausschliesslich ihre Anwendung bei Splay-Baeumen.
Bild 6 zeigt eine doppelte Rotation von w, wie sie auch bei Rot-Schwarz und AVL-Baeumen benutzt wird. Wir bezeichnen diese Rotation von nun an als links-rechts-Rotation. Da diese Transformation aus zwei einfachen Rotationen besteht, wird auch bei dieser die binaere Suchbedingung gewahrt.
Bild 7 zeigt die rechts-links-Rotation von x.
Bild 8 zeigt die rechts-rechts und links-links Rotation. Diese findet ihre Anwendung bei AVL- und Splay-Baeumen. Auch bei dieser Rotation bleibt die binaere Suchbedingung gewahrt, da es sich wieder um eine Folge von zwei einfachen Rotationen handelt.
