लाल-काले पेड़ का परिचय


कठिनाई स्तर कठिन
में अक्सर पूछा वीरांगना कोडेशन Facebook गूगल Uber
उन्नत डेटा संरचना बाइनरी सर्च ट्री बाइनरी ट्री डेटा संरचना पेड़

रेड ब्लैक ट्री एक सेल्फ-बैलेंसिंग बाइनरी ट्री है। इस पेड़ में, प्रत्येक नोड या तो एक लाल नोड या एक काला नोड है। इस रेड-ब्लैक ट्री परिचय में, हम इसके सभी मूल गुणों को शामिल करने का प्रयास करेंगे।

लाल-काले पेड़ के गुण

  1. हर नोड को लाल या काले रंग के रूप में दर्शाया जाता है।
  2. रूट नोड हमेशा काला होता है।
  3. लाल नोड में लाल माता-पिता या लाल बच्चा नहीं हो सकता (अर्थात कोई दो लाल नोड आसन्न नहीं हैं)।
  4. किसी भी नोड से उसके NIL वंशज के हर रास्ते में काले नोड की एक समान संख्या होनी चाहिए।

रेड-ब्लैक ट्री के मान्य और अमान्य उदाहरण

लाल-काले पेड़ का परिचय

लाल-काले पेड़ का परिचय

समय जटिलता विश्लेषण

खोज, प्रविष्टि, विलोपन आदि जैसे सभी BST संचालन O (h) समय में किए जा सकते हैं, जहाँ h लाल-काले वृक्ष की ऊँचाई है, और एक संतुलित BST के लिए ऊँचाई हमेशा क्रम में होती है लॉग (n) [n-> नोड्स की संख्या]।

खोजना = O (लॉग (n))
निवेशन = O (लॉग (n))
विलोपन = O (लॉग (n))

रेड-ब्लैक ट्री में ब्लैक हाइट

एक लाल-काले पेड़ में काली ऊँचाई को सरल पथ पर काले नोड्स की संख्या के रूप में परिभाषित किया गया है (आप एक ही नोड में दो बार एक ही नोड का दौरा नहीं करते हैं) एक पत्ती (जो कि एनआईएल है) से। इसे bh (x) द्वारा दर्शाया गया है।

रेड-ब्लैक ट्री की ऊँचाई

विपरीत AVL पेड़, ऊंचाई संतुलन उतना सख्त नहीं है, लेकिन लाल-काले पेड़ों में, एवीएल पेड़ों की तुलना में घुमाव की संख्या कम है।
लाल-काले पेड़ की ऊँचाई h <= 2 (log (n + 1)) {लॉग का आधार 2} विस्तृत है प्रमाण क्यों आरबी पेड़ों की ऊंचाई <= 2 लॉग (एन + 1) है।

ऊँचाई में संतुलन बनाए रखने के लिए लाल-काले वृक्ष का उपयोग पुनर्संरचना और पुनर्गठन करता है।

आप देख सकते हैं कि आरबी के पेड़ किस तरह खुद को पुनर्गठित और पुनर्गठित करते हैं यहाँ.

याद करते हुए

यह कुछ लाल नोड्स के रंग को काले और इसके विपरीत में बदलने के लिए संदर्भित करता है, यह तब भी किया जाता है जब भी एक लाल नोड के लाल माता-पिता का भाई लाल होता है।

लाल-काले पेड़ का परिचय

 

पुनर्गठन

यह पेड़ के रोटेशन को संदर्भित करता है, यह तब भी किया जाता है जब एक लाल बच्चे में एक लाल माता-पिता और काले या अशक्त चाचा होते हैं। पुनर्गठन में चार मामले हैं,

  • सही
  • वाम
  • दाएं से बाएं
  • बाएँ दांए

अनुप्रयोगों

  • स्व-संतुलन BSTs को लागू करने के लिए वास्तविक दुनिया के पुस्तकालयों में उपयोग किया जाता है।
  • इसके समान इस्तेमाल किया ट्रीसेट और C ++ में JAVA और सेट्स एंड मैप्स में ट्री-मैप।

खोजना

एक लाल-काला पेड़ एक BST है, इसलिए एक RBT में खोज BST में खोजने के समान है, नोड का रंग कोई फर्क नहीं पड़ता।