ایک سادہ BST اگر keys ترتیب سے آئیں تو linked list میں خراب ہو سکتا ہے (O(n) operations)۔ Self-balancing BSTs — جیسے AVL اور red-black trees — خود بخود rotate کرتے ہیں insertions/deletions کے بعد تاکہ height ~log n رہے، O(log n) operations کی ضمانت دیتے ہیں۔
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL tree | Red-black tree | |
|---|---|---|
| توازن کی سختی | سخت (height-balanced) | کمزور |
| Lookups | تیز (مختصر) | قدرے سست |
| Insert/delete | مزید rotations | کم rotations |
| بہترین | read-heavy workloads | write-heavy workloads |
| Operation | Time |
|---|---|
| search | O(log n) |
| insert | O(log n) |
| delete | O(log n) |
دونوں rotations کے ذریعے توازن برقرار رکھتے ہیں — مقامی O(1) restructurings جو BST ordering کو محفوظ رکھتے ہوئے height کو کم کرتے ہیں۔
متوازن درخت standard libraries میں ordered maps اور sets کی بنیاد ہیں (مثال کے طور پر Java TreeMap، C++ std::map red-black trees استعمال کرتے ہیں)، sorted iteration اور guaranteed logarithmic operations فراہم کرتے ہیں۔
یہ جواب ہے جب آپ کو BST کی ordering اور adversarial input کے خلاف سخت کارکردگی کی ضمانت درکار ہو۔