रातो-कालो रूख परिचय


कठिनाई तह हार्ड
बारम्बार सोधिन्छ अमेजन CodeNation फेसबुक गुगल Uber
उन्नत डाटा संरचना बाइनरी खोज रूख बाइनरी रूख डाटा संरचना ट्री

रातो कालो रूख एक आत्म-सन्तुलित बाइनरी रूख हो। यस रूखमा, प्रत्येक नोड या त रातो नोड वा कालो नोड हुन्छ। यो रातो कालो रूख परिचयमा हामी यसको सबै आधारभूत गुणहरू कभर गर्ने प्रयास गर्नेछौं।

रातो-कालो रूखका गुणहरू

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

मान्य र अमान्य उदाहरण रेड-कालो रूखको

रातो-कालो रूख परिचय

रातो-कालो रूख परिचय

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

सबै BST अपरेसनहरू जस्तै खोज, सम्मिलन, मेटाउने, आदि O (h) समयमा प्रदर्शन गर्न सकिन्छ, जहाँ रातो कालो रूखको उचाई हो, र सन्तुलित बीएसटीको लागि उचाइ सधैं क्रममा हुन्छ। लग (एन) [n-> नोडहरूको संख्या]

खोजी = O (लग (n))
सम्मिलन = O (लग (n))
मेटाउने = O (लग (n))

रातो-कालो रूखमा कालो उचाई

रातो-कालो रूखमा कालो उचाई कुनै पनी नोडदेखि पातमा (जुन NIL हो) साधारण मार्गमा कालो नोडहरूको संख्याको रूपमा परिभाषित गरिएको छ (तपाईं दुई पटक समान नोड भ्रमण गर्नुहुन्न)। यो bh (x) द्वारा प्रतिनिधित्व गर्दछ।

रातो-कालो रूखको उचाई

विपरीत AVL रूख, उचाइ ब्यालेन्स कडा छैन, तर रातो कालो रूखहरूमा, रोटेशनको संख्या AVL रूखहरूको तुलनामा कम छ।
रातो-कालो रूखको उचाइ h <= २ (लग (n + १)) log लगको आधार २ हो} विस्तृत प्रमाण किन RB रूखहरूको उचाई <= 2 लग (n + १) हो।

उचाईमा सन्तुलन कायम गर्न रातो-कालो रूखले पुन: रoring्ग र पुनर्संरचनाको प्रयोग गर्दछ।

तपाईं देख्न सक्नुहुन्छ कि कसरी RB रूखहरू पुन: रंग र आफैंमा पुनर्गठन गर्दछ यहाँ.

पुन: रoring्ग गर्दै

यसले केहि रातो नोडको र black कालो र यसको विपरितमा परिवर्तन गर्न दर्साउँदछ, जब यो रातो नोडको रातो अभिभावकको भाई रातो हुन्छ।

रातो-कालो रूख परिचय

 

पुनर्गठन

यसले रूखको परिक्रमणलाई जनाउँछ, यो तब गरिन्छ जब रातो बच्चामा रातो अभिभावक र कालो वा कालो वा काका हुन्छन्। पुनर्गठनमा त्यहाँ चारवटा केसहरू छन्,

  • ठिक
  • बाँकी
  • दायाँ बायाँ
  • बायाँ दायाँ

आवेदन

  • वास्तविक-विश्व पुस्तकालयहरुमा आत्म-संतुलन BSTs लागू गर्न प्रयोग गरियो।
  • को रूपमा प्रयोग भयो TreeSet र जाभामा TreeMap र C ++ मा सेट्स र नक्सा।

खोजी

रातो-कालो रूख BST हो, त्यसैले RBT मा खोज्नु भनेको BST मा खोजी गर्नु जत्तिकै हो, नोडको रंगले फरक पार्दैन।