સાદો BST લિંક્ડ લિસ્ટમાં અધોગતિ પામી શકે છે (O(n) કામગીરી) જો કી સૉર્ટેડ ક્રમમાં આવે. સ્વ-સંતુલન BSTs — જેમ કે AVL અને લાલ-કાળું વૃક્ષ — insertion/deletion પછી નોડ્સને આપમેળે ફરીથી ગોઠવે છે જેથી ઊંચાઈ ~log n રહે, કામગીરીની ખાતરી આપે છે.
સાદો BST લિંક્ડ લિસ્ટમાં અધોગતિ પામી શકે છે (O(n) કામગીરી) જો કી સૉર્ટેડ ક્રમમાં આવે. સ્વ-સંતુલન BSTs — જેમ કે AVL અને લાલ-કાળું વૃક્ષ — insertion/deletion પછી નોડ્સને આપમેળે ફરીથી ગોઠવે છે જેથી ઊંચાઈ ~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 વૃક્ષ | લાલ-કાળું વૃક્ષ | |
|---|---|---|
| સંતુલન કડક | કઠોર (ઊંચાઈ-સંતુલિત) | નમ્ર |
| શોધ | વધુ ઝડપી (ટૂંકી) | થોડી ધીમી |
| Insert/delete | વધુ રિક્રિયાઓ | ઓછી રિક્રિયાઓ |
| સર્વોત્તમ | વાંચન-ભારી કાર્યોભાર | લેખન-ભારી કાર્યોભાર |
| કામગીરી | સમય |
|---|---|
| search | O(log n) |
| insert | O(log n) |
| delete | O(log n) |
બંને રિક્રિયાઓ દ્વારા સંતુલન જાળવે છે — સ્થાનિક O(1) પુનર્રચના જે BST ક્રમ સુરક્ષિત રાખે છે જ્યારે ઊંચાઈ ઘટાડે છે.
સંતુલિત વૃક્ષો પ્રમાણભૂત લાઈબ્રેરીમાં ક્રમાંકિત નકશા અને સમૂહને સમર્થન આપે છે (ઉદા., Java TreeMap, C++ std::map લાલ-કાળું વૃક્ષ વાપરે છે), સૉર્ટેડ પુનરાવર્તન અને ખાતરી આપેલ લોગરિધમિક કામગીરી આપે છે.
તેઓ જવાબ છે જ્યારે તમને BST ક્રમ અને દુર્વાવજનક ઇનપુટ વિરુદ્ધ કઠોર કામગીરી ગ્યારંટી જોઈએ.
વિગતવાર જવાબો સાથે IT ઇન્ટરવ્યૂ પ્રશ્નોની લાઇબ્રેરી — જુનિયરથી સિનિયર સુધી.
દાન કરો