Een gewone BST kan degenereren in een gekoppelde lijst (O(n) operaties) als sleutels in gesorteerde volgorde arriveren. Zelf-balancerende BSTs — zoals AVL en rood-zwarte bomen — voeren automatisch rotaties uit na invoegingen/verwijderingen om de hoogte ~log n te houden, waardoor operaties worden gegarandeerd.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL boom | Rood-zwarte boom | |
|---|---|---|
| Balanceringsnauwkeurigheid | strikt (hoogte-gebalanceerd) | losser |
| Zoekopdrachten | sneller (korter) | iets langzamer |
| Invoegen/verwijderen | meer rotaties | minder rotaties |
| Het beste voor | lees-intensieve werklasten | schrijf-intensieve werklasten |
| Operatie | Tijd |
|---|---|
| zoeken | O(log n) |
| invoegen | O(log n) |
| verwijderen | O(log n) |
Beiden handhaven balancering via rotaties — lokale O(1) herstructureringen die de BST-ordening behouden terwijl de hoogte wordt gereduceerd.
Gebalanceerde bomen ondersteunen geordende kaarten en sets in standaardbibliotheken (bijv. Java TreeMap, C++ std::map gebruiken rood-zwarte bomen), wat gesorteerde iteratie plus gegarandeerde logaritmische operaties oplevert.
Ze zijn het antwoord wanneer je de ordening van een BST en een harde prestatiegarantie tegen adversariale invoer nodig hebt.