लाल-काले पेड़ के पूरे उप-भाग को हटाने से इसकी गुणों को बनाए रखा जाएगा?

Question

मैं वर्तमान में किसी एप्लिकेशन के लिए कुछ अनुकूलन करने के लिए एक लाल-काले पेड़ डेटा संरचना लागू कर रहा हूं।

मेरे आवेदन में, किसी दिए गए बिंदु पर मुझे पेड़ से दिए गए मान से कम या उसके बराबर सभी तत्वों को हटाने की आवश्यकता है (आप मान सकते हैं कि तत्व पूर्णांक हैं)।

मैं तत्वों को एक-एक करके हटा सकता हूं, लेकिन मैं कुछ तेज़ी से लेना चाहता हूं। इसलिए, मेरा सवाल यह है कि: यदि मैं एक लाल-काले पेड़ की एक पूरी उपखंड हटा देता हूं, तो मैं ऊंचाई और रंग आविष्कारों को पुनर्प्राप्त करने के लिए पेड़ को कैसे ठीक कर सकता हूं?

Answer 1

जब आप लाल-काले पेड़ से एक तत्व हटाते हैं तो यह ओ (लॉग एन) समय लेता है, जहां n वर्तमान में पेड़ में मौजूद तत्वों की संख्या है।

यदि आप केवल कुछ तत्वों को हटाते हैं, तो ओ (के लॉग एन) ऑपरेशंस (के = हटाए गए तत्व, n = हटाने से पहले पेड़ में तत्वों) के साथ समाप्त होने के बाद, उन्हें एक-एक करके निकालना सर्वोत्तम होता है।

लेकिन यदि आप जानते हैं कि आप बड़ी संख्या में नोड्स (उदाहरण के लिए 50% या अधिक पेड़) को हटाने जा रहे हैं, तो उन तत्वों के माध्यम से पुन: प्रयास करना बेहतर है जिन्हें आप रखना चाहते हैं (ओ (के ') ऑपरेशन के '= तत्वों को रखा जाएगा), फिर पेड़ (ओ (1) या ओ (एन) को अपनी मेमोरी प्रबंधन योजना के आधार पर स्क्रैप करें) और पेड़ (ओ (के' लॉग के ')) ऑपरेशन का पुनर्निर्माण करें। कुल जटिलता ओ (के ') + ओ (के' लॉग के ') = ओ (के' लॉग के ') है, जो स्पष्ट रूप से ओ (के लॉग एन) से कम है जब के' < के (आप 50 से कम रखते हैं पेड़ का%)।

वैसे, बिंदु यह है कि जब आप अधिकांश तत्वों को हटाने जा रहे हैं, तो अभ्यास में बेहतर है कि आप उन लोगों को समझाने के लिए बेहतर हैं जिन्हें आप रखना चाहते हैं और फिर पेड़ का पुनर्निर्माण करें।

Answer 2

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

Answer 3

संपादित करें: नीचे एक सामान्य उप-पेड़ हटाने के लिए है। आपको केवल एक ही Split ऑपरेशन (आपकी वास्तविक प्रश्न सामग्री के आधार पर) की आवश्यकता है।

सबसे खराब मामले O(log n) समय में लाल-काले पेड़ की पूरी उप-मिटाना हटाना संभव है।

यह ज्ञात है कि Split और Join लाल-काले पेड़ पर संचालन O(log n) समय में किया जा सकता है।

स्प्लिट: को देखते हुए एक मूल्य के कश्मीर और एक लाल-काले ट्री टी, स्प्लिट टी दो लाल-काले पेड़ों T1 में और टी 2 ऐसी है कि टी 2 में टी 1 < कश्मीर में सभी मान और सभी मूल्यों> = k। टी 1 में एक भी लाल-काले पेड़ टी टी 1 में दो लाल-काले पेड़ों T1 और टी 2 कम्बाइन और टी 2 संतुष्ट अधिकतम < = टी 2 (या टी 1 < = संक्षेप में टी 2) में न्यूनतम:

जुड़ें।

आपको दो Splits और एक Join की आवश्यकता है।

आपके मामले में, उपट्री जिसे आपको हटाने की आवश्यकता है, L <= v <= U मानों की एक श्रृंखला के अनुरूप होगी।

तो आप टी= टी 2 के साथ टी 1 और टी 2 प्राप्त करने के लिए एल पर पहले Split लेते हैं। टी 3 < = टी 4 के साथ टी 3 और टी 4 प्राप्त करने के लिए Split टी 2 पर टी 2। अब Join पेड़ टी 1 और टी 4।

स्यूडोकोड में, अपने कोड कुछ इस तरह दिखेगा: https://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree

:

Tree DeleteSubTree(Tree tree, Tree subTree) { 

    Key L = subTree.Min(); 
    Key U = subTree.Max(); 

    Pair <Tree> splitOnL = tree.Split(L); 
    Pair <Tree> splitOnU = splitOnL.Right.Split(U); 

    Tree newTree = splitOnL.Left.Join(splitOnU.Right); 

    return newTree; 
} 

अधिक जानकारी के लिए इस देखें