WAVL ट्री: Difference between revisions

From Vigyanwiki
(Created page with "कंप्यूटर विज्ञान में, WAVL ट्री या कमजोर AVL ट्री एक स्व-संतुलन द्विआ...")
 
No edit summary
 
(12 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में, WAVL ट्री या कमजोर AVL ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष]] है। WAVL पेड़ों का नाम AVL पेड़ों के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज पेड़ है, और यह AVL पेड़ों और लाल-काले पेड़ों दोनों से निकटता से संबंधित है, जो सभी रैंक संतुलित पेड़ों के एक सामान्य ढांचे में आते हैं।
[[कंप्यूटर विज्ञान]] में, '''डब्ल्यूएवीएल (WAVL) ट्री''' या कमजोर एवीएल ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष|स्व-संतुलन द्विआधारी विवृत्त ट्री]] है। डब्ल्यूएवीएल ट्री का नाम एवीएल ट्री  के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज ट्री है, और यह एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित है, जो सभी पद संतुलित ट्री के एक सामान्य ढांचे में आते हैं। अन्य संतुलित बाइनरी खोज ट्री की तरह, डब्ल्यूएवीएल ट्री प्रति संचालन {{math|''O''(log ''n'')}} समय में सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं। <ref name="hst15"/>
अन्य संतुलित बाइनरी खोज पेड़ों की तरह, WAVL पेड़ समय पर सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं {{math|''O''(log ''n'')}} प्रति ऑपरेशन.<ref name="gt">{{citation|contribution=4.4 Weak AVL Trees|pages=130–138|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015}}.</ref><ref name="hst15"/>


WAVL पेड़ों को AVL पेड़ों और लाल-काले पेड़ों दोनों के कुछ सर्वोत्तम गुणों को संयोजित करने के लिए डिज़ाइन किया गया है। लाल-काले पेड़ों की तुलना में एवीएल पेड़ों का एक फायदा यह है कि वे अधिक संतुलित होते हैं: उनकी अधिकतम ऊंचाई होती है <math>\log_{\varphi} n\approx 1.44\log_2 n</math> (एक पेड़ के लिए {{mvar|n}} डेटा आइटम, कहां <math>\varphi</math> [[सुनहरा अनुपात]] है), जबकि लाल-काले पेड़ों की अधिकतम ऊंचाई अधिक होती है, <math>2\log_2 n</math>. यदि एक WAVL ट्री केवल सम्मिलन का उपयोग करके, बिना हटाए बनाया जाता है, तो इसमें वही छोटी ऊँचाई होती है जो AVL ट्री में होती है। दूसरी ओर, लाल-काले पेड़ों को अपने पेड़ों के कम पुनर्गठन में एवीएल पेड़ों की तुलना में फायदा होता है। एवीएल पेड़ों में, प्रत्येक विलोपन के लिए पेड़ के घूर्णन संचालन की एक लघुगणकीय संख्या की आवश्यकता हो सकती है, जबकि लाल-काले पेड़ों में सरल विलोपन संचालन होते हैं जो केवल पेड़ के घूर्णन की एक स्थिर संख्या का उपयोग करते हैं। WAVL पेड़, लाल-काले पेड़ों की तरह, केवल पेड़ के घूर्णन की एक स्थिर संख्या का उपयोग करते हैं, और स्थिरांक लाल-काले पेड़ों की तुलना में भी बेहतर है।<ref name="gt"/><ref name="hst15"/>
डब्ल्यूएवीएल ट्री को एवीएल ट्री लाल-काले ट्री दोनों के कुछ सर्वोत्तम गुणों को संयोजित करने के लिए प्ररूपित किया गया है। लाल-काले ट्री  की तुलना में एवीएल ट्री का एक लाभ यह है कि वे अधिक संतुलित होते हैं: उनकी अधिकतम ऊंचाई होती है <math>\log_{\varphi} n\approx 1.44\log_2 n</math>, जबकि लाल-काले ट्री की अधिकतम ऊंचाई <math>2\log_2 n</math> से अधिक होती है, यदि एक डब्ल्यूएवीएल ट्री केवल सम्मिलन का उपयोग करके, बिना हटाए बनाया जाता है, तो इसमें वही छोटी ऊँचाई होती है जो एवीएल ट्री में होती है। दूसरी ओर, लाल-काले ट्री  को अपने ट्री  के कम पुनर्गठन में एवीएल ट्री के सापेक्ष में लाभ होता है। एवीएल ट्री में, प्रत्येक विलोपन के लिए ट्री के घूर्णन संचालन की एक लघुगणकीय संख्या की आवश्यकता हो सकती है, जबकि लाल-काले ट्री में सरल विलोपन संचालन होते हैं जो केवल ट्री  के घूर्णन की एक स्थिर संख्या का उपयोग करते हैं। डब्ल्यूएवीएल ट्री, लाल-काले ट्री की तरह, केवल ट्री के घूर्णन की एक स्थिर संख्या का उपयोग करते हैं, और स्थिरांक लाल-काले ट्री के सापेक्ष में भी उत्तम है।<ref name="gt">{{citation|contribution=4.4 Weak AVL Trees|pages=130–138|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015}}.</ref><ref name="hst15"/>


WAVL वृक्षों की शुरुआत किसके द्वारा की गई थी? {{harvtxt|Haeupler|Sen|Tarjan|2015}}. उन्हीं लेखकों ने एवीएल पेड़ों, डब्ल्यूएवीएल पेड़ों और लाल-काले पेड़ों के बारे में एक सामान्य दृष्टिकोण भी प्रदान किया, क्योंकि ये सभी एक प्रकार के रैंक-संतुलित पेड़ हैं।<ref name="hst15">{{citation
<ref name="hst15">{{citation
  | last1 = Haeupler | first1 = Bernhard
  | last1 = Haeupler | first1 = Bernhard
  | last2 = Sen | first2 = Siddhartha
  | last2 = Sen | first2 = Siddhartha
Line 16: Line 15:
  | url = http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf     
  | url = http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf     
  | volume = 11
  | volume = 11
  | year = 2015}}.</ref>
  | year = 2015}}.</ref>डब्ल्यूएवीएल ट्री एवीएल ट्रीज को कहा जाता है जिन्हें {{harvtxt|ह्युप्लर|सेन |टारजन |2015}}. ने प्रस्तुत किया था। उन्ही लेखकों ने एवीएल ट्रीज, एवीएल ट्रीज और लाल-काले ट्रीज को पद -संतुलित ट्री के एक प्रकार के रूप में प्रदर्शित किया।
== पद संतुलित ट्रीज की रूपरेखा ==
अलग-अलग बाइनरी सर्च ट्री में डालने/हटाने और संतुलन कला विधि  के लिए अलग-अलग कला विधि  होते हैं, जिससे व्यवस्थित अध्ययन करना मुश्किल हो जाता है। लेखक {{harvtxt|ह्युप्लर|सेन |टारजन |2015}} पद  बाइनरी ट्री को परिभाषित करके बाइनरी सर्च ट्री के अध्ययन को एकीकृत करने के लिए पद संतुलित ट्री फ्रेमवर्क का परिचय दें, और प्रत्येक बाइनरी सर्च ट्री पद फलन पर लागू विशिष्ट बाधाओं का पालन करता है। ध्यान दें कि फ़्रेमवर्क उन कला विधि को निर्दिष्ट नहीं करता है जिनमें ये ट्री लागू किए जाते हैं।


पद बाइनरी ट्री एक बाइनरी ट्री है जहां प्रत्येक बिन्दु  x एक पद  r(x) से जुड़ा होता है। परंपरा के अनुसार, खाली बिन्दु  की पद  -1 होती है। एक बिन्दु  x के लिए जो रूट नहीं है, पद अंतर है <math>r(p(x))-r(x)</math>, और यदि पद अंतर i है तो ऐसे बिन्दु को आई-चाइल्ड कहा जाता है। एक बिन्दु <math>i,j</math> प्रकार का होता है। यदि इसके बाएं चाइल्ड और दाएं चाइल्ड की पद का अंतर i और j है।


== रैंक संतुलित वृक्ष रूपरेखा ==
इसके साथ, हम अतिरिक्त नियम परिभाषित कर सकते हैं, जो विभिन्न ट्री से मेल खाते हैं:
अलग-अलग बाइनरी सर्च ट्री में डालने/हटाने और संतुलन एल्गोरिदम के लिए अलग-अलग एल्गोरिदम होते हैं, जिससे व्यवस्थित अध्ययन करना मुश्किल हो जाता है। के लेखक {{harvtxt|Haeupler|Sen|Tarjan|2015}} रैंक बाइनरी ट्री को परिभाषित करके बाइनरी सर्च ट्री के अध्ययन को एकीकृत करने के लिए रैंक संतुलित ट्री फ्रेमवर्क का परिचय दें, और प्रत्येक बाइनरी सर्च ट्री रैंक फ़ंक्शन पर लागू विशिष्ट बाधाओं का पालन करता है। ध्यान दें कि फ़्रेमवर्क उन एल्गोरिदम को निर्दिष्ट नहीं करता है जिनमें ये पेड़ लागू किए जाते हैं।


रैंक बाइनरी ट्री एक बाइनरी ट्री है जहां प्रत्येक नोड x एक रैंक r(x) से जुड़ा होता है। परंपरा के अनुसार, खाली नोड की रैंक -1 होती है। एक नोड x के लिए जो रूट नहीं है, रैंक अंतर है <math>r(p(x))-r(x)</math>, और यदि रैंक अंतर i है तो ऐसे नोड को आई-चाइल्ड कहा जाता है। एक नोड प्रकार का होता है <math>i,j</math> यदि इसके बाएं बच्चे और दाएं बच्चे की रैंक का अंतर i और j है (आदेश की परवाह किए बिना)।
* एवीएल नियम, जो एवीएल ट्री से मेल खाता है: प्रत्येक बिन्दु प्रकार 1,1 या 1,2 का है।
* 2-3 नियम, जो बाइनराइज्ड 2-3 ट्री से मेल खाता है: प्रत्येक बिन्दु 0,1 या 1,1 प्रकार का है, और 0-चाइल्ड का कोई भी माता-पिता 0-बच्चा नहीं है।
* लाल काला नियम, जो लाल-काले ट्री से मेल खाता है: सभी पद अंतर 0 या 1 हैं, और 0-चाइल्ड का कोई भी माता-पिता 0-बच्चा नहीं है। ध्यान दें कि लाल-काला नियम 0,0 प्रकार के बिन्दु की अनुमति देकर 2-3 नियम को सामान्य बनाता है।


इसके साथ, हम अतिरिक्त नियम परिभाषित कर सकते हैं, जो विभिन्न पेड़ों से मेल खाते हैं:
अब तक ये सभी नियम बाएँ बिन्दु और दाएँ बिन्दु के लिए सममित हैं। ऐसी समरूपता को तोड़कर, यह अन्य नियमों को जन्म देता है:


* AVL नियम, जो AVL ट्री से मेल खाता है: प्रत्येक नोड प्रकार 1,1 या 1,2 का है।
* दाएँ-झुकाव वाला दो-तीन नियम, जो दाएँ झुकाव वाले द्विअर्थी 2-3 ट्री से मेल खाता है: प्रत्येक बिन्दु 1,1 या 0,1 है, 0-चाइल्ड का कोई भी माता-पिता 0-बच्चा नहीं है, और कोई 0-बच्चा नहीं है।
* 2-3 नियम, जो बाइनराइज्ड 2-3 ट्री से मेल खाता है: प्रत्येक नोड 0,1 या 1,1 प्रकार का है, और 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है।
* वाम-झुकाव वाला दो-तीन नियम, जो बायीं ओर झुके हुए द्विअर्थी 2-3 ट्री से मेल खाता है: प्रत्येक बिन्दु 1,1 या 0,1 है, 0-चाइल्ड  का कोई भी माता-पिता 0-बच्चा नहीं है, और कोई 0-बच्चा नहीं है सही है।
* लाल काला नियम, जो लाल-काले पेड़ से मेल खाता है: सभी रैंक अंतर 0 या 1 हैं, और 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है। ध्यान दें कि लाल-काला नियम 0,0 प्रकार के नोड की अनुमति देकर 2-3 नियम को सामान्य बनाता है।
* दाएं-झुकाव वाला लाल-काला नियम, जो रेफ्ट-झुकाव वाले लाल-काले ट्री  से मेल खाता है: 0-चाइल्ड का कोई भी माता-पिता 0-बच्चा नहीं है, और 0,1-बिन्दु  का कोई 0-बच्चा नहीं बचा है।
* वाम-झुकाव वाले लाल-काले नियम, जो वाम-झुकाव वाले लाल-काले ट्री  से मेल खाता है: सभी पद 0 या 1 हैं, 0-चाइल्ड का कोई भी माता-पिता 0-बच्चा नहीं है, और 0 का कोई 0-बच्चा नहीं है, 1-बिन्दु सही है.


अब तक ये सभी नियम बाएँ नोड और दाएँ नोड के लिए सममित हैं। ऐसी समरूपता को तोड़कर, यह अन्य नियमों को जन्म देता है:
कमज़ोर एवीएल ट्री कमज़ोर एवीएल नियम द्वारा परिभाषित किया गया है:


* दाएँ-झुकाव वाला दो-तीन नियम, जो दाएँ झुकाव वाले द्विअर्थी 2-3 पेड़ से मेल खाता है: प्रत्येक नोड 1,1 या 0,1 है, 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और कोई 0-बच्चा नहीं है शेष है।
* कमजोर एवीएल नियम: सभी पद  अंतर 1 या 2 हैं, और सभी लीफ बिन्दु की पद  0 है।
* वाम-झुकाव वाला दो-तीन नियम, जो बायीं ओर झुके हुए द्विअर्थी 2-3 पेड़ से मेल खाता है: प्रत्येक नोड 1,1 या 0,1 है, 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और कोई 0-बच्चा नहीं है सही है।
* दाएं-झुकाव वाला लाल-काला नियम, जो रेफ्ट-झुकाव वाले लाल-काले पेड़ से मेल खाता है: 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और 0,1-नोड का कोई 0-बच्चा नहीं बचा है।
* वाम-झुकाव वाले लाल-काले नियम, जो वाम-झुकाव वाले लाल-काले पेड़ से मेल खाता है: सभी रैंक अंतर 0 या 1 हैं, 0-बच्चे का कोई भी माता-पिता 0-बच्चा नहीं है, और 0 का कोई 0-बच्चा नहीं है, 1-नोड सही है.


कमज़ोर AVL वृक्ष को कमज़ोर AVL नियम द्वारा परिभाषित किया गया है:
ध्यान दें कि कमजोर एवीएल ट्री 2,2 प्रकार के बिन्दु की अनुमति देकर एवीएल ट्री को सामान्यीकृत करता है। एक साधारण प्रमाण से पता चलता है कि एक कमजोर एवीएल ट्री को इस तरह से रंगा जा सकता है जो लाल-काले ट्री का प्रतिनिधित्व करता है। तो एक अर्थ में, कमजोर एवीएल ट्री एवीएल ट्री और लाल-काले ट्री  के गुणों को जोड़ता है।
 
* कमजोर एवीएल नियम: सभी रैंक अंतर 1 या 2 हैं, और सभी लीफ नोड्स की रैंक 0 है।
 
ध्यान दें कि कमजोर AVL ट्री 2,2 प्रकार के नोड की अनुमति देकर AVL ट्री को सामान्यीकृत करता है। एक साधारण प्रमाण से पता चलता है कि एक कमजोर एवीएल पेड़ को इस तरह से रंगा जा सकता है जो लाल-काले पेड़ का प्रतिनिधित्व करता है। तो एक अर्थ में, कमजोर AVL वृक्ष AVL वृक्ष और लाल-काले वृक्ष के गुणों को जोड़ता है।


==परिभाषा==
==परिभाषा==
आमतौर पर बाइनरी सर्च ट्री की तरह, WAVL ट्री में दो प्रकार के [[नोड (कंप्यूटर विज्ञान)]] का संग्रह होता है: आंतरिक नोड्स और बाहरी नोड्स। एक आंतरिक नोड एक डेटा आइटम संग्रहीत करता है, और अपने माता-पिता से जुड़ा होता है (निर्दिष्ट रूट नोड को छोड़कर जिसका कोई माता-पिता नहीं है) और पेड़ में ठीक दो बच्चों, बाएं बच्चे और दाएं बच्चे से जुड़ा होता है। एक बाहरी नोड में कोई डेटा नहीं होता है, और उसका लिंक केवल पेड़ में उसके मूल नोड से होता है। इन नोड्स को एक बाइनरी ट्री बनाने के लिए व्यवस्थित किया जाता है, ताकि किसी भी आंतरिक नोड के लिए {{mvar|x}} बाएँ और दाएँ बच्चों के माता-पिता {{mvar|x}} हैं {{mvar|x}} अपने आप। बाहरी गांठें पेड़ की पत्तियाँ बनाती हैं।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, Section 2.3 Trees, pp. 68–83.</ref> डेटा आइटम को ट्री में इस तरह व्यवस्थित किया जाता है कि ट्री का एक [[इनऑर्डर ट्रैवर्सल]] डेटा आइटम को क्रमबद्ध क्रम में सूचीबद्ध करता है।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, Chapter 3 Binary Search Trees, pp. 89–114.</ref>
सामान्यतः बाइनरी सर्च ट्री की तरह, डब्ल्यूएवीएल ट्री में दो प्रकार के [[नोड (कंप्यूटर विज्ञान)|बिन्दु]] का संग्रह होता है: आंतरिक बिन्दु और बाहरी बिन्दु एक आंतरिक बिन्दु एक डेटा वस्तु संग्रहीत करता है, और अपने माता-पिता से जुड़ा होता है और ट्री में ठीक दो बच्चों, बाएं चाइल्ड और दाएं चाइल्ड से जुड़ा होता है। एक बाहरी बिन्दु में कोई डेटा नहीं होता है, और उसका लिंक केवल ट्री में उसके मूल बिन्दु से होता है। इन बिन्दु  को एक बाइनरी ट्री बनाने के लिए व्यवस्थित किया जाता है, ताकि किसी भी आंतरिक बिन्दु के लिए {{mvar|x}} बाएँ और {{mvar|x}} दाएँ बच्चों के माता-पिता हैं । बाहरी गांठें ट्री की पत्तियाँ बनाती हैं।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, Section 2.3 Trees, pp. 68–83.</ref> डेटा वस्तु को ट्री में इस तरह व्यवस्थित किया जाता है कि ट्री का एक [[इनऑर्डर ट्रैवर्सल]] डेटा वस्तु  को क्रमबद्ध क्रम में सूचीबद्ध करता है।<ref>{{harvtxt|Goodrich|Tamassia|2015}}, Chapter 3 Binary Search Trees, pp. 89–114.</ref>डब्ल्यूएवीएल ट्री को अन्य प्रकार के बाइनरी सर्च ट्री से जो अलग करता है, वह है इसका पद  का उपयोग। ये प्रत्येक बिन्दु से जुड़े नंबर हैं, जो बिन्दु से उसके सबसे दूर के पत्ते के वंशज तक की दूरी का अनुमान प्रदान करते हैं। एवीएल ट्री के विपरीत, जहां पद को बिन्दु की ऊंचाई के समान परिभाषित किया जाता है, डब्ल्यूएवीएल ट्री  में पद  हमेशा ऊंचाई के बराबर नहीं होती है। बिन्दु  x के पद अंतर को x के मूल पद  और x के पद  के बीच अंतर के रूप में परिभाषित किया गया है। पदो को निम्नलिखित गुणों का पालन करना आवश्यक है:<ref name="gt"/><ref name="hst15"/>*बाहरी-बिन्दु गुण: प्रत्येक बाहरी बिन्दु की पद {{math|0}} होती है <ref>In this we follow {{harvtxt|Goodrich|Tamassia|2015}}. In the version described by {{harvtxt|Haeupler|Sen|Tarjan|2015}}, the external nodes have rank &minus;1. This variation makes very little difference in the operations of WAVL trees, but it causes some minor changes to the formula for converting WAVL trees to red–black trees.</ref>
WAVL ट्री को अन्य प्रकार के बाइनरी सर्च ट्री से जो अलग करता है, वह है इसका रैंक का उपयोग। ये प्रत्येक नोड से जुड़े नंबर हैं, जो नोड से उसके सबसे दूर के पत्ते के वंशज तक की दूरी का अनुमान प्रदान करते हैं।
*पद -अंतर संपत्ति: यदि एक गैर-रूट बिन्दु में पद  है {{mvar|r}}, तो उसके माता-पिता का पद या तो होना चाहिए {{math|''r'' + 1}} या {{math|''r'' + 2}}. दूसरे शब्दों में, किसी भी गैर-रूट बिन्दु के लिए पद  अंतर 1 या 2 है।<ref name="gt" />*आंतरिक-बिन्दु गुण: दो बाहरी बच्चों वाले एक आंतरिक बिन्दु की पद  बिल्कुल 1 होनी चाहिए।
एवीएल पेड़ों के विपरीत, जहां रैंक को नोड्स की ऊंचाई के समान परिभाषित किया जाता है, डब्ल्यूएवीएल पेड़ों में रैंक हमेशा ऊंचाई के बराबर नहीं होती है। नोड x के रैंक अंतर को x के मूल रैंक और x के रैंक के बीच अंतर के रूप में परिभाषित किया गया है। रैंकों को निम्नलिखित गुणों का पालन करना आवश्यक है:<ref name="gt"/><ref name="hst15"/>*बाहरी-नोड संपत्ति: प्रत्येक बाहरी नोड की रैंक होती है {{math|0}}<ref>In this we follow {{harvtxt|Goodrich|Tamassia|2015}}. In the version described by {{harvtxt|Haeupler|Sen|Tarjan|2015}}, the external nodes have rank &minus;1. This variation makes very little difference in the operations of WAVL trees, but it causes some minor changes to the formula for converting WAVL trees to red–black trees.</ref>
*रैंक-अंतर संपत्ति: यदि एक गैर-रूट नोड में रैंक है {{mvar|r}}, तो उसके माता-पिता का पद या तो होना चाहिए {{math|''r'' + 1}} या {{math|''r'' + 2}}. दूसरे शब्दों में, किसी भी गैर-रूट नोड के लिए रैंक अंतर 1 या 2 है।<ref name="gt" />*आंतरिक-नोड संपत्ति: दो बाहरी बच्चों वाले एक आंतरिक नोड की रैंक बिल्कुल 1 होनी चाहिए।


==संचालन==
==संचालन==


===खोज रहा हूँ===
===अन्वेषण===
कुंजी की तलाश की जा रही है {{mvar|k}} WAVL ट्री में किसी भी संतुलित बाइनरी सर्च ट्री डेटा संरचना के समान ही है। कोई पेड़ की जड़ से शुरुआत करता है और फिर बार-बार तुलना करता है {{mvar|k}} रूट से पथ पर प्रत्येक नोड पर संग्रहीत डेटा आइटम के साथ, नोड के बाएं बच्चे के पथ का अनुसरण करते हुए {{mvar|k}} नोड पर मान से छोटा है या इसके बजाय सही बच्चे के पथ का अनुसरण कर रहा है {{mvar|k}} नोड पर मान से बड़ा है। जब एक नोड जिसका मान बराबर हो {{mvar|k}} पहुँच जाता है, या कोई बाहरी नोड पहुँच जाता है, खोज रुक जाती है।<ref name="gt-search">{{harvtxt|Goodrich|Tamassia|2015}}, Section 3.1.2 Searching in a Binary Search Tree, pp. 95–96.</ref>
डब्ल्यूएवीएल ट्री में एक कुंजी{{mvar|k}} की खोज करना किसी भी संतुलित द्विआधार सर्च ट्री डेटा संरचना की तरह होता है। पहले ट्री की रूट पर प्रारंभ करें, और फिर मूल से रूट तक के पथ पर प्रत्येक बिन्दु पर संग्रहीत डेटा वस्तु के साथ {{mvar|k}} की तुलना करें, जब  {{mvar|k}} बिन्दु  के मान से छोटा हो तो वर्तमान बिन्दु के बाएं बच्चे के पथ का पालन करें और जब {{mvar|k}} बिन्दु के मान से बड़ा हो तो वर्तमान बिन्दु के दाएं बच्चे के पथ का पालन करें। <ref name="gt-search">{{harvtxt|Goodrich|Tamassia|2015}}, Section 3.1.2 Searching in a Binary Search Tree, pp. 95–96.</ref>जब किसी बिन्दु के मान के बराबर कीमत के साथ एक बिन्दु तक पहुंचा जाता है या एक बाह्य बिन्दु  तक पहुंचा जाता है, खोज समाप्त हो जाती है।<ref name="gt-search"/>यदि खोज किसी आंतरिक बिन्दु पर रुकती है, तो कुंजी {{mvar|k}} मिल गई है। यदि विपरीत होता है, तो खोज किसी बाह्य बिन्दु पर रुकती है, तो {{mvar|k}} को किस स्थान पर सम्मिलित किया जाएगा, वह स्थान मिल गया है।
यदि खोज किसी आंतरिक नोड पर रुकती है, तो कुंजी {{mvar|k}} मिल गया है। यदि इसके बजाय, खोज किसी बाहरी नोड पर रुक जाती है, तो वह स्थिति कहाँ है {{mvar|k}} डाला जाएगा (यदि डाला गया हो) मिल गया है।<ref name="gt-search"/>
===सम्मिलन===
कुंजी के साथ एक आंतरिक बिन्दु सम्मिलित करना {{mvar|k}} डब्ल्यूएवीएल ट्री में खोज की आवश्यकता होती है {{mvar|k}} ट्री  में, एक बाहरी बिन्दु  पर समाप्त होता है, फिर दो बाहरी बच्चों के साथ नए आंतरिक बिन्दु  के साथ उस बाहरी बिन्दु  का प्रतिस्थापन होता है, और अंत में ट्री  का पुनर्संतुलन होता है। पुनर्संतुलन चरण या तो ऊपर से नीचे या नीचे से ऊपर किया जा सकता है,<ref name="hst15"/>लेकिन पुनर्संतुलन का निचला-ऊपर संस्करण वह है जो एवीएल ट्री से सबसे अधिक मेल खाता है।<ref name="gt"/><ref name="hst15"/>


डब्ल्यूएवीएल ट्री में कुंजी {{mvar|k}} के साथ एक आंतरिक बिन्दु को सम्मिलित करने के लिए, ट्री में {{mvar|k}} की खोज की जाती है, जो एक बाह्य बिन्दु  पर समाप्त होती है, फिर उस बाह्य बिन्दु को दो बाह्य बच्चों के साथ नए आंतरिक बिन्दु से प्रतिस्थापित किया जाता है, और अंततः ट्री को संतुलित किया जाता है। संतुलनाधीन चरण को शीर्ष से नीचे तक या नीचे से शीर्ष तक किया जा सकता है लेकिन संतुलित करने का नीचे से शीर्ष तक वर्जन एवीएल ट्री के सबसे समीप होता है।


===सम्मिलन===
पद -अंतर पर विचार करके नीचे-ऊपर पुनर्संतुलन प्रारंभ होता है एक बिन्दु के बीच प्रारंभ में नया डाला गया बिन्दु और उसके अभिभावक. यदि कोई माता-पिता नहीं है, तो संतुलन बहाल हो जाता है। पहले प्रविष्टि प्रारंभ  हुई, पैरेंट और बिन्दु के बीच पद -अंतर 1 या 2,था लेकिन उपट्री के कारण वह अंतर 1 से कम हो गया है बिन्दु पर जड़ें लंबी हो गई हैं। यदि नये पद -अंतर के बीच पैरेंट और बिन्दु 1 है, संतुलन बहाल हो गया है। अन्यथा, यदि भाई-बहन, माता-पिता की दूसरी संतान, के साथ पद -अंतर 1 है माता-पिता, माता-पिता को बढ़ावा दें - वृद्धि करके इसकी पद  बढ़ाएं इसके और इसके प्रत्येक चाइल्ड के बीच पद -अंतर और जारी है नए बिन्दु के रूप में पुराने पैरेंट के साथ पुनर्संतुलन करता है।
कुंजी के साथ एक आंतरिक नोड सम्मिलित करना {{mvar|k}} WAVL ट्री में खोज की आवश्यकता होती है {{mvar|k}} पेड़ में, एक बाहरी नोड पर समाप्त होता है, फिर दो बाहरी बच्चों के साथ नए आंतरिक नोड के साथ उस बाहरी नोड का प्रतिस्थापन होता है, और अंत में पेड़ का पुनर्संतुलन होता है। पुनर्संतुलन चरण या तो ऊपर से नीचे या नीचे से ऊपर किया जा सकता है,<ref name="hst15"/>लेकिन पुनर्संतुलन का निचला-ऊपर संस्करण वह है जो एवीएल पेड़ों से सबसे अधिक मेल खाता है।<ref name="gt"/><ref name="hst15"/>


रैंक-अंतर पर विचार करके नीचे-ऊपर पुनर्संतुलन शुरू होता है
अंत में, बिन्दु और सिबलिंग के लिए 0 और 2 के पद -अंतर के साथ, एक या पद -अंतर से संबंधित समायोजन के साथ, दो ट्री  घूर्णन,संतुलन बहाल कर सकता है. बिन्दु का बीच वाला बच्चा कुंजी वाला होता है बिन्दु और पैरेंट की कुंजियों के बीच यदि उसके लिए पद -अंतर है
एक नोड के बीच - प्रारंभ में नया डाला गया नोड - और उसके
चाइल्ड और बिन्दु 2 है, बिन्दु को ट्री और पेरेंट में ऊपर ले जाने के लिए घुमाएँ नीचे, फिर माता-पिता को पदावनत करें - समायोजित करके इसकी पद  कम करें इसके चारों ओर पद -अंतर - और संतुलन बहाल हो जाता है। अन्यथा,चाइल्ड को ऊपर और बिन्दु को नीचे ले जाने के लिए घुमाएँ, फिर दोबारा घुमाएँ चाइल्ड को ऊपर और माता-पिता को नीचे ले जाएँ। चाइल्ड को प्रमोट करो, डिमोट करो बिन्दु और पैरेंट, और संतुलन बहाल हो जाता है।
अभिभावक. यदि कोई माता-पिता नहीं है, तो संतुलन बहाल हो जाता है। पहले
प्रविष्टि शुरू हुई, पैरेंट और नोड के बीच रैंक-अंतर 1 या था
2, लेकिन उपवृक्ष के कारण वह अंतर 1 से कम हो गया है
नोड पर जड़ें लंबी हो गई हैं। यदि नये रैंक-अंतर के बीच
पैरेंट और नोड 1 है, संतुलन बहाल हो गया है। अन्यथा, यदि
भाई-बहन, माता-पिता की दूसरी संतान, के साथ रैंक-अंतर 1 है
माता-पिता, माता-पिता को बढ़ावा दें - वृद्धि करके इसकी रैंक बढ़ाएं
इसके और इसके प्रत्येक बच्चे के बीच रैंक-अंतर - और जारी है
नए नोड के रूप में पुराने पैरेंट के साथ पुनर्संतुलन।


अंत में, नोड और सिबलिंग के लिए 0 और 2 के रैंक-अंतर के साथ, एक या
इस प्रकार, कुल मिलाकर, सम्मिलन प्रक्रिया में एक खोज, नए बिन्दु की एक निरंतर संख्या का निर्माण, पद  परिवर्तनों की एक लघुगणकीय संख्या और ट्री के घूर्णन की एक निरंतर संख्या सम्मिलित होती है।<ref name="gt" /><ref name="hst15" />
रैंक-अंतर से संबंधित समायोजन के साथ, दो वृक्ष घूर्णन,
संतुलन बहाल कर सकता है. नोड का बीच वाला बच्चा कुंजी वाला होता है
नोड और पैरेंट की कुंजियों के बीच। यदि उसके लिए रैंक-अंतर है
चाइल्ड और नोड 2 है, नोड को पेड़ और पेरेंट में ऊपर ले जाने के लिए घुमाएँ
नीचे, फिर माता-पिता को पदावनत करें - समायोजित करके इसकी रैंक कम करें
इसके चारों ओर रैंक-अंतर - और संतुलन बहाल हो जाता है। अन्यथा,
बच्चे को ऊपर और नोड को नीचे ले जाने के लिए घुमाएँ, फिर दोबारा घुमाएँ
बच्चे को ऊपर और माता-पिता को नीचे ले जाएँ। बच्चे को प्रमोट करो, डिमोट करो
नोड और पैरेंट, और संतुलन बहाल हो जाता है।


इस प्रकार, कुल मिलाकर, सम्मिलन प्रक्रिया में एक खोज, नए नोड्स की एक निरंतर संख्या का निर्माण, रैंक परिवर्तनों की एक लघुगणकीय संख्या और पेड़ के घूर्णन की एक निरंतर संख्या शामिल होती है।<ref name="gt"/><ref name="hst15"/>




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


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