బైనరీ చెట్టు రకాలు


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Delhivery ఇన్ఫోసిస్ మాక్య్
థియరీ ట్రీ

మేము కొనసాగడానికి ముందు, BT నిజంగా ఏమిటో మనకు మొదట తెలుసు? బైనరీ చెట్టు ఒక రకం డేటా నిర్మాణం ఇది క్రమానుగత స్వభావం. ప్రతి నోడ్ వదిలివేసిన నోడ్లు, కుడి పాయింటర్ మరియు డేటా నోడ్ యొక్క బరువుగా BT సూచించబడుతుంది. ప్రతి నోడ్ గరిష్టంగా 2 పిల్లలను కలిగి ఉంటుంది, ఇది పేరెంట్ నోడ్ యొక్క ఎడమ మరియు కుడి బిడ్డను సూచిస్తుంది.

బైనరీ చెట్టు రకాలు

మనకు బైనరీ చెట్లు ఎందుకు అవసరం? | మేము బైనరీ చెట్లను ఎందుకు ఉపయోగిస్తాము?

  • BT ని ఉపయోగించి మనం డేటాపై వేగంగా శోధించడం, చొప్పించడం మరియు తొలగించడం చేయవచ్చు (కొంత ప్రాధాన్యత క్రమంలో ఇవ్వబడింది… BST వంటివి).
  • బిటిని ఉపయోగించి మనం దగ్గరి వస్తువును కూడా కనుగొనవచ్చు.
  • డేటాను క్రమానుగత పద్ధతిలో నిల్వ చేయండి (ఉదా. కంప్యూటర్‌లో ఫైల్ సిస్టమ్).
  • ఏదైనా చర్య చేయడానికి తక్కువ సమయం తీసుకునే పాయింటర్ ఉపయోగించి BT ని అమలు చేయండి.
  • ఉపసర్గ శోధనతో నిఘంటువులను అమలు చేయండి.
  • ఇచ్చిన డేటాసెట్ యొక్క స్థిర వచనంలో వేగంగా శోధించండి.

బైనరీ చెట్ల లక్షణాలు

  1. ఏ స్థాయిలోనైనా గరిష్ట సంఖ్యలో నోడ్లు: 2 ^ L. ఇక్కడ L అనేది అనేక స్థాయిలు (0 <= L <= H).
  2. ఎత్తు H యొక్క BT లో కనిష్ట మరియు గరిష్ట సంఖ్య నోడ్లు: కనిష్ట- H + 1 మరియు గరిష్ట- 2 ^ (H + 1) - 1 ఇక్కడ స్థాయి 0 ఎత్తు 0 గా ఉంటుంది.
  3. N నోడ్‌లను కలిగి ఉన్న BT యొక్క కనీస ఎత్తు: log2 (N + 1) -1 ఇక్కడ స్థాయి 0 ఎత్తు 0 గా ఉంటుంది.
  4. ఆకు నోడ్ల మొత్తం సంఖ్య: 2 పిల్లలు + 1 ఉన్న మొత్తం నోడ్‌ల సంఖ్య.
  5. L ఆకు నోడ్లను కలిగి ఉన్న BT యొక్క కనీస స్థాయిల సంఖ్య: (log2 L) +1.

బైనరీ చెట్ల రకాలు

పూర్తి బైనరీ చెట్లు

రూట్ మరియు ఇంటర్మీడియట్ నోడ్స్ 2 చైల్డ్ నోడ్స్ కలిగి ఉన్న బైనరీ చెట్టు. మరో మాటలో చెప్పాలంటే, ఆకు నోడ్లు తప్ప ప్రతి నోడ్‌లో 2 చైల్డ్ నోడ్స్ ఉన్నాయని కూడా చెప్పగలను.

గమనిక: పూర్తి బైనరీ చెట్టులోని ఆకు నోడ్ల సంఖ్య: అంతర్గత నోడ్ల సంఖ్య + 1.

పూర్తి బైనరీ చెట్లు

పూర్తి బైనరీ చెట్టు

చివరి స్థాయి మినహా అన్ని స్థాయిలు పూర్తిగా నిండిన బైనరీ చెట్టు మరియు అన్ని నోడ్లు ఎడమ నుండి కుడికి నిండి ఉంటాయి

గమనిక: బైనరీ హీప్ పూర్తి బైనరీ చెట్టుకు ఉదాహరణ.

పూర్తి బైనరీ చెట్టు

పర్ఫెక్ట్ బైనరీ ట్రీ

ఒక బైనరీ చెట్టు, దాని అంతర్గత నోడ్లు మరియు రూట్ నోడ్‌లో 2 పిల్లలు మరియు అన్ని ఆకులు ఒకే స్థాయిలో ఉంటాయి.

గమనిక: పర్ఫెక్ట్ బైనరీ ట్రీలోని మొత్తం నోడ్‌ల సంఖ్య: 2 ^ H -1 ఇక్కడ H అనేది BT యొక్క ఎత్తు.

పర్ఫెక్ట్ బైనరీ ట్రీ

సమతుల్య బైనరీ చెట్టు

బైనరీ చెట్టు, దీని ఎడమ సబ్‌ట్రీ ఎత్తు h1 మరియు కుడి సబ్‌ట్రీ ఎత్తు h2 | h1-h2 | <= 1.

గమనిక: AVL మరియు RB చెట్టు సమతుల్య బైనరీ చెట్టును నిర్వహిస్తాయి.

సమతుల్య బైనరీ చెట్టు

పాథలాజికల్ బైనరీ ట్రీ (వక్రీకృత BT / క్షీణించిన BT)

అన్ని అంతర్గత నోడ్లలో ఒకే బిడ్డ ఉన్న బైనరీ చెట్టు పిల్లవాడిని వదిలివేయవచ్చు లేదా అది సరైన పిల్లవాడు కావచ్చు.

గమనిక: పాథలాజికల్ బిటి ఎత్తు: నోడ్స్ -1.

రోగలక్షణ బైనరీ చెట్టు

 

సూచన ఇంటర్వ్యూ ప్రశ్నలు