చెట్లు, ఎరుపు మరియు నలుపు చెట్లు

"హాయ్, అమిగో!"

"హలో, రిషీ!"

"నేను అక్కడ నా పాత నోట్లను కనుగొన్నాను మరియు మీ కోసం కొన్ని ఆసక్తికరమైన విషయాలను సిద్ధం చేసాను. మీరు దానిని వినడానికి ఆసక్తి చూపుతారని నేను భావిస్తున్నాను."

"అది విందాం. మీరు ఎల్లప్పుడూ ఆసక్తికరమైనదాన్ని కనుగొంటారు, అది చాలా ఉపయోగకరంగా ఉంటుంది."

"సరే. ఈ రోజు నేను మీకు చెట్ల గురించి చెప్పాలనుకుంటున్నాను , కాబట్టి నేను గ్రాఫ్‌లతో ప్రారంభిస్తాను ."

" గ్రాఫ్ అనేది వాటిని కనెక్ట్ చేసే పాయింట్లు మరియు పంక్తుల వ్యవస్థ. పాయింట్లను గ్రాఫ్ యొక్క శీర్షాలు అని పిలుస్తారు మరియు పంక్తులను గ్రాఫ్ అంచులు అంటారు. ఉదాహరణకు:"

"గ్రాఫ్ వివిధ వాస్తవ-ప్రపంచ ప్రక్రియలు మరియు పనుల కోసం గణిత నమూనాగా ఉపయోగించడానికి చాలా సౌకర్యవంతంగా ఉంటుంది. గ్రాఫ్‌ల కోసం అనేక విభిన్న పనులు మరియు అల్గారిథమ్‌లు కనుగొనబడ్డాయి, కాబట్టి అవి చాలా తరచుగా ఉపయోగించబడతాయి."

"ఉదాహరణకు, శీర్షాలు నగరాలు, మరియు అంచులు రోడ్లు అని అనుకుందాం. అప్పుడు నగరాల మధ్య అతి చిన్న రహదారి కోసం శోధించడం ఇలా అవుతుంది: «గ్రాఫ్ ఇచ్చినట్లయితే, రెండు శీర్షాల మధ్య చిన్నదైన మార్గాన్ని కనుగొనండి» .

"కానీ A నుండి Bకి మార్గం ఎల్లప్పుడూ B నుండి Aకి మార్గం వలె ఉండదు. కాబట్టి, కొన్నిసార్లు రెండు వేర్వేరు పంక్తులు కలిగి ఉండటం ప్రాధాన్యతనిస్తుంది. దీన్ని చేయడానికి, పంక్తులు (గ్రాఫ్ యొక్క అంచులు) బాణాలతో భర్తీ చేయబడతాయి. ఇతర మాటలలో, గ్రాఫ్ రెండు బాణాలను కలిగి ఉంటుంది: ఒకటి A నుండి B వరకు మరియు మరొకటి B నుండి A వరకు."

"గ్రాఫ్ బాణాలను ఉపయోగిస్తే, దానిని డైరెక్ట్ గ్రాఫ్ అంటారు ; అది కేవలం పంక్తులు కలిగి ఉంటే, దానిని నిర్దేశించని గ్రాఫ్ అంటారు ."

"ప్రతి శీర్షం దాని స్వంత అంచుల సంఖ్యను కలిగి ఉంటుంది. ఒక శీర్షానికి అంచులు కూడా ఉండవు. దీనికి విరుద్ధంగా, ఒక శీర్షాన్ని ప్రతి ఇతర శీర్షానికి అంచుల ద్వారా అనుసంధానించవచ్చు. గ్రాఫ్‌లోని ప్రతి జత శీర్షాలు అంచుతో అనుసంధానించబడి ఉంటే,  అప్పుడు దానిని పూర్తి గ్రాఫ్ అంటారు. "

"గ్రాఫ్‌లోని ప్రతి శీర్షాన్ని చేరుకోవడానికి మీరు అంచులను ఉపయోగించగలిగితే, దానిని కనెక్ట్ చేయబడిన గ్రాఫ్ అంటారు. మూడు వేర్వేరు శీర్షాలు మరియు అంచులు లేని గ్రాఫ్ ఇప్పటికీ గ్రాఫ్, కానీ మేము దానిని డిస్‌కనెక్ట్ చేయబడిన గ్రాఫ్ అని పిలుస్తాము."

"N శీర్షాల నుండి కనెక్ట్ చేయబడిన గ్రాఫ్‌ను రూపొందించడానికి, మీకు కనీసం N-1 అంచులు అవసరం. ఈ రకమైన గ్రాఫ్‌ని చెట్టు అంటారు."

"అంతేకాకుండా, సాధారణంగా ఒక శీర్షాన్ని చెట్టు యొక్క మూలంగా ఎంచుకుంటారు మరియు మిగిలిన వాటిని శాఖలుగా ప్రకటిస్తారు. స్వంత కొమ్మలు లేని చెట్ల కొమ్మలను ఆకులు అంటారు . ఉదాహరణకు:"

"చెట్టు యొక్క ప్రతి మూలకానికి ఇద్దరు పిల్లలు ఉంటే, దానిని బైనరీ ట్రీ అంటారు . మరో మాటలో చెప్పాలంటే, 0 లేదా 2 శాఖలు ఉండవచ్చు. మీరు ఎగువ కుడి వైపున ఒక బైనరీ చెట్టును చూడవచ్చు ."

" ఒక్కో శాఖకు 2 పిల్లలు ఉన్నప్పుడు ఒక చెట్టును పూర్తి బైనరీ చెట్టు అంటారు , మరియు అన్ని ఆకులు (పిల్లలు లేని శీర్షాలు) ఒకే వరుసలో ఉంటాయి."

"ఉదాహరణకి:"

"ఈ చెట్లు ఎందుకు అవసరం?"

"ఓహ్, చెట్లు చాలా ప్రదేశాలలో ఉపయోగించబడతాయి. సాధారణంగా, బైనరీ చెట్లు నిర్మాణాత్మక డేటాను క్రమబద్ధీకరించబడతాయి."

"అదేమిటి?"

"అవును, ఇది చాలా సులభం. మేము ప్రతి శీర్షంలో నిర్దిష్ట విలువను నిల్వ చేస్తాము. మరియు ప్రతి మూలకం ఒక నియమాన్ని అనుసరిస్తుంది: కుడి చైల్డ్‌లో నిల్వ చేయబడిన విలువ శీర్షంలో నిల్వ చేయబడిన విలువ కంటే ఎక్కువగా ఉండాలి మరియు ఎడమ చైల్డ్‌లో నిల్వ చేయబడిన విలువ తప్పనిసరిగా ఉండాలి శీర్షంలో నిల్వ చేయబడిన విలువ కంటే తక్కువగా ఉండాలి.  ఈ క్రమం మీకు అవసరమైన చెట్టు యొక్క మూలకాలను త్వరగా కనుగొనడం సాధ్యం చేస్తుంది."

"దీని అర్థం ఏమిటో మీరు స్పష్టం చేయగలరా?"

"వృక్ష మూలకాలు సాధారణంగా జోడించడం ద్వారా క్రమబద్ధీకరించబడతాయి. మనకు 7 అంశాలు ఉన్నాయని అనుకుందాం: 13, 5, 4, 16, 8, 11, 10"

"చెట్టుకు మూలకాలు ఎలా జోడించబడతాయో ఇక్కడ ఉంది."

"మేము ఈ చెట్టులో 7 నంబర్ కోసం చూస్తున్నట్లయితే, శోధన ఇలా సాగుతుంది"

"0) రూట్ వద్ద ప్రారంభించండి."

"1a) 7 సమానం 13? లేదు"

"1b) 13 కంటే 7 పెద్దదా? లేదు, కాబట్టి మనం ఎడమ సబ్‌ట్రీకి వెళ్తాము."

"2a) 7 సమానం 5? కాదు."

"2b) 5 కంటే 7 పెద్దదా? అవును, కాబట్టి మనం కుడి సబ్‌ట్రీకి వెళ్తాము."

"3a) 7 సమానం 8? కాదు"

"3b) 8 కంటే 7 పెద్దదా? లేదు, కాబట్టి మనం ఎడమ సబ్‌ట్రీకి వెళ్తాము."

"4a) ఎడమ సబ్‌ట్రీ లేదు, అంటే సంఖ్య 7 చెట్టులో లేదు."

"ఆహ్. మరో మాటలో చెప్పాలంటే, మేము రూట్ నుండి కోరుకున్న సంఖ్య యొక్క స్థానానికి వెళ్లే మార్గంలో శీర్షాలను మాత్రమే తనిఖీ చేయాలి. అవును, అది నిజంగా వేగవంతమైనది."

"అంతేకాదు, చెట్టు సమతుల్యంగా ఉంటే, మిలియన్ మూలకాలను శోధించడానికి మీరు కేవలం 20 శీర్షాల గుండా వెళ్లాలి."

"నేను అంగీకరిస్తున్నాను - ఇది చాలా ఎక్కువ కాదు."

"సమతుల్య చెట్టు అంటే ఏమిటి?"

"వక్రీకరించని చెట్టు, అంటే పొడవాటి కొమ్మలు లేవు. ఉదాహరణకు, మేము చెట్టును నిర్మించినప్పుడు మూలకాలు ఇప్పటికే క్రమబద్ధీకరించబడి ఉంటే, మేము ఒక కొమ్మతో కూడిన చాలా పొడవైన చెట్టును తయారు చేస్తాము. "

"హ్మ్. నువ్వు చెప్పింది నిజమే. కాబట్టి మనం ఏమి చేయాలి?"

"మీరు బహుశా ఇప్పటికే ఊహించినట్లుగా, అత్యంత ప్రభావవంతమైన చెట్టు దాదాపు ఒకే పొడవు ఉండే కొమ్మలను కలిగి ఉంటుంది. అప్పుడు ప్రతి పోలిక మిగిలిన సబ్‌ట్రీలో అతిపెద్ద భాగాన్ని విస్మరిస్తుంది."

"కాబట్టి, మనం చెట్టును పునర్నిర్మించాలా?"

"అవును. ఇది «సమతుల్యమైనది» - పూర్తి బైనరీ చెట్టుకు వీలైనంత దగ్గరగా ఉండాలి."

"ఈ సమస్యను పరిష్కరించడానికి, స్వీయ-సమతుల్య వృక్షాలు కనుగొనబడ్డాయి.  ఒక మూలకాన్ని జోడించిన తర్వాత చెట్టు వక్రీకరించబడితే, అది ప్రతిదీ సరిగ్గా చేయడానికి మూలకాలను కొద్దిగా క్రమబద్ధీకరిస్తుంది.  బ్యాలెన్సింగ్ యొక్క ఉదాహరణ ఇక్కడ ఉంది:"

"ఈ చెట్లలో కొన్నింటిని ఎరుపు -నలుపు చెట్లు అంటారు ."

"వారు ఎరుపు-నలుపు అని ఎందుకు పిలుస్తారు?"

"వారి ఆవిష్కర్త రెండు రంగులను ఉపయోగించి అన్ని శీర్షాలను గీసాడు. ఒక రంగు ఎరుపు, మరియు మరొకటి నలుపు. వివిధ శీర్షాలు వేర్వేరు నియమాలను పాటిస్తాయి. ఇది బ్యాలెన్సింగ్ ప్రక్రియకు పూర్తి ఆధారాన్ని ఏర్పరుస్తుంది."

"ఉదాహరణకి:"

"కాబట్టి ఈ నియమాలు ఏమిటి?"

"1) ఎరుపు శీర్షం ఎర్రటి శీర్షానికి బిడ్డ కాకూడదు."

"2) ప్రతి ఆకు యొక్క నలుపు లోతు ఒకేలా ఉంటుంది (నలుపు లోతు అనేది రూట్ నుండి మార్గంలో ఉన్న నల్లటి శీర్షాల సంఖ్యను సూచిస్తుంది)."

"3) చెట్టు యొక్క మూలం నలుపు."

"ఇది ఎలా పని చేస్తుందో నేను వివరించను - మీ తల బహుశా ఇప్పటికే పేలుతోంది."

"అవును. నా ప్రాసెసర్ కొంచెం పొగను వదులుతోంది."

"మీ కోసం ఇక్కడ ఒక లింక్ ఉంది. మీకు కావాలంటే, మీరు దాని గురించి ఇక్కడ మరింత చదవవచ్చు."

అదనపు మెటీరియల్‌కి లింక్ చేయండి

"మరియు ఇప్పుడు, విశ్రాంతి తీసుకోండి."