AVL-puu, binomiaalpuu ja värvitud kahendpuu (red-black tree).
AVL (Adelson-Velski, Landis) puu on kahendotsimise puu, mille korral:
1. Vasak ja parem alampuu on AVL-puud ning nende kõrgused erinevad ülimalt ühe võrra.
2. Tühi puu on AVL-puu.
Otsimine puud ei muuda ja on korraldatud samuti, nagu kahendotsimise puus.
Lisamine ja eemaldamine tuleb defineerida nii, et AVL-puu omadus säiliks, s.t. alampuude kõrguste vahe ei tohi olla suurem kui 1.
Pööre.Alampuude I ja III kõrgused enne pööret erinevad 2 võrra, omadus a≤b säilib.
Seda joonist võiks vaadata ka peegelpildis.
Topeltpööre. Alampuude I ja III kõrgused enne pööret erinevad 2 võrra, omadus a≤c≤b säilib.
Ka seda joonist võib vaadata peegelpildis.