Rotacja drzewa – operacja polegająca na lokalnej zmianie struktury binarnego drzewa poszukiwań (BST) z zachowaniem porządku wierzchołków. Rotacje stosuje się w drzewach BST do uzyskania wyważenia drzewa i minimalizacji jego wysokości, co prowadzi do zmniejszenia kosztu operacji na drzewie. Matematycznie rotacja jest dopuszczalna jeżeli relacja opisana drzewem jest łączna. Binarne drzewa poszukiwań są generalnie łączne ze względu na łączność relacji porządkującej klucze. Jeżeli rozpatrywane jest drzewo składniowe opisujące wyrażenie arytmetyczne to rotacje są dozwolone tylko między operacjami, które są łączne - np. dodawanie można obracać względem dodawania lub odejmowania, ale nie względem mnożenia.
Przebieg rotacji Rotacja odbywa się wokół krawędzi drzewa. Jeżeli jest rodzicem (jest wyżej w drzewie), a jest jego lewym synem, mówimy o prawej rotacji (rotacji w prawo), jeżeli jest prawym synem – o lewej rotacji (rotacji w lewo). frame|center|Lewa i prawa rotacja wokół krawędzi
Pseudokod W poniższym pseudokodzie oznacza wierzchołek leżący wyżej w drzewie, – wierzchołek leżący niżej (lewego syna ), a rotacja odbywa się w prawo względem krawędzi (sytuacja przy rotacji lewej jest symetryczna).