સાદો BST લિંક્ડ લિસ્ટમાં અધોગતિ પામી શકે છે (O(n) કામગીરી) જો કી સૉર્ટેડ ક્રમમાં આવે. સ્વ-સંતુલન BSTs — જેમ કે AVL અને લાલ-કાળું વૃક્ષ — insertion/deletion પછી નોડ્સને આપમેળે ફરીથી ગોઠવે છે જેથી ઊંચાઈ ~log n રહે, O(log n) કામગીરીની ખાતરી આપે છે.
સંતુલન સમસ્યા
text
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)