Obyčejný BST se může degenerovat na propojenou seznam (operace O(n)), pokud klíče přicházejí v seřazeném pořadí. Samoregulovací BST — jako AVL a červeno-černé stromy — automaticky otáčejí uzly po vkládání/mazání, aby udržely výšku ~log n, což garantuje operace O(log n).
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL strom | Červeno-černý strom | |
|---|---|---|
| Přísnost vyvážení | přísné (vyváženo podle výšky) | volnější |
| Vyhledávání | rychlejší (kratší) | mírně pomalejší |
| Vkládání/mazání | více rotací | méně rotací |
| Ideální pro | zatížení orientované na čtení | zatížení orientované na zápis |
| Operace | Čas |
|---|---|
| vyhledávání | O(log n) |
| vkládání | O(log n) |
| mazání | O(log n) |
Obě udržují rovnováhu pomocí rotací — lokálních přeskupení O(1), která zachovávají pořadí BST a zároveň snižují výšku.
Vyvážené stromy podporují seřazené mapy a sady ve standardních knihovnách (např. Java TreeMap, C++ std::map používají červeno-černé stromy), což poskytuje seřazenou iteraci a garantované logaritmické operace.
Jsou odpovědí, když potřebujete seřazení BST a tvrdou záruku výkonu proti nepřátelskému vstupu.