1. घर
  2. सवाल और जवाब
  3. रेड-ब्लैक ट्री - ब्लैक ऊंचाई प्रतिबंध

रेड-ब्लैक ट्री - ब्लैक ऊंचाई प्रतिबंध

2013-02-24 104 views
5

मैं Red-Black Trees के बारे में विकी पढ़ रहा था।रेड-ब्लैक ट्री - ब्लैक ऊंचाई प्रतिबंध

कोई 5 वीं प्रतिबंध पर विस्तृत कर सकते हैं:

  1. नोड या तो लाल या काले है।

  2. रूट काला है।

  3. सभी पत्तियां (एनआईएल) काला हैं। (सभी पत्तियां रूट के समान रंग हैं।)

  4. प्रत्येक लाल नोड के दोनों बच्चे काले हैं।

  5. किसी दिए गए नोड से प्रत्येक सरल पथ में प्रत्येक सरल पथ में काले नोड्स की संख्या समान होती है।

मैं इसे समझने में कठिनाइयां आ रही हूँ क्योंकि the final case of insertion (विकि पर मामला 5) के बाद उदाहरण RBT के राज्य दिया हमें देता है:

Wiki Red Black tree

4 और 5 नहीं करता है 1,2, और 3 की तुलना में एक और काला नोड है?

स्रोत

2013-02-24 bunnybare

+2

नहीं, क्योंकि 1, 2, और 3 काले नोड्स हैं, जहां 4 और 5 नहीं हैं, इसलिए उन सभी पांच पथों में दो काले नोड्स हैं। –

+0

@IanMcMahon कैसे 4 और 5 काले नहीं हैं? क्या वे प्रतिबंध 3 के कारण नहीं होना चाहिए? – bunnybare

+1

निश्चित रूप से ऐसा लगता है, है ना। अब आप मुझे आश्चर्यचकित कर चुके हैं कि शायद विकी गलत है या नहीं। विकी गलत हो सकता है? यह दुनिया की दृढ़ता में मेरा विश्वास हिलाता है! –

उत्तर

5

1, 2, 3, 4 और 5 सभी सबट्री हैं। हम काले होने के लिए पेड़ 1, 2 और 3 में रूट नोड का रंग जानते हैं। हम नहीं जानते कि नोड्स में से कोई भी 1-5 पत्ती नोड्स हैं, क्योंकि सम्मिलन के इस मामले को कुछ एन पर रिकर्सिवली कहा जा सकता है जो नए डाले गए नोड (सम्मिलन मामले 3 से) के दादा थे।

घूर्णन से पहले और बाद में, subtrees 1, 2 और 3 सभी एक काले नोड (जी पहले, पी के बाद) से नीचे हैं, और subtrees 4 और 5 दो काले नोड्स से नीचे हैं (जी और यू पहले, पी और यू के बाद)। सबट्रीस 1, 2 और 3 में सबट्री 4 और 5 की तुलना में एक और काला नोड है।

स्रोत

2013-02-24 14:19:17 James

+0

इसमें और अधिक देखकर, मैं इसके साथ जाऊंगा। 1,2,3,4, और 5 प्रति पत्तियां नहीं हैं, लेकिन स्वयं के उप-हैं। एन और जी में काले बच्चे हैं (1,2,3 के सिर), इसलिए वहां से आने वाले हर पथ में वास्तव में बदलाव नहीं होता है, क्योंकि यह पहले की तरह काले नोड्स की तरह ही था। यू के माध्यम से पारित होने वाले प्रत्येक पथ में यू और जी को ब्लैक नोड्स (दो) के रूप में रखा गया था, इसलिए घूर्णन के बाद हर पथ को अब यू और पी ब्लैक नोड्स (दो) से गुजरना पड़ा। पहले की तरह काले नोड्स की एक ही संख्या कौन सा है। तो प्रतिबंध अभी भी है, यह मानते हुए कि उनके नीचे subtrees पर प्रतिबंध लगाया। – bunnybare

+0

इसके अतिरिक्त, 1,2, और 3 में से एक और अधिक ब्लैक नोड 4 और 5 से अधिक है क्योंकि 4 और 5 यू के माध्यम से अतिरिक्त ब्लैक नोड प्राप्त करने के लिए पास होते हैं, उन्हें 1,2, और 3. मैं प्रकार की तरह अब समझे। – bunnybare

1

मैंने इसे गहराई से पढ़ा, और ऐसा लगता है कि तस्वीर में कोई समस्या थी।

N के बाद से नोड जो सिर्फ डालने इसका मतलब है कि पिछले insertP के तहत पहले वहाँ के बच्चों [1,3] या [2,3] थे (और डालने सम्मान से 2 या 1 का था) किया गया है। तो उस मामले में अंतिम डालने से पहले P और U लाल होना चाहिए (और 4,5 काला हैं)।

स्रोत

2013-02-24 12:57:36

1

विकी आरेख को समझने के लिए जेम्स को बधाई! यह गलत नहीं है, सिर्फ संदिग्ध है।

पृष्ठ का "टॉक" टैब उल्लेख करता है कि "त्रिभुज पत्तियों का प्रतिनिधित्व करने के लिए नहीं हैं बल्कि उप-निवासी हैं। कुछ subtrees शीर्ष पर काले घेरे हैं यह इंगित करने के लिए कि उनकी जड़ काला होनी चाहिए।"

जाहिर है, मंडलियों की कमी के त्रिभुज उपट्री (पत्तियों समेत) का प्रतिनिधित्व करते हैं जिसके लिए रूट नोड का रंग, और वृक्ष गहराई अज्ञात (और संभवतः अप्रासंगिक) है।

तो आरेख केवल यह बताते हैं कि "नियम 5" का उल्लंघन किया गया है या नहीं, यह पर्याप्त जानकारी प्रदान नहीं करता है। हमें इसे एक दिए गए के रूप में लेना है कि यह नहीं है।

स्रोत

2013-02-24 18:07:33

 संबंधित मुद्दे

  • कोई संबंधित समस्या नहीं^_^