సాధారణ 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 ఆర్డరింగ్ను సంరక్షిస్తూ ఎత్తును తగ్గిస్తాయి.
సమతుల్య చెట్లు ప్రామాణిక లైబ్రరీలలో ఆర్డర్ చేయిన మ్యాప్లు మరియు సెట్లను మద్దతు ఇస్తాయి (ఉదా జావా TreeMap, C++ std::map రెడ్-బ్లాక్ చెట్లను ఉపయోగిస్తాయి), దీని ఫలితంగా సార్టు చేయిన ఇటరేషన్ మరియు గ్యారంటీ చేయిన లాగరిథమిక్ ఆపరేషన్లు లభిస్తాయి.
BST ఆర్డరింగ్ మరియు విపరీతమైన ఇన్పుట్కు వ్యతిరేకంగా గట్టి పనితీరు గ్యారంటీ అవసరమైనప్పుడు అవి సమాధానం.
జూనియర్ నుండి సీనియర్ వరకు వివరణాత్మక సమాధానాలతో IT ఇంటర్వ్యూ ప్రశ్నల లైబ్రరీ.
విరాళం