ஒரு சாதாரண BST சரிசெய்யப்பட்ட வரிசையில் விசைகள் வந்தால் ஒரு இணைக்கப்பட்ட பட்டியலாக சீரழிந்துவிடலாம் (O(n) செயல்பாடுகள்). சுய-சமநிலையுள்ள BST கள் — AVL மற்றும் சிவப்பு-கருப்பு மரங்களை போன்ற — செருக்குதல்/நீக்குதல் விசையை பின் நியூட்ரோ தானாக ஆ rotateCircle செய்து உயரத்தை ~ வைத்திருந்து செயல்பாடுகளை உறுதிப்படுத்துகிறது.
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 மரம் | சிவப்பு-கருப்பு மரம் | |
|---|---|---|
| சமநிலை கடுமை | கடுமை (உயரம் சமநிலையுள்ள) | தளர்வு |
| தேடல்கள் | வேகமான (குறுகிய) | சற்று மெதுவான |
| செருக்குதல்/நீக்குதல் | மிக rotations | குறைந்த rotations |
| சிறந்த | பாக்கா-பொலிவான வேலையை | எழுதுதல்-பொலிவான வேலையை |
| செயல்பாடு | நேரம் |
|---|---|
| தேடல் | O(log n) |
| செருக்குதல் | O(log n) |
| நீக்குதல் | O(log n) |
இரண்டும் rotations மூலம் சமநிலையை பராமரிக்கின்றன — உள்ளூர் O(1) மறுசீரமைப்புகள் BST வரிசையை பாதுகாக்கும் போது உயரத்தை குறைக்கின்றன.
சமநிலையுள்ள மரங்கள் நிலையான நூலகங்களில் வரிசைப்படுத்தப்பட்ட வரைபடங்கள் மற்றும் தொகுப்புகளை ஆதரிக்கிறது (எ.கா. Java TreeMap, C++ std::map சிவப்பு-கருப்பு மரங்களை பயன்படுத்துக), வரிசைப்படுத்தப்பட்ட iteration மற்றும் உறுதிப்படுத்தப்பட்ட logarithmic செயல்பாடுகளை வழங்குகிறது.
BST இன் வரிசை மற்றும் எதிரி உள்ளீட்டுக்கு எதிரான கடினமான செயல்திறன் உறுதிமொழி தேவைப்படும் போது இவை பதிலாக உள்ளன.