बाइनरी पेड़ में नोड हटाने के लिए, हमें नोड खोजना होगा। न्यूनतम ओ (लॉग एन) और अधिकतम ओ (एन) में यह संभव है। नोड के आधार पर, हमें पॉइंटर्स को पुनर्व्यवस्थित करना होगा। हम उस समय की जटिलता की गणना कैसे करते हैं।बाइनरी पेड़ में नोड को हटाने की समय जटिलता क्या है
अधिकांश जटिलता नोड की खोज कर रही है। एक बार यह पाया गया है - जब तक कि पैरेंट नोड बनाए रखा जाता है-यह नोड को हटाने के लिए केवल कुछ और असाइनमेंट है। तो यह एक निरंतर आदेश है।
यह इस बात पर निर्भर करता है कि आप कैसे हटा रहे हैं। सबसे आम तरीके में नोड के उत्तराधिकारी को ढूंढना शामिल है, फिर उस उत्तराधिकारी के साथ नोड को बदलना शामिल है। यह ओ (एच) में किया जा सकता है, जहां पे पेड़ की ऊंचाई है। सबसे बुरे मामले में यह ओ (एन) है, लेकिन एक संतुलित पेड़ में सबसे खराब मामला ओ (एलजी एन) है।
आपको "अधिकतम ओ (एन)" के रूप में सबसे खराब खोज समय कहां मिल रहा है? यह बीएसटी में कभी नहीं होना चाहिए। सबसे बुरी स्थिति में, यह खोज और हटाने के लिए अधिकतम ओ (एच) होना चाहिए, जहां पेड़ की ऊंचाई 'एच' है। यह helpful article देखें।
ओ (एच) एक रोगजनक रूप से अपमानजनक पेड़ में ओ (एन) हो सकता है। – templatetypedef
हाँ सबसे अच्छा मामले जटिलता है ओ (logn) (जब अच्छी तरह से संतुलित) और
सबसे खराब स्थिति जटिलता हे है (एन)
1 - 2 - 3 - BST विलोपन के साथ 4
लेकिन मुख्य समस्या (हिबार्ड हटाना) यह है कि यह सममित नहीं है। कई प्रविष्टि और हटाने के बाद बीएसटी कम संतुलन बन गया। शोधकर्ताओं ने साबित किया कि पर्याप्त लंबे समय तक यादृच्छिक डालने और पेड़ की ऊंचाई को हटाने के बाद वर्ग (एन) बन जाता है। तो अब प्रत्येक ऑपरेशन (सर्च, डालने, डिलीट) sqrt (n) समय लेगा जो ओ (लॉगन) की तुलना में अच्छा नहीं है।
यह बीएसटी के लिए कुशल सममित हटाने के लिए बहुत लंबी स्थिति (लगभग 50 वर्षों) खुली समस्या है। गारंटीकृत संतुलित पेड़ के लिए, हमें रेडब्लैक ट्री इत्यादि का उपयोग करना होगा
+1, अच्छा और संक्षिप्त। –