ਇੱਕ ਸਾਧਾਰਨ BST ਇੱਕ ਲਿੰਕਡ ਲਿਸਟ ਵਿੱਚ ਖਰਾਬ ਹੋ ਸਕਦਾ ਹੈ (O(n) ਓਪਰੇਸਨ) ਜੇਕਰ ਚਾਬੀਆਂ ਸਾਈਡ ਬਰਡਰ ਆਦੇਸ਼ ਵਿੱਚ ਆਉਂਦੀਆਂ ਹਨ। ਆਪਣੇ ਆਪ ਨੂੰ ਸੰਤੁਲਿਤ ਕਰਨ ਵਾਲੇ BSTs — ਜਿਵੇਂ AVL ਅਤੇ ਲਾਲ-ਕਾਲੇ ਦਰਖਤ — ਸੂਚਕਾਂ ਨੂੰ ਸ਼ਾਮਲ ਕਰਨ/ਹਟਾਉਣ ਤੋਂ ਬਾਅਦ ਆਪਣੇ ਆਪ ਘੁੰਮਣ ਕਰਦੇ ਹਨ ਤਾਂ ਕਿ ਉਚਾਈ ~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 ਦਰਖਤ | ਲਾਲ-ਕਾਲਾ ਦਰਖਤ | |
|---|---|---|
| ਸੰਤੁਲਨ ਕਠੋਰਤਾ | ਸਖ਼ਤ (ਉਚਾਈ-ਸੰਤੁਲਿਤ) | ਢਿੱਲਾ |
| ਖੋਜ | ਤੇਜ਼ (ਛੋਟਾ) | ਥੋੜਾ ਹੌਲੀ |
| ਸ਼ਾਮਲ ਕਰੋ/ਹਟਾਓ | ਹੋਰ ਘੁੰਮਣ | ਘੱਟ ਘੁੰਮਣ |
| ਵਧੀਆ | ਪੜ੍ਹਨ-ਭਾਰੀ ਕਾਰਜ | ਲਿਖਣ-ਭਾਰੀ ਕਾਰਜ |
| ਓਪਰੇਸ਼ਨ | ਸਮਾਂ |
|---|---|
| ਖੋਜ | O(log n) |
| ਸ਼ਾਮਲ ਕਰੋ | O(log n) |
| ਹਟਾਓ | O(log n) |
ਦੋਵੇਂ ਘੁੰਮਣ ਰਾਹੀਂ ਸੰਤੁਲਨ ਰੱਖਦੇ ਹਨ — ਸਥਾਨਕ O(1) ਪੁਨਰ-ਸੰਗਠਨ ਜੋ BST ਆਦੇਸ਼ ਨੂੰ ਬਰਕਰਾਰ ਰੱਖਦੇ ਹਨ ਜਦਕਿ ਉਚਾਈ ਘਟਾਉਂਦੇ ਹਨ।
ਸੰਤੁਲਿਤ ਦਰਖਤ ਮਾਨਕ ਲਾਇਬ੍ਰੇਰੀਜ਼ ਵਿੱਚ ਕ੍ਰਮਬੱਧ ਨਕਸ਼ਿਆਂ ਅਤੇ ਸੈੱਟਾਂ ਨੂੰ ਸਮਰਥਨ ਕਰਦੇ ਹਨ (ਉਦਾ. Java TreeMap, C++ std::map ਲਾਲ-ਕਾਲੇ ਦਰਖਤ ਵਰਤਦੇ ਹਨ), ਕ੍ਰਮਬੱਧ ਦੁਹਰਾਓ ਅਤੇ ਗ੍ਰਹਿ ਕੀਤੇ ਲੌਗੀਥਮਿਕ ਓਪਰੇਸ਼ਨ ਦਿੰਦੇ ਹਨ।
ਇਹ ਜਵਾਬ ਹੈ ਜਦੋਂ ਤੁਹਾਨੂੰ BST ਦਾ ਆਦੇਸ਼ ਅਤੇ ਵਿਰੋਧੀ ਇਨਪੁਟ ਦੇ ਵਿਰੁੱਧ ਸਖ਼ਤ ਕਾਰਕਰਦਗੀ ਦੀ ਗ੍ਰਹਿ ਦੋਵਾਂ ਦੀ ਜ਼ਰੂਰਤ ਹੋਵੇ।
ਵਿਸਤ੍ਰਿਤ ਜਵਾਬਾਂ ਨਾਲ IT ਇੰਟਰਵਿਊ ਸਵਾਲਾਂ ਦੀ ਇੱਕ ਲਾਇਬ੍ਰੇਰੀ — ਜੂਨੀਅਰ ਤੋਂ ਸੀਨੀਅਰ ਤੱਕ।
ਦਾਨ ਕਰੋ