क्यों यह महत्वपूर्ण है कि एक द्विआधारी पेड़यह क्यों महत्वपूर्ण है कि एक बाइनरी पेड़ संतुलित हो?</p> <pre><code>A B C D E </code></pre> <p>यह एक वैध द्विआधारी पेड़ है, लेकिन अब सबसे संचालन कर रहे हैं हे (एन) के बजाय हे:
संतुलित किया जानाएक द्विआधारी पेड़ के संतुलन संपत्ति कहा जाता तिरछापन द्वारा नियंत्रित है। यदि एक पेड़ अधिक skewed है, तो बाइनरी पेड़ के एक तत्व का उपयोग करने के लिए समय जटिलता बढ़ जाती है। एक पेड़
1 /\ 2 3 \ \ 7 4 \ 5 \ 6
कहो ऊपर भी एक द्विआधारी पेड़ है, लेकिन सही विषम है। इसमें 7 तत्व हैं, इसलिए एक आदर्श बाइनरी पेड़ की आवश्यकता है ओ (लॉग 7) = 3 लुकअप। लेकिन आपको सबसे खराब मामले में एक और स्तर गहरी = 4 लुकअप जाने की जरूरत है। तो यहाँ skewness एक स्थिर 1 है। लेकिन विचार करें कि पेड़ हजारों नोड्स है। उस मामले में skewness और भी अधिक महत्वपूर्ण होगा। इसलिए बाइनरी पेड़ को संतुलित रखना महत्वपूर्ण है।
लेकिन फिर तिरछापन एक यादृच्छिक द्विआधारी पेड़ के probablity विश्लेषण के रूप में बहस का विषय है पता चलता है कि एक random binary tree with n elements is 4.3 log n की औसत गहराई। तो यह वास्तव में तिरछापन बनाम संतुलन की बात है।
एक और दिलचस्प बात यह है कि कंप्यूटर वैज्ञानिकों ने भी स्केवनेस में लाभ प्राप्त किया है और skew heap
नामक एक तिरछे डेटास्ट्रक्चर का प्रस्ताव दिया हैएक पेड़ है कि इस तरह दिखता है कल्पना कीजिए है (एलजी एन)।
लॉग (एन) खोज समय सुनिश्चित करने के लिए, आप प्रत्येक शाखा में 2 से नीचे स्तर नोड्स की कुल संख्या को विभाजित करने की जरूरत है। उदाहरण के लिए, यदि आपके पास रैखिक पेड़ है, तो रूट से पत्ती नोड तक कभी भी शाखा नहीं लेते हैं, तो खोज समय एक लिंक्ड सूची में रैखिक होगा।
एक बेहद असंतुलित पेड़, उदाहरण के लिए एक पेड़ जहां सभी नोड बाईं ओर जुड़े होते हैं, इसका मतलब है कि आप अभी भी आखिरी एक ढूंढने से पहले हर एक नोड से खोज करते हैं, जो पेड़ का बिंदु नहीं है और इसका कोई लाभ नहीं है एक लिंक्ड सूची पर। पेड़ को संतुलित करना ओ (एन) के विपरीत बेहतर खोज समय ओ (लॉग (एन)) के लिए बनाता है।