लाल-काळा वृक्ष परिचय


अडचण पातळी हार्ड
वारंवार विचारले ऍमेझॉन कोडनेशन फेसबुक Google उबेर
प्रगत डेटा रचना बायनरी शोध वृक्ष बायनरी ट्री डेटा रचना झाड

रेड ब्लॅक ट्री एक स्व-संतुलित बायनरी वृक्ष आहे. या झाडामध्ये, प्रत्येक नोड एकतर लाल नोड किंवा काळा नोड असतो. या लाल-काळ्या झाडाच्या परिचयात, आम्ही त्याच्या सर्व मूलभूत गुणधर्मांना कव्हर करण्याचा प्रयत्न करू.

लाल-काळ्या झाडाचे गुणधर्म

  1. प्रत्येक नोड लाल किंवा काळा एकतर दर्शविला जातो.
  2. मूळ नोड नेहमीच काळा असतो.
  3. लाल नोडला लाल पालक किंवा लाल मूल असू शकत नाही (म्हणजे दोन लाल नोड शेजारी नसतात).
  4. कोणत्याही नोडपासून त्याच्या एनआयएल वंशजापर्यंतच्या प्रत्येक पथात समान संख्येने काळा नोड असणे आवश्यक आहे.

लाल-काळ्या झाडाची वैध आणि अवैध उदाहरणे

लाल-काळा वृक्ष परिचय

लाल-काळा वृक्ष परिचय

वेळ कॉम्प्लेक्सिटी विश्लेषण

ओएस (एच) वेळेत शोध, घालणे, हटविणे इत्यादी सर्व बीएसटी ऑपरेशन्स केल्या जाऊ शकतात, जेथे लाल-काळ्या झाडाची उंची असते आणि संतुलित बीएसटीसाठी उंची नेहमीच असते. लॉग (एन) [n-> नोड्सची संख्या]

शोधत आहे = ओ (लॉग (एन))
अंतर्भूत = ओ (लॉग (एन))
हटविणे = ओ (लॉग (एन))

लाल-काळ्या झाडाची ब्लॅक उंची

लाल-काळ्या झाडाच्या काळ्या उंचीची व्याख्या कोणत्याही नोडपासून एका पानापर्यंत (जे एनआयएल आहे) साध्या मार्गावरील काळ्या नोड्स (आपण समान नोडला दोनदा भेट देत नाही) म्हणून परिभाषित केले आहे. हे बीएच (एक्स) द्वारे दर्शविले जाते.

लाल-काळ्या झाडाची उंची

विपरीत AVL वृक्ष, उंची शिल्लक तितकी कठोर नसते, परंतु लाल-काळ्या झाडांमध्ये, एव्हीएलच्या झाडाच्या तुलनेत फिरण्याची संख्या कमी असते.
लाल-काळ्या झाडाची उंची एच <= 2 (लॉग (एन + 1)) log लॉगचा आधार 2} तपशीलवार आहे पुरावा आरबी झाडांची उंची <= 2 लॉग (एन + 1) का आहे.

उंचीमध्ये समतोल राखण्यासाठी लाल-काळे झाड पुनर्रचना आणि पुनर्रचना वापरते.

आपण पाहू शकता की आरबी झाडे कशी पुनर्रचना करतात आणि त्यांची पुनर्रचना करतात येथे.

पुन्हा रंगत आहे

हे काही लाल नोड्सचा रंग काळा आणि त्याउलट बदलण्याचा संदर्भ देते, जेव्हा लाल नोडच्या लाल पालकांचा भाऊ लाल असतो तेव्हा हे केले जाते.

लाल-काळा वृक्ष परिचय

 

पुनर्रचना

हे झाडाच्या फिरण्याच्या संदर्भात आहे, जेव्हा जेव्हा लाल मुलाला लाल पालक आणि काळा किंवा शून्य काका असतो तेव्हा हे केले जाते. पुनर्रचनेत चार प्रकरणे आहेत,

  • योग्य
  • बाकी
  • उजवा-डावा
  • डाव्या उजव्या

अनुप्रयोग

  • सेल्फ-बॅलेन्सिंग बीएसटी लागू करण्यासाठी रिअल-वर्ल्ड लायब्ररीत वापरली जाते.
  • म्हणून वापरले ट्रीसेट आणि जावामध्ये ट्रीमॅप आणि सी ++ मधील सेट्स आणि नकाशे.

शोधत आहे

लाल-काळा झाड एक बीएसटी आहे, म्हणून आरबीटीमध्ये शोधणे अगदी बीएसटीमध्ये शोधण्यासारखेच आहे, नोडचा रंग काही फरक पडत नाही.