WAVL ट्री - Revision history

Manidh at 09:14, 28 July 2023

2023-07-28T09:14:44Z

← Older revision		Revision as of 14:44, 28 July 2023
Line 111:		Line 111:
	==संदर्भ==		==संदर्भ==
	{{reflist}}		{{reflist}}
	~~[[Category: बाइनरी पेड़]] [[Category: पेड़ खोजें]]~~



	~~[[Category: Machine Translated Page]]~~
	[[Category:Created On 10/07/2023]]		[[Category:Created On 10/07/2023]]
	[[Category:Vigyan Ready]]		[[Category:Machine Translated Page]]
			[[Category:Pages with script errors]]
			[[Category:Templates Vigyan Ready]]
			[[Category:पेड़ खोजें]]
			[[Category:बाइनरी पेड़]]

Indicwiki: 12 revisions imported from :alpha:WAVL_ट्री

2023-07-28T04:53:02Z

12 revisions imported from alpha:WAVL_ट्री

← Older revision	Revision as of 10:23, 28 July 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-07-27T05:17:20Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 10:47, 27 July 2023
Line 117:		Line 117:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 10/07/2023]]		[[Category:Created On 10/07/2023]]
			[[Category:Vigyan Ready]]

alpha>Abhishek at 08:52, 17 July 2023

2023-07-17T08:52:47Z

← Older revision		Revision as of 14:22, 17 July 2023
Line 1:		Line 1:
	[[कंप्यूटर विज्ञान]] में, डब्ल्यूएवीएल (WAVL) ट्री या कमजोर एवीएल ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष\|स्व-संतुलन द्विआधारी विवृत्त ट्री]] है। डब्ल्यूएवीएल ट्री का नाम एवीएल ट्री के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज ट्री है, और यह एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित है, जो सभी पद संतुलित ट्री के एक सामान्य ढांचे में आते हैं। अन्य संतुलित बाइनरी खोज ट्री की तरह, डब्ल्यूएवीएल ट्री प्रति संचालन {{math\|''O''(log ''n'')}} समय में सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं। <ref name="hst15"/>		[[कंप्यूटर विज्ञान]] में, '''डब्ल्यूएवीएल (WAVL) ट्री''' या कमजोर एवीएल ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष\|स्व-संतुलन द्विआधारी विवृत्त ट्री]] है। डब्ल्यूएवीएल ट्री का नाम एवीएल ट्री के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज ट्री है, और यह एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित है, जो सभी पद संतुलित ट्री के एक सामान्य ढांचे में आते हैं। अन्य संतुलित बाइनरी खोज ट्री की तरह, डब्ल्यूएवीएल ट्री प्रति संचालन {{math\|''O''(log ''n'')}} समय में सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं। <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"/>		डब्ल्यूएवीएल ट्री को एवीएल ट्री लाल-काले ट्री दोनों के कुछ सर्वोत्तम गुणों को संयोजित करने के लिए प्ररूपित किया गया है। लाल-काले ट्री की तुलना में एवीएल ट्री का एक लाभ यह है कि वे अधिक संतुलित होते हैं: उनकी अधिकतम ऊंचाई होती है <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"/>

alpha>Abhishek at 08:52, 17 July 2023

2023-07-17T08:52:24Z

← Older revision		Revision as of 14:22, 17 July 2023
Line 1:		Line 1:
	[[कंप्यूटर विज्ञान]] में, डब्ल्यूएवीएल ट्री या कमजोर एवीएल ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष\|स्व-संतुलन द्विआधारी विवृत्त ट्री]] है। डब्ल्यूएवीएल ट्री का नाम एवीएल ट्री के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज ट्री है, और यह एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित है, जो सभी पद संतुलित ट्री के एक सामान्य ढांचे में आते हैं। अन्य संतुलित बाइनरी खोज ट्री की तरह, डब्ल्यूएवीएल ट्री प्रति संचालन {{math\|''O''(log ''n'')}} समय में सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं। <ref name="hst15"/>		[[कंप्यूटर विज्ञान]] में, डब्ल्यूएवीएल (WAVL) ट्री या कमजोर एवीएल ट्री एक [[स्व-संतुलन द्विआधारी खोज वृक्ष\|स्व-संतुलन द्विआधारी विवृत्त ट्री]] है। डब्ल्यूएवीएल ट्री का नाम एवीएल ट्री के नाम पर रखा गया है, जो एक अन्य प्रकार का संतुलित खोज ट्री है, और यह एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित है, जो सभी पद संतुलित ट्री के एक सामान्य ढांचे में आते हैं। अन्य संतुलित बाइनरी खोज ट्री की तरह, डब्ल्यूएवीएल ट्री प्रति संचालन {{math\|''O''(log ''n'')}} समय में सम्मिलन, विलोपन और खोज संचालन को संभाल सकते हैं। <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"/>		डब्ल्यूएवीएल ट्री को एवीएल ट्री लाल-काले ट्री दोनों के कुछ सर्वोत्तम गुणों को संयोजित करने के लिए प्ररूपित किया गया है। लाल-काले ट्री की तुलना में एवीएल ट्री का एक लाभ यह है कि वे अधिक संतुलित होते हैं: उनकी अधिकतम ऊंचाई होती है <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"/>

alpha>Abhishek: Abhishek moved page WAVL पेड़ to WAVL ट्री without leaving a redirect

2023-07-17T08:51:06Z

Abhishek moved page WAVL पेड़ to WAVL ट्री without leaving a redirect

← Older revision	Revision as of 14:21, 17 July 2023
(No difference)

alpha>Shyamunayak: /* कम्प्यूटेशनल जटिलता */

2023-07-17T06:20:20Z

कम्प्यूटेशनल जटिलता

← Older revision		Revision as of 11:50, 17 July 2023
Line 74:		Line 74:

	यह महत्वपूर्ण है कि एवीएल ट्री में कई स्तरों पर घुमाने वाले चक्रवात होने के कारण हटाने के परिणाम को डब्ल्यूएवीएल ट्री में किए गए चक्रवात और पद परिवर्तनों के साथ तुलना किया जाए। दूसरी छवि में, मान 12 वाले बिन्दु को हटा दिया गया है, इसके बाद दाएं घूमाने और सभी बाह्य बिन्दु को पद शून्य के रूप में निर्धारित किया गया है।		यह महत्वपूर्ण है कि एवीएल ट्री में कई स्तरों पर घुमाने वाले चक्रवात होने के कारण हटाने के परिणाम को डब्ल्यूएवीएल ट्री में किए गए चक्रवात और पद परिवर्तनों के साथ तुलना किया जाए। दूसरी छवि में, मान 12 वाले बिन्दु को हटा दिया गया है, इसके बाद दाएं घूमाने और सभी बाह्य बिन्दु को पद शून्य के रूप में निर्धारित किया गया है।
	[[File:FibonacciTreeWRanks.png\|thumb\|~~पद ों~~ के साथ फाइबोनैचि ट्री ]] [[File:Fibonacci Tree after Delete.png\|thumb\|हटाने के बाद पद के साथ फाइबोनैचि ट्री ]]		[[File:FibonacciTreeWRanks.png\|thumb\|पदो के साथ फाइबोनैचि ट्री ]] [[File:Fibonacci Tree after Delete.png\|thumb\|हटाने के बाद पद के साथ फाइबोनैचि ट्री ]]

	==कम्प्यूटेशनल जटिलता==		==कम्प्यूटेशनल जटिलता==

alpha>Shyamunayak: /* एवीएल ट्री */

2023-07-17T06:18:44Z

एवीएल ट्री

← Older revision		Revision as of 11:48, 17 July 2023
Line 85:		Line 85:

	===एवीएल ट्री ===		===एवीएल ट्री ===
	एवीएल ट्री एक प्रकार का संतुलित बाइनरी सर्च ट्री है जिसमें प्रत्येक आंतरिक बिन्दु के दो बच्चों की ऊंचाई अधिकतम एक से भिन्न होनी चाहिए।<ref>{{harvtxt\|Goodrich\|Tamassia\|2015}}, Section 4.2 AVL Trees, pp. 120–125.</ref> किसी बाहरी बिन्दु की ऊंचाई शून्य है, और किसी भी आंतरिक बिन्दु की ऊंचाई हमेशा उसके दो बच्चों की ऊंचाई से एक प्लस अधिक होती है। इस प्रकार, एवीएल ट्री की ऊंचाई फलन डब्ल्यूएवीएल ट्री की बाधाओं का पालन करती है, और हम प्रत्येक बिन्दु की ऊंचाई को उसके पद के रूप में उपयोग करके किसी भी एवीएल ट्री को डब्ल्यूएवीएल ट्री में परिवर्तित कर सकते हैं।<ref name="gt"/><ref name="hst15"/>		<ref name="gt"/><ref name="hst15"/>

	एवीएल ट्री और डब्ल्यूएवीएल ट्री के बीच मुख्य अंतर तब उत्पन्न होता है जब एक बिन्दु ~~में समान पद या ऊंचाई वाले~~ दो ~~चाइल्ड~~ होते ~~हैं।~~ एवीएल ट्री में, यदि एक बिन्दु ~~{{mvar\|~~x~~}} के एक ही कद~~ के दो ~~चाइल्ड~~ हैं ~~{{mvar\|~~h}} एक दूसरे के ~~रूप में~~, तो की ऊंचाई ~~{{mvar\|x}} बिलकुल होना चाहिए {{math\|''~~h'' + 1~~}}.~~ इसके विपरीत, डब्ल्यूएवीएल ट्री में, यदि एक ~~node {{mvar\|~~x~~}} के एक ही पद~~ के दो ~~चाइल्ड~~ हैं ~~{{mvar\|~~r}} एक दूसरे के ~~रूप में~~, ~~फिर की~~ पद ~~{{mvar\|x}}~~ या तो ~~किया जा सकता है {{math\|''~~r'' + 1}} या ~~{{math\|''~~r'' + 2~~}}. ऐसा इसलिए~~ है ~~क्योंकि~~ डब्ल्यूएवीएल ट्री में ~~पद पूरी तरह~~ से ~~ऊंचाई के~~ बराबर नहीं है। पद ों में ~~इस अधिक लचीलेपन से~~ संरचनाओं में ~~भी अधिक लचीलापन आता~~ है: कुछ डब्ल्यूएवीएल ट्री ~~को उनके~~ पद ों को संशोधित करके भी एवीएल ट्री में नहीं ~~बनाया~~ जा सकता है, क्योंकि ~~उनमें~~ ऐसे बिन्दु सम्मिलित होते हैं जिनके बच्चों की ऊंचाई एक से अधिक ~~भिन्न होती~~ है।~~<ref name="hst15"/>हालाँकि~~, हम कह सकते हैं कि सभी एवीएल ट्री डब्ल्यूएवीएल ट्री हैं। एवीएल ट्री ~~बिना किसी प्रकार के बिन्दु वाले~~ डब्ल्यूएवीएल ट्री हैं ~~जिनके दोनों बच्चों की~~ पद ~~में~~ अंतर 2 है।<ref name="gt" />		एक एवीएल ट्री एक प्रकार का संतुलित द्विआधार सर्च ट्री है जिसमें प्रत्येक आंतरिक बिन्दु के दो बच्चों की ऊंचाइयों में अधिकतम एक तक का अंतर होना चाहिए। बाह्य बिन्दु की ऊंचाई शून्य होती है, और किसी भी आंतरिक बिन्दु की ऊंचाई हमेशा उसके दो बच्चों की ऊंचाइयों की अधिकतम ऊंचाई प्लस एक होती है। इस प्रकार, एक एवीएल ट्री की ऊंचाई की फलन एक डब्ल्यूएवीएल ट्री की नियमों का पालन करती है, और हम प्रत्येक बिन्दु की ऊंचाई को उसकी पद के रूप में उपयोग करके किसी भी एवीएल ट्री को एक डब्ल्यूएवीएल ट्री में बदल सकते हैं।<ref name="hst15" /><ref name="gt" />

			एक एवीएल ट्री और डब्ल्यूएवीएल ट्री के बीच मुख्य अंतर उत्पन्न होता है जब एक बिन्दु के पास दो बच्चे होते हैं जिनकी ऊंचाई या पद समान होती है। एक एवीएल ट्री में, यदि एक बिन्दु x के पास दो ऐसे बच्चे होते हैं जिनकी ऊंचाई h होती है और एक दूसरे के समान होती है, तो x की ऊंचाई केवल h + 1 होनी चाहिए। इसके विपरीत, एक डब्ल्यूएवीएल ट्री में, यदि एक बिन्दु x के पास दो ऐसे बच्चे होते हैं जिनकी पद r होती है और एक दूसरे के समान होती है, तो x का पद या तो r + 1 या r + 2 हो सकता है। इसका कारण यह है कि डब्ल्यूएवीएल ट्री में ऊंचाई से सामान्यतः बराबर नहीं होती है। पद में अधिकतम परिवर्तिता के कारण, संरचनाओं में अधिकतम परिवर्तिता होती है: कुछ डब्ल्यूएवीएल ट्री ऐसी हो सकती हैं जिन्हें पद को संशोधित करके भी एवीएल ट्री में बदला नहीं जा सकता है, क्योंकि इसमें ऐसे बिन्दु सम्मिलित होते हैं जिनके बच्चों की ऊंचाई में एक से अधिक अंतर होता है। यद्यपि, हम कह सकते हैं कि सभी एवीएल ट्री डब्ल्यूएवीएल ट्री हैं। एवीएल ट्री डब्ल्यूएवीएल ट्री होते हैं जिनमें पद अंतर 2 वाले बिन्दु के प्रकार नहीं होते हैं।।<ref name="gt" />

			यदि एक डब्ल्यूएवीएल ट्री केवल सम्मिलन संचालन का उपयोग करके बनाया गया है, तो इसकी संरचना समान सम्मिलन अनुक्रम द्वारा बनाए गए एवीएल ट्री की संरचना के समान होगी, और इसकी पद संबंधित एवीएल ट्री की पद के समान होगी। केवल विलोपन कार्यों के माध्यम से ही एक डब्ल्यूएवीएल ट्री एक एवीएल ट्री से भिन्न हो सकता है। विशेष रूप से इसका तात्पर्य यह है कि केवल सम्मिलन के माध्यम से बनाए गए डब्ल्यूएवीएल ट्री की ऊंचाई अधिकतम होती है <math>\log_{\varphi} n\approx 1.44\log_2 n</math> तक होती है।<ref name="hst15" />

	यदि एक डब्ल्यूएवीएल ट्री केवल सम्मिलन संचालन का उपयोग करके बनाया गया है, तो इसकी संरचना समान सम्मिलन अनुक्रम द्वारा बनाए गए एवीएल ट्री की संरचना के समान होगी, और इसकी पद संबंधित एवीएल ट्री की पद के समान होगी। केवल विलोपन कार्यों के माध्यम से ही एक डब्ल्यूएवीएल ट्री एक एवीएल ट्री से भिन्न हो सकता है। विशेष रूप से इसका तात्पर्य यह है कि केवल सम्मिलन के माध्यम से बनाए गए डब्ल्यूएवीएल ट्री की ऊंचाई अधिकतम होती है <math>\log_{\varphi} n\approx 1.44\log_2 n</math>.<ref name="hst15"/>


	===लाल-काले ट्री ===		===लाल-काले ट्री ===
	लाल-काला ट्री एक संतुलित बाइनरी खोज ट्री है जिसमें प्रत्येक बिन्दु का एक रंग होता है, जो निम्नलिखित गुणों को संतुष्ट करता है:		लाल-काला ट्री एक संतुलित बाइनरी खोज ट्री है जिसमें प्रत्येक बिन्दु का एक रंग होता है, जो निम्नलिखित गुणों को संतुष्ट करता है:
	* बाहरी बिन्दु काले हैं.		* बाहरी बिन्दु काले हैं.
	* यदि कोई आंतरिक बिन्दु लाल है, तो उसके दोनों चाइल्ड काले हैं।		* यदि कोई आंतरिक बिन्दु लाल है, तो उसके दोनों चाइल्ड काले हैं।

alpha>Shyamunayak: /* लाल-काले ट्री */

2023-07-17T06:07:19Z

लाल-काले ट्री

← Older revision		Revision as of 11:37, 17 July 2023
Line 82:		Line 82:

	==संबंधित संरचनाएं==		==संबंधित संरचनाएं==
	डब्ल्यूएवीएल ट्री , एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित हैं।		डब्ल्यूएवीएल ट्री, एवीएल ट्री और लाल-काले ट्री दोनों से निकटता से संबंधित हैं। प्रत्येक एवीएल ट्री के बिन्दु को इस तरह से पद दी जा सकती है कि वह डब्ल्यूएवीएल ट्री बन जाए। और प्रत्येक डब्ल्यूएवीएल ट्री के बिन्दु लाल और काले रंग के हो सकते हैं जिससे यह एक लाल-काले ट्री में बदल जाता है। यद्यपि, कुछ डब्ल्यूएवीएल ट्री इस तरह से एवीएल ट्री से नहीं आते हैं और कुछ लाल-काले ट्री इस तरह से डब्ल्यूएवीएल ट्री से नहीं आते हैं।
	प्रत्येक एवीएल ट्री के बिन्दु ्स को इस तरह से पद दी जा सकती है कि वह डब्ल्यूएवीएल ट्री बन जाए। और प्रत्येक डब्ल्यूएवीएल ट्री के बिन्दु ्स लाल और काले रंग के हो सकते हैं ~~(और इसकी पद ों को फिर से निर्दिष्ट किया जा सकता है)~~ जिससे यह एक लाल-काले ट्री में बदल जाता है। ~~हालाँकि~~, कुछ डब्ल्यूएवीएल ट्री इस तरह से एवीएल ट्री से नहीं आते हैं और कुछ लाल-काले ट्री इस तरह से डब्ल्यूएवीएल ट्री से नहीं आते हैं।

	===एवीएल ट्री ===		===एवीएल ट्री ===
Line 94:		Line 93:

	===लाल-काले ट्री ===		===लाल-काले ट्री ===
	लाल-काला ट्री एक संतुलित बाइनरी खोज ट्री है जिसमें प्रत्येक बिन्दु का एक रंग ~~(लाल या काला)~~ होता है, जो निम्नलिखित गुणों को संतुष्ट करता है:		लाल-काला ट्री एक संतुलित बाइनरी खोज ट्री है जिसमें प्रत्येक बिन्दु का एक रंग होता है, जो निम्नलिखित गुणों को संतुष्ट करता है:
	* बाहरी बिन्दु ्स काले हैं.		* बाहरी बिन्दु काले हैं.
	* यदि कोई आंतरिक बिन्दु लाल है, तो उसके दोनों चाइल्ड काले हैं।		* यदि कोई आंतरिक बिन्दु लाल है, तो उसके दोनों चाइल्ड काले हैं।
	* रूट से बाहरी बिन्दु तक के सभी पथों में समान संख्या में ~~ब्लैक~~ बिन्दु होते हैं।		* रूट से बाहरी बिन्दु तक के सभी पथों में समान संख्या में काले बिन्दु होते हैं।
	लाल-काले ट्री को समान रूप से बिन्दु ्स पर संग्रहीत पद ों की एक प्रणाली के संदर्भ में परिभाषित किया जा सकता है, जो निम्नलिखित आवश्यकताओं को पूरा करता ~~है (डब्ल्यूएवीएल ट्री में पद ों की आवश्यकताओं से भिन्न):~~		लाल-काले ट्री को समान रूप से बिन्दु पर संग्रहीत पद की एक प्रणाली के संदर्भ में परिभाषित किया जा सकता है, जो निम्नलिखित आवश्यकताओं को पूरा करता है।
	* बाहरी बिन्दु की पद हमेशा 0 होती है और उसके मूल बिन्दु की पद ~~हमेशा~~ 1 होती है।		* बाहरी बिन्दु की पद हमेशा 0 होती है और उसके मूल बिन्दु की पद 1 होती है।
	* किसी भी गैर-रूट बिन्दु की पद या तो उसके मूल बिन्दु की पद या उसके मूल बिन्दु की पद ~~माइनस~~ 1 के बराबर होती है।		* किसी भी गैर-रूट बिन्दु की पद या तो उसके मूल बिन्दु की पद या उसके मूल बिन्दु की पद - 1 के बराबर होती है।
	* किसी भी जड़-पत्ती पथ पर लगातार दो किनारों में पद अंतर 0 नहीं होता है।		* किसी भी जड़-पत्ती पथ पर लगातार दो किनारों में पद अंतर 0 नहीं होता है।
	रंग-आधारित और पद -आधारित परिभाषाओं के बीच समानता को एक दिशा में, एक बिन्दु को काले रंग से देखा जा सकता है यदि उसके मूल की पद अधिक है और लाल रंग से यदि उसके मूल की पद समान है। दूसरी दिशा में, किसी बाहरी बिन्दु के किसी भी पथ पर काले बिन्दु की पद को काले बिन्दु की संख्या के बराबर बनाकर और लाल बिन्दु की पद को उसके मूल बिन्दु के बराबर बनाकर रंगों को पद में परिवर्तित किया जा सकता है।<ref>{{harvtxt\|Goodrich\|Tamassia\|2015}}, Section 4.3 Red–black Trees, pp. 126–129.</ref>		रंग-आधारित और पद -आधारित परिभाषाओं के बीच समानता को एक दिशा में, एक बिन्दु को काले रंग से देखा जा सकता है यदि उसके मूल की पद अधिक है और लाल रंग से यदि उसके मूल की पद समान है। दूसरी दिशा में, किसी बाहरी बिन्दु के किसी भी पथ पर काले बिन्दु की पद को काले बिन्दु की संख्या के बराबर बनाकर और लाल बिन्दु की पद को उसके मूल बिन्दु के बराबर बनाकर रंगों को पद में परिवर्तित किया जा सकता है।<ref>{{harvtxt\|Goodrich\|Tamassia\|2015}}, Section 4.3 Red–black Trees, pp. 126–129.</ref>डब्ल्यूएवीएल ट्री में बिन्दु पद को प्रत्येक पद को दो से विभाजित करके और निकटतम पूर्णांक तक पूर्णांकित करके, लाल-काले ट्री की आवश्यकताओं का पालन करते हुए, बिन्दु की पद की एक प्रणाली में परिवर्तित किया जा सकता है।<ref>In {{harvtxt\|Haeupler\|Sen\|Tarjan\|2015}} the conversion is done by rounding down, because the ranks of external nodes are −1 rather than 0. {{harvtxt\|Goodrich\|Tamassia\|2015}} give a formula that also rounds down, but because they use rank 0 for external nodes their formula incorrectly assigns red–black rank 0 to internal nodes with WAVL rank 1.</ref> इस रूपांतरण के कारण, प्रत्येक डब्ल्यूएवीएल ट्री के लिए समान संरचना वाला एक वैध लाल-काला ट्री उपस्थित होता है। क्योंकि लाल-काले ट्री की ऊंचाई सबसे अधिक होती है <math>2\log_2 n</math>, डब्ल्यूएवीएल ट्री के लिए भी यही सच है।<ref name="gt"/><ref name="hst15"/> यद्यपि ऐसे लाल-काले ट्री उपस्थित हैं जिन्हें वैध डब्ल्यूएवीएल ट्री पद फलन नहीं दिया जा सकता है।<ref name="hst15"/>
	डब्ल्यूएवीएल ट्री में बिन्दु ~~्स की~~ पद को प्रत्येक पद को दो से विभाजित करके और निकटतम पूर्णांक तक पूर्णांकित करके, लाल-काले ट्री की आवश्यकताओं का पालन करते हुए, बिन्दु ्स की पद की एक प्रणाली में परिवर्तित किया जा सकता है।<ref>In {{harvtxt\|Haeupler\|Sen\|Tarjan\|2015}} the conversion is done by rounding down, because the ranks of external nodes are −1 rather than 0. {{harvtxt\|Goodrich\|Tamassia\|2015}} give a formula that also rounds down, but because they use rank 0 for external nodes their formula incorrectly assigns red–black rank 0 to internal nodes with WAVL rank 1.</ref> इस रूपांतरण के कारण, प्रत्येक डब्ल्यूएवीएल ट्री के लिए समान संरचना वाला एक वैध लाल-काला ट्री ~~मौजूद~~ होता है। क्योंकि लाल-काले ट्री की ऊंचाई सबसे अधिक होती है <math>2\log_2 n</math>, डब्ल्यूएवीएल ट्री के लिए भी यही सच है।<ref name="gt"/><ref name="hst15"/>~~हालाँकि,~~ ऐसे लाल-काले ट्री ~~मौजूद~~ हैं जिन्हें वैध डब्ल्यूएवीएल ट्री पद फलन नहीं दिया जा सकता है।<ref name="hst15"/>

	इस तथ्य के ~~बावजूद कि~~, अपने ट्री संरचनाओं के संदर्भ में, डब्ल्यूएवीएल ट्री लाल-काले ट्री के विशेष ~~मामले~~ हैं, उनके अद्यतन संचालन अलग-अलग हैं। डब्ल्यूएवीएल ट्री अपडेट ~~ऑपरेशन~~ में उपयोग किए जाने वाले ट्री ~~रोटेशन~~ ऐसे परिवर्तन कर सकते हैं जिन्हें लाल-काले ट्री में अनुमति नहीं दी जाएगी, क्योंकि वे वास्तव में केवल एक ही रंग में परिवर्तन करने के ~~बजाय~~ लाल-काले ट्री के बड़े उप-ट्री ों का रंग बदलने का कारण बनेंगे। ~~ट्री में पथ.~~<ref name="hst15"/>यह डब्ल्यूएवीएल ट्री को लाल-काले ट्री की तुलना में, सबसे ~~खराब~~ स्थिति में, प्रति विलोपन कम ट्री ~~रोटेशन~~ करने की अनुमति देता है।<ref name="gt"/><ref name="hst15"/>		इस तथ्य के बाद भी, अपने ट्री संरचनाओं के संदर्भ में, डब्ल्यूएवीएल ट्री लाल-काले ट्री के विशेष स्थितिया हैं, उनके अद्यतन संचालन अलग-अलग हैं। डब्ल्यूएवीएल ट्री अपडेट संचालन में उपयोग किए जाने वाले ट्री वर्तन ऐसे परिवर्तन कर सकते हैं जिन्हें लाल-काले ट्री में अनुमति नहीं दी जाएगी, क्योंकि वे वास्तव में केवल एक ही रंग में परिवर्तन करने के अतिरिक्त लाल-काले ट्री के बड़े उप-ट्री का रंग बदलने का कारण बनेंगे।<ref name="hst15"/>यह डब्ल्यूएवीएल ट्री को लाल-काले ट्री की तुलना में, सबसे निम्न स्थिति में, प्रति विलोपन कम ट्री वर्तन करने की अनुमति देता है।<ref name="gt"/><ref name="hst15"/>

alpha>Shyamunayak: /* संचालन */

2023-07-17T05:53:21Z

संचालन

Show changes