రెడ్-బ్లాక్ ట్రీ పరిచయం


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది అమెజాన్ కోడ్‌నేషన్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ ఉబెర్
అధునాతన డేటా నిర్మాణం బైనరీ శోధన చెట్టు బైనరీ చెట్టు డేటా నిర్మాణం ట్రీ

రెడ్ బ్లాక్ ట్రీ ఒక స్వీయ-బ్యాలెన్సింగ్ బైనరీ చెట్టు. ఈ చెట్టులో, ప్రతి నోడ్ ఎరుపు నోడ్ లేదా బ్లాక్ నోడ్. ఈ ఎరుపు-నలుపు చెట్టు పరిచయంలో, మేము దాని ప్రాథమిక లక్షణాలన్నింటినీ కవర్ చేయడానికి ప్రయత్నిస్తాము.

ఎరుపు-నల్ల చెట్టు యొక్క లక్షణాలు

  1. ప్రతి నోడ్ ఎరుపు లేదా నలుపు రంగుగా సూచించబడుతుంది.
  2. రూట్ నోడ్ ఎల్లప్పుడూ నల్లగా ఉంటుంది.
  3. ఎరుపు నోడ్‌లో ఎరుపు పేరెంట్ లేదా ఎరుపు బిడ్డ ఉండకూడదు (అనగా రెండు ఎరుపు నోడ్‌లు ప్రక్కనే లేవు).
  4. ఏదైనా నోడ్ నుండి దాని ఎన్‌ఐఎల్ వారసుడికి వెళ్లే ప్రతి మార్గంలో సమాన సంఖ్యలో బ్లాక్ నోడ్‌లు ఉండాలి.

ఎరుపు-నల్ల చెట్టు యొక్క చెల్లుబాటు అయ్యే మరియు చెల్లని ఉదాహరణలు

రెడ్-బ్లాక్ ట్రీ పరిచయం

రెడ్-బ్లాక్ ట్రీ పరిచయం

సమయం సంక్లిష్టత విశ్లేషణ

శోధన, చొప్పించడం, తొలగింపు మొదలైన అన్ని BST కార్యకలాపాలను O (h) సమయంలో చేయవచ్చు, ఇక్కడ h అనేది ఎరుపు-నలుపు చెట్టు యొక్క ఎత్తు, మరియు సమతుల్య BST కొరకు ఎత్తు ఎల్లప్పుడూ క్రమంలో ఉంటుంది లాగ్ (n) [n-> నోడ్‌ల సంఖ్య].

శోధించండి = O (లాగ్ (n))
చొప్పించడం = O (లాగ్ (n))
తొలగింపు = O (లాగ్ (n))

ఎరుపు-నల్ల చెట్టులో నల్ల ఎత్తు

ఎరుపు-నలుపు చెట్టులోని నల్ల ఎత్తు సాధారణ మార్గంలో ఉన్న నల్ల నోడ్‌ల సంఖ్యగా నిర్వచించబడింది (మీరు ఒకే నోడ్‌ను రెండుసార్లు సందర్శించరు) ఏదైనా నోడ్ నుండి ఆకు వరకు (ఇది NIL). ఇది bh (x) ద్వారా ప్రాతినిధ్యం వహిస్తుంది.

ఎరుపు-నల్ల చెట్టు యొక్క ఎత్తు

కాకుండా AVL చెట్టు, ఎత్తు సంతులనం అంత కఠినమైనది కాదు, కానీ ఎరుపు-నలుపు చెట్లలో, AVL చెట్లతో పోలిస్తే భ్రమణాల సంఖ్య తక్కువగా ఉంటుంది.
ఎరుపు-నలుపు చెట్టు యొక్క ఎత్తు h <= 2 (లాగ్ (n + 1)) log లాగ్ యొక్క స్థావరం 2} వివరణాత్మక ప్రూఫ్ RB చెట్ల ఎత్తు <= 2 లాగ్ (n + 1) ఎందుకు.

ఎత్తులో సమతుల్యతను కొనసాగించడానికి ఎరుపు-నలుపు చెట్టు రంగు మరియు పునర్నిర్మాణాన్ని ఉపయోగిస్తుంది.

RB చెట్లు తమను తాము ఎలా గుర్తుకు తెచ్చుకుంటాయో మరియు పునర్నిర్మించవచ్చో మీరు చూడవచ్చు <span style="font-family: Mandali; ">ఇక్కడ క్లిక్ చేయండి .

గుర్తుపట్టడం

ఇది కొన్ని ఎరుపు నోడ్‌ల రంగును నలుపు మరియు వైస్ వెర్సాగా మార్చడాన్ని సూచిస్తుంది, ఎరుపు నోడ్ యొక్క ఎరుపు పేరెంట్ యొక్క తోబుట్టువు ఎరుపుగా ఉన్నప్పుడు ఇది జరుగుతుంది.

రెడ్-బ్లాక్ ట్రీ పరిచయం

 

పునర్నిర్మాణ

ఇది చెట్టు యొక్క భ్రమణాన్ని సూచిస్తుంది, ఎరుపు బిడ్డకు ఎరుపు తల్లిదండ్రులు మరియు నలుపు లేదా శూన్య మామ ఉన్నప్పుడల్లా ఇది జరుగుతుంది. పునర్నిర్మాణంలో నాలుగు కేసులు ఉన్నాయి,

  • కుడి
  • ఎడమ
  • కుడి ఎడమ
  • ఎడమ-కుడి

అప్లికేషన్స్

  • స్వీయ-బ్యాలెన్సింగ్ BST లను అమలు చేయడానికి వాస్తవ ప్రపంచ గ్రంథాలయాలలో ఉపయోగించబడుతుంది.
  • గా వాడతారు ట్రీసెట్ మరియు జావాలో ట్రీమ్యాప్ మరియు సి ++ లో సెట్స్ అండ్ మ్యాప్స్.

శోధించండి

ఎరుపు-నలుపు చెట్టు ఒక BST, కాబట్టి RBT లో శోధించడం BST లో శోధించినట్లే, నోడ్ యొక్క రంగు పట్టింపు లేదు.