ჩვეულებრივი BST-ი შეიძლება გადაიზარდოს კავშირიან სიაში (O(n) ოპერაციები), თუ გასაღებები დალაგებული თანმიმდევრობით გამოჩნდება. თვითრეგულირებელი BST-ები — როგორიცაა AVL და წითელი-შავი ხეები — ავტომატურად ახდენენ ნოდების ბრუნვას ჩამატებისა და წაშლის შემდეგ, რომ სიმაღლე დაახლოებით დარჩეს, რაც აგარანტებს ოპერაციებს.
log nUnbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL ხე | წითელი-შავი ხე | |
|---|---|---|
| ბალანსის მკაცრობა | მკაცრი (სიმაღლით დაბალანსებული) | უფრო სუსტი |
| ძებნა | უფრო სწრაფი (უფრო მოკლე) | ოდნავ ნელი |
| ჩამატება/წაშლა | მეტი ბრუნვა | ნაკლები ბრუნვა |
| საუკეთესო | წაკითხვის ინტენსიური დატვირთვისთვის | ჩაწერის ინტენსიური დატვირთვისთვის |
| ოპერაცია | დრო |
|---|---|
| ძებნა | O(log n) |
| ჩამატება | O(log n) |
| წაშლა | O(log n) |
ორივე ინარჩუნებს ბალანსს ბრუნვების საშუალებით — ლოკალური O(1) რესტრუქტურიზაციები, რომლებიც ინახავენ BST-ის რიგს, ხოლო სიმაღლე ამცირებენ.
დაბალანსებული ხეები საბუშაოდ გამოიყენება დახარისხებული რუკები და კომპლექტები სტანდარტული ბიბლიოთეკებში (მაგალითად, Java TreeMap, C++ std::map იყენებენ წითელი-შავი ხეებს), რაც იძლევა დახარისხებულ გამეორებას სამაგიეროდ გარანტირებული ლოგარითმული ოპერაციებით.
ისინი წარმოადგენენ პასუხს, როცა საჭიროა BST-ის დახარისხება და მკაცრი შესრულების გარანტია დაჩქარებული შეყვანის წინააღმდეგ.