बाइनरी सर्च ट्री का कार्यान्वयन

2024 लेखक: Angel Austin | [email protected]. अंतिम बार संशोधित: 2023-12-17 05:27

बाइनरी सर्च ट्री - एक संरचित डेटाबेस जिसमें नोड्स होते हैं, अन्य नोड्स के दो लिंक, दाएं और बाएं। नोड्स उस वर्ग का एक ऑब्जेक्ट है जिसमें डेटा है, और NULL वह चिन्ह है जो पेड़ के अंत को चिह्नित करता है।

इसे अक्सर बीएसटी के रूप में संदर्भित किया जाता है, जिसमें एक विशेष गुण होता है: रूट से बड़े नोड इसके दाईं ओर स्थित होते हैं, और छोटे वाले बाईं ओर स्थित होते हैं।

सामान्य सिद्धांत और शब्दावली

एक बाइनरी सर्च ट्री में, प्रत्येक नोड, रूट को छोड़कर, एक निर्देशित किनारे से एक नोड से दूसरे में जुड़ा होता है, जिसे पैरेंट कहा जाता है। उनमें से प्रत्येक को मनमाने ढंग से नोड्स से जोड़ा जा सकता है, जिन्हें बच्चे कहा जाता है। "बच्चों" के बिना नोड्स को पत्ते (बाहरी नोड्स) कहा जाता है। वे तत्व जो पत्तियाँ नहीं हैं, आन्तरिक कहलाते हैं। एक ही माता-पिता वाले नोड भाई-बहन हैं। सबसे ऊपरी नोड को रूट कहा जाता है। BST में, प्रत्येक नोड को एक तत्व असाइन करें और सुनिश्चित करें कि उनके पास उनके लिए एक विशेष गुण सेट है।

वृक्ष शब्दावली:

1. नोड की गहराई उसके रूट से परिभाषित किनारों की संख्या है।
2. नोड की ऊंचाई उसके किनारे से सबसे गहरे पत्ते तक परिभाषित किनारों की संख्या है।
3. पेड़ की ऊंचाई जड़ की ऊंचाई से निर्धारित होती है।
4. बाइनरी सर्च ट्री एक विशेष डिजाइन है, यह ऊंचाई और नोड्स की संख्या का सबसे अच्छा अनुपात प्रदान करता है।
5. ऊंचाई ज एन नोड्स के साथ अधिकतम ओ (लॉग एन)।

आप प्रत्येक स्तर पर नोड्स की गणना करके इसे आसानी से साबित कर सकते हैं, यह मानते हुए कि इसमें सबसे बड़ी संख्या है: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 इसे h के लिए हल करने पर h=O (log n) प्राप्त होता है।

लकड़ी के फायदे:

1. डेटा के संरचनात्मक संबंधों को प्रतिबिंबित करें।
2. पदानुक्रमों का प्रतिनिधित्व करते थे।
3. कुशल स्थापना और खोज सुनिश्चित करें।
4. पेड़ बहुत लचीले डेटा होते हैं, जिससे आप कम से कम प्रयास के साथ उप-वृक्षों को स्थानांतरित कर सकते हैं।

खोज विधि

सामान्य तौर पर, यह निर्धारित करने के लिए कि क्या कोई मान BST में है, इसके मूल में एक बाइनरी सर्च ट्री शुरू करें और निर्धारित करें कि क्या यह आवश्यकताओं को पूरा करता है:

• जड़ पर रहें;
• रूट के बायें उप-वृक्ष में हों;
• जड़ के दाहिने उपप्रकार में।

यदि कोई आधार रजिस्टर संतुष्ट नहीं है, तो संबंधित सबट्री में एक पुनरावर्ती खोज की जाती है। वास्तव में दो बुनियादी विकल्प हैं:

1. पेड़ खाली है - झूठी वापसी।
2. मान रूट नोड में है - सही लौटें।

यह ध्यान दिया जाना चाहिए कि एक विकसित स्कीमा के साथ एक बाइनरी सर्च ट्री हमेशा जड़ से पत्ती तक के रास्ते में खोजना शुरू करता है। सबसे खराब स्थिति में, यह पत्ते तक जाता है।इसलिए, सबसे खराब समय जड़ से पत्ती तक के सबसे लंबे रास्ते की लंबाई के समानुपाती होता है, जो कि पेड़ की ऊंचाई है। सामान्य तौर पर, यह तब होता है जब आपको यह जानने की आवश्यकता होती है कि पेड़ में संग्रहीत मूल्यों की संख्या के कार्य के रूप में देखने में कितना समय लगता है।

दूसरे शब्दों में, एक BST में नोड्स की संख्या और एक पेड़ की ऊंचाई के बीच एक संबंध होता है, जो उसके "आकार" पर निर्भर करता है। सबसे खराब स्थिति में, नोड्स में केवल एक बच्चा होता है, और एक संतुलित बाइनरी सर्च ट्री अनिवार्य रूप से एक लिंक्ड सूची है। उदाहरण के लिए:

50

/

10

15

30

/

20

इस पेड़ में 5 नोड्स और ऊंचाई=5 है। 16-19 और 21-29 की सीमा में मान खोजने के लिए रूट से लीफ तक निम्न पथ की आवश्यकता होगी (नोड जिसमें मान 20 है), अर्थात।, इसमें नोड्स की संख्या के अनुपात में समय लगेगा। अधिक से अधिक, उन सभी के 2 बच्चे हैं, और पत्तियाँ समान गहराई पर स्थित हैं।

इस बाइनरी सर्च ट्री में 7 नोड और ऊंचाई=3 है। सामान्य तौर पर, इस तरह के एक पेड़ (पूर्ण पेड़) की ऊंचाई लगभग लॉग 2 (एन) होगी, जहां एन पेड़ में नोड्स की संख्या है।. लॉग 2 (N) का मान उस संख्या (2) की संख्या है जिसे शून्य तक पहुंचने से पहले N को विभाजित किया जा सकता है।

संक्षेप में: BST में खोज करने के लिए सबसे खराब समय O (पेड़ की ऊंचाई) है। सबसे खराब स्थिति "रैखिक" पेड़ ओ (एन) है, जहां एन पेड़ में नोड्स की संख्या है। सबसे अच्छा, एक "पूर्ण" पेड़ O(log N) होता है।

बीएसटी बाइनरी इंसर्ट

सोच रहा हूँ कि कहाँ होना चाहिएनया नोड बीएसटी में स्थित है, आपको तर्क को समझने की जरूरत है, इसे वहां रखा जाना चाहिए जहां उपयोगकर्ता इसे ढूंढता है। इसके अलावा, आपको नियमों को याद रखने की जरूरत है:

1. डुप्लिकेट की अनुमति नहीं है, डुप्लीकेट मान डालने का प्रयास एक अपवाद देगा।
2. सार्वजनिक सम्मिलन विधि वास्तव में सम्मिलित करने के लिए एक सहायक पुनरावर्ती "सहायक" विधि का उपयोग करती है।
3. नया मान वाला एक नोड हमेशा बीएसटी में एक पत्ती के रूप में डाला जाता है।
4. सार्वजनिक सम्मिलन विधि शून्य हो जाती है, लेकिन सहायक विधि एक बीएसटीनोड लौटाती है। यह उस मामले को संभालने के लिए करता है जहां इसे पास किया गया नोड शून्य है।

सामान्य तौर पर, हेल्पर विधि इंगित करती है कि यदि मूल बाइनरी सर्च ट्री खाली है, तो परिणाम एक नोड वाला ट्री है। अन्यथा, परिणाम उसी नोड का सूचक होगा जिसे तर्क के रूप में पारित किया गया था।

बाइनरी एल्गोरिथम में हटाना

जैसा कि आप उम्मीद कर सकते हैं, किसी तत्व को हटाने में एक नोड ढूंढना शामिल है जिसमें हटाया जाने वाला मान होता है। इस कोड में कई चीजें हैं:

1. बीएसटी एक हेल्पर, ओवरलोडेड डिलीट मेथड का उपयोग करता है। यदि आप जिस तत्व की तलाश कर रहे हैं वह पेड़ में नहीं है, तो अंततः सहायक विधि को n==null के साथ बुलाया जाएगा। इसे एक त्रुटि नहीं माना जाता है, इस मामले में पेड़ बस नहीं बदलता है। डिलीट हेल्पर मेथड एक वैल्यू देता है - अपडेटेड ट्री के लिए एक पॉइंटर।
2. जब एक पत्ता हटा दिया जाता है, तो बाइनरी सर्च ट्री से हटाने से उसके माता-पिता के संबंधित चाइल्ड पॉइंटर को शून्य पर सेट कर दिया जाता है, या यदि हटाया जा रहा है तो रूट शून्य हो जाता हैनोड एक जड़ है और उसके कोई संतान नहीं है।
3. ध्यान दें कि डिलीट कॉल निम्न में से एक होना चाहिए: रूट=डिलीट (रूट, की), n.setLeft (डिलीट (n.getLeft (), की)), n.setRight (डिलीट (n. गेटराइट (), कुंजी))। इस प्रकार, तीनों मामलों में यह सही है कि हटाने का तरीका केवल शून्य लौटाता है।
4. जब हटाए जाने वाले मान वाले नोड की खोज सफल होती है, तो तीन विकल्प होते हैं: हटाए जाने वाले नोड को एक पत्ता (कोई बच्चा नहीं है), हटाए जाने वाले नोड में एक बच्चा होता है, इसमें दो होते हैं बच्चे।
5. जब हटाए जा रहे नोड में एक बच्चा होता है, तो आप बस इसे बच्चे से बदल सकते हैं, बच्चे को एक पॉइंटर लौटा सकते हैं।
6. यदि हटाए जाने वाले नोड में शून्य या 1 बच्चे हैं, तो डिलीट विधि रूट से उस नोड तक "पथ का अनुसरण" करेगी। तो सबसे खराब समय पेड़ की ऊंचाई के समानुपाती होता है, खोज और डालने दोनों के लिए।

यदि हटाए जाने वाले नोड के दो बच्चे हैं, तो निम्नलिखित कदम उठाए जाते हैं:

1. हटाए जाने वाले नोड का पता लगाएं, जड़ से उस तक के पथ का अनुसरण करें।
2. पत्ते के पथ के साथ जारी रखते हुए, दाएँ उपट्री में v का सबसे छोटा मान ज्ञात करें।
3. v के मान को पुनरावर्ती रूप से हटाएं, चरण 2 के समान पथ का अनुसरण करें।
4. इस प्रकार, सबसे खराब स्थिति में, जड़ से पत्ती तक का मार्ग दो बार किया जाता है।

ट्रैवर्स का क्रम

ट्रैवर्सल एक प्रक्रिया है जो एक पेड़ के सभी नोड्स पर जाती है। चूंकि सी बाइनरी सर्च ट्री एक गैर-रेखीय डेटा संरचना है, इसलिए कोई अद्वितीय ट्रैवर्सल नहीं है। उदाहरण के लिए, कभी-कभी कई ट्रैवर्सल एल्गोरिदमनिम्नलिखित दो प्रकारों में बांटा गया:

• गहराई पार करना;
• पहला पास।

चौड़ाई का एक ही प्रकार है - लेवल को बायपास करना। यह ट्रैवर्सल नीचे और बाएँ, ऊपर और दाएँ नोड्स के स्तर पर जाता है।

तीन अलग-अलग प्रकार की गहराई के क्रॉसिंग हैं:

1. प्रीआर्डर पास करना - पहले माता-पिता और फिर बाएँ और दाएँ बच्चे के पास जाएँ।
2. पासिंग इनऑर्डर - बाएं बच्चे का दौरा, फिर माता-पिता और दाएं बच्चे का।
3. पोस्टऑर्डर के बाद - बाएं बच्चे, फिर दाएं बच्चे, फिर माता-पिता का दौरा करें।

एक बाइनरी सर्च ट्री के चार ट्रैवर्सल के लिए उदाहरण:

1. प्रीऑर्डर - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
2. इनऑर्डर - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
3. पोस्टऑर्डर - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
4. स्तर क्रम - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

आंकड़ा उस क्रम को दिखाता है जिसमें नोड्स का दौरा किया जाता है। नंबर 1 किसी विशेष ट्रैवर्सल में पहला नोड है, और 7 अंतिम नोड है।

इन सामान्य ट्रैवर्सल को एकल एल्गोरिथ्म के रूप में दर्शाया जा सकता है, यह मानते हुए कि प्रत्येक नोड का तीन बार दौरा किया जाता है। यूलर टूर एक बाइनरी ट्री के चारों ओर घूमना है जहां प्रत्येक किनारे को एक दीवार के रूप में माना जाता है जिसे उपयोगकर्ता पार नहीं कर सकता है। इस वॉक में, प्रत्येक नोड को या तो बाईं ओर, या नीचे, या दाईं ओर देखा जाएगा। यूलर टूर, जो बाईं ओर के नोड्स पर जाता है, पूर्वसर्ग को बायपास करने का कारण बनता है। जब नीचे के नोड्स का दौरा किया जाता है, तो वे क्रम में ट्रैवर्स हो जाते हैं। और जब दाईं ओर के नोड्स का दौरा किया जाता है - प्राप्त करेंचरण-दर-चरण बाईपास।

नेविगेशन और डिबगिंग

पेड़ को नेविगेट करना आसान बनाने के लिए, ऐसे फ़ंक्शन बनाएं जो पहले जांच लें कि वे बाएं या दाएं बच्चे हैं या नहीं। नोड की स्थिति बदलने के लिए, पैरेंट नोड पर पॉइंटर तक आसान पहुंच होनी चाहिए। एक पेड़ को सही ढंग से लागू करना बहुत मुश्किल है, इसलिए आपको डिबगिंग प्रक्रियाओं को जानने और लागू करने की आवश्यकता है। कार्यान्वयन के साथ एक बाइनरी सर्च ट्री में अक्सर ऐसे पॉइंटर्स होते हैं जो वास्तव में यात्रा की दिशा का संकेत नहीं देते हैं।

यह सब पता लगाने के लिए, एक फ़ंक्शन का उपयोग किया जाता है जो यह जांचता है कि क्या पेड़ सही हो सकता है, और कई त्रुटियों को खोजने में मदद करता है। उदाहरण के लिए, यह जांचता है कि पैरेंट नोड एक चाइल्ड नोड है या नहीं। जोर देकर (is_wellformed (रूट)) कई त्रुटियों को समय से पहले पकड़ा जा सकता है। इस फ़ंक्शन के भीतर दिए गए कुछ ब्रेकप्वाइंट का उपयोग करके, आप यह भी निर्धारित कर सकते हैं कि कौन सा पॉइंटर गलत है।

फंक्शन Konsolenausgabe

यह फ़ंक्शन पूरे ट्री को कंसोल पर फ्लश करता है और इसलिए बहुत उपयोगी है। ट्री आउटपुट लक्ष्य को निष्पादित करने का क्रम है:

1. ऐसा करने के लिए, आपको सबसे पहले यह निर्धारित करना होगा कि नोड के माध्यम से कौन सी जानकारी आउटपुट होगी।
2. और आपको यह भी जानना होगा कि कितनी जगह छोड़नी है, इसका हिसाब देने के लिए पेड़ कितना चौड़ा और लंबा है।
3. निम्न कार्य पेड़ और प्रत्येक उपट्री के लिए इस जानकारी की गणना करते हैं। चूंकि आप केवल कंसोल लाइन को लाइन से लिख सकते हैं, इसलिए आपको ट्री लाइन को लाइन से प्रिंट करना होगा।
4. अब हमें वापस लेने का एक और तरीका चाहिएपूरा पेड़, न सिर्फ लाइन दर लाइन।
5. डंप फंक्शन की मदद से आप ट्री को पढ़ सकते हैं और जहां तक स्पीड का सवाल है, आउटपुट एल्गोरिथम में काफी सुधार कर सकते हैं।

हालांकि, बड़े पेड़ों पर इस फ़ंक्शन का उपयोग करना मुश्किल होगा।

कॉपी कंस्ट्रक्टर और डिस्ट्रक्टर

चूंकि एक पेड़ एक तुच्छ डेटा संरचना नहीं है, इसलिए कॉपी कंस्ट्रक्टर, डिस्ट्रक्टर और असाइनमेंट ऑपरेटर को लागू करना बेहतर है। विध्वंसक को पुनरावर्ती रूप से लागू करना आसान है। बहुत बड़े पेड़ों के लिए, यह "ढेर अतिप्रवाह" को संभाल सकता है। इस मामले में, इसे पुनरावृत्त रूप से तैयार किया जाता है। विचार सभी पत्तियों के सबसे छोटे मूल्य का प्रतिनिधित्व करने वाले पत्ते को हटाने का है, इसलिए यह पेड़ के बाईं ओर है। पहली पत्तियों को काटने से नए पत्ते बनते हैं, और पेड़ तब तक सिकुड़ता है जब तक कि उसका अस्तित्व समाप्त नहीं हो जाता।

कॉपी कंस्ट्रक्टर को पुनरावर्ती रूप से भी लागू किया जा सकता है, लेकिन अगर कोई अपवाद फेंका जाता है तो सावधान रहें। अन्यथा, पेड़ जल्दी भ्रमित और त्रुटि-प्रवण हो जाता है। इसलिए पुनरावृत्त संस्करण को प्राथमिकता दी जाती है। पुराने पेड़ और नए पेड़ के माध्यम से जाने का विचार है, जैसा कि आप विनाशक में करेंगे, पुराने पेड़ में मौजूद सभी नोड्स को क्लोन कर रहे हैं लेकिन नए नहीं हैं।

इस पद्धति के साथ, बाइनरी सर्च ट्री कार्यान्वयन हमेशा स्वस्थ अवस्था में होता है और अपूर्ण अवस्था में भी विनाशक द्वारा हटाया जा सकता है। यदि कोई अपवाद होता है, तो आपको केवल विध्वंसक को अर्ध-तैयार पेड़ को हटाने का निर्देश देना होगा। असाइनमेंट ऑपरेटरकॉपी और स्वैप का उपयोग करके आसानी से कार्यान्वित किया जा सकता है।

बाइनरी सर्च ट्री बनाना

इष्टतम बाइनरी सर्च ट्री अगर ठीक से प्रबंधित किया जाए तो अविश्वसनीय रूप से कुशल हैं। बाइनरी सर्च ट्री के लिए कुछ नियम:

1. एक पैरेंट नोड में अधिकतम 2 चाइल्ड नोड होते हैं।
2. बायां चाइल्ड नोड हमेशा पैरेंट नोड से छोटा होता है।
3. एक मान्य चाइल्ड नोड हमेशा पैरेंट नोड से बड़ा या उसके बराबर होता है।

वह सरणी जिसका उपयोग बाइनरी सर्च ट्री बनाने के लिए किया जाएगा:

1. सात मानों का आधार पूर्णांक सरणी क्रमबद्ध क्रम में।
2. सरणी में पहला मान 10 है, इसलिए ट्री बनाने में पहला कदम 10 रूट नोड बनाना है, जैसा कि यहां दिखाया गया है।
3. रूट नोड्स के एक सेट के साथ, अन्य सभी मान इस नोड के बच्चे होंगे। नियमों का हवाला देते हुए, पेड़ में 7 जोड़ने के लिए पहला कदम यह है कि इसकी तुलना रूट नोड से की जाए।
4. यदि मान 7, 10 से कम है, तो यह लेफ्ट चाइल्ड नोड बन जाएगा।
5. यदि मान 7, 10 से बड़ा या उसके बराबर है, तो वह दाईं ओर चला जाएगा। चूंकि 7 को 10 से कम माना जाता है, इसलिए इसे लेफ्ट चाइल्ड नोड के रूप में नामित किया गया है।
6. प्रत्येक तत्व के लिए पुनरावर्ती रूप से तुलना करें।
7. समान पैटर्न का अनुसरण करते हुए, सरणी में 14वें मान के विरुद्ध समान तुलना करें।
8. मान 14 की तुलना रूट नोड 10 से करना, यह जानते हुए कि 14 सही बच्चा है।
9. सरणी के माध्यम से चलना,20 पर आओ।
10. सरणी की तुलना 10 से करें, जो भी अधिक हो। इसलिए दाईं ओर जाएं और इसकी तुलना 14 से करें, वह 14 वर्ष से अधिक का है और उसके दाईं ओर कोई संतान नहीं है।
11. अब 1 का मान है। अन्य मानों के समान पैटर्न का अनुसरण करते हुए, 1 से 10 की तुलना करें, बाईं ओर जाएं और 7 की तुलना करें और अंत में 7वें नोड के 1 बाएं बच्चे से करें।
12. यदि मान 5 है, तो इसकी तुलना 10 से करें। चूँकि 5, 10 से कम है, बाईं ओर पास करें और इसकी तुलना 7 से करें।
13. यह जानते हुए कि 5, 7 से कम है, पेड़ को जारी रखें और 5 की तुलना 1 मान से करें।
14. यदि 1 की कोई संतान नहीं है और 5 1 से बड़ा है, तो 5 1 नोड का वैध बच्चा है।
15. आखिरकार ट्री में मान 8 डालें।
16. जब 8, 10 से कम हो, तो इसे बाईं ओर ले जाएँ और 7 से तुलना करें, 8, 7 से बड़ा है, इसलिए इसे दाईं ओर ले जाएँ और 8 को 7 का एक उचित बच्चा बनाते हुए पेड़ को पूरा करें।

इष्टतम बाइनरी सर्च ट्री के सरल लालित्य को प्राप्त करना और उसका मूल्यांकन करना। प्रोग्रामिंग में कई विषयों की तरह, बाइनरी सर्च ट्री की शक्ति डेटा को छोटे, संबंधित घटकों में हल करने की उनकी क्षमता से आती है। अब से, आप पूरे डेटासेट के साथ व्यवस्थित तरीके से काम कर सकते हैं।

संभावित बाइनरी खोज मुद्दे

बाइनरी सर्च ट्री महान हैं, लेकिन ध्यान में रखने के लिए कुछ चेतावनी हैं। वे आमतौर पर तभी प्रभावी होते हैं जब वे संतुलित हों। संतुलित वृक्ष वह वृक्ष होता है जिसमेंपेड़ में किसी भी नोड के सबट्री की ऊंचाई के बीच का अंतर अधिकतम एक है। आइए एक उदाहरण देखें जो नियमों को स्पष्ट करने में मदद कर सकता है। आइए कल्पना करें कि सरणी सॉर्ट करने योग्य के रूप में शुरू होती है।

यदि आप इस ट्री पर बाइनरी सर्च ट्री एल्गोरिथम चलाने का प्रयास करते हैं, तो यह ठीक वैसा ही प्रदर्शन करेगा जैसे कि वांछित मान मिलने तक यह केवल सरणी के माध्यम से पुनरावृत्ति कर रहा था। द्विआधारी खोज की शक्ति अवांछित मूल्यों को जल्दी से फ़िल्टर करने की क्षमता में निहित है। जब एक पेड़ संतुलित नहीं होगा, तो वह एक संतुलित पेड़ के समान लाभ नहीं देगा।

बाइनरी सर्च ट्री बनाते समय उपयोगकर्ता जिस डेटा के साथ काम कर रहा है, उसकी जांच करना बहुत महत्वपूर्ण है। पूर्णांकों को संतुलित करने के लिए बाइनरी सर्च ट्री को लागू करने से पहले आप सरणी रैंडमाइजेशन जैसे रूटीन को एकीकृत कर सकते हैं।

द्विआधारी खोज गणना उदाहरण

हमें यह निर्धारित करने की आवश्यकता है कि निम्नलिखित बाइनरी सर्च ट्री में 25 डालने पर किस प्रकार के पेड़ का परिणाम होगा:

10

/

/

5 15

/ /

/ /

2 12 20

जब एक पेड़ T में x डालते हैं जिसमें अभी तक x नहीं है, तो कुंजी x को हमेशा एक नए पत्ते में रखा जाता है। इसके संबंध में नया पेड़ इस तरह दिखेगा:

10

/

/

5 15

/ /

/ /

2 12 20

25

यदि आप निम्नलिखित बाइनरी सर्च ट्री में 7 डालते हैं तो आपको किस प्रकार का पेड़ मिलेगा?

10

/

/

5 15

/ /

/ /

2 12 20

उत्तर:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

किसी भी वस्तु को स्टोर करने के लिए बाइनरी सर्च ट्री का उपयोग किया जा सकता है। लिंक की गई सूची के बजाय बाइनरी सर्च ट्री का उपयोग करने का लाभ यह है कि यदि ट्री यथोचित रूप से संतुलित है और "रैखिक" की तुलना में "पूर्ण" पेड़ की तरह है, तो सम्मिलन, खोज और सभी डिलीट ऑपरेशन को चलाने के लिए लागू किया जा सकता है। हे(लॉग एन) समय।