[Powered by Google Translate] మీరు ఒక కంప్యూటర్ లో మీ కుటుంబ సభ్యులు ఎలా ప్రాతినిధ్యం వహించే రీతిలో?
మేము కేవలం, ఒక జాబితా ఉపయోగించవచ్చు
కానీ స్పష్టమైన సోపానక్రమం ఇక్కడ ఉంది.
>> లెట్ యొక్క మీ తాతమ్మ, ఆలిస్ ప్రారంభించి చేస్తున్నారు అనుకోండి.
ఆమె 2 కుమారులు, బాబ్ ఉంది
మరియు మీ తాత, చార్లీ.
చార్లీ, 3 పిల్లలు
మీ మామ, డేవ్, మీ అత్త, ఈవ్, మరియు మీ తండ్రి, ఫ్రెడ్.
మీరు ఫ్రెడ్ యొక్క ఏకైక సంతానం ఉన్నారు.
>> ఎందుకు ఈ విధంగా మీ కుటుంబ సభ్యులు నిర్వహించే చేస్తుంది
సాధారణ జాబితా ప్రాతినిధ్యం కన్నా మెరుగుగా?
ఒక కారణం అని ఈ తరతమ శ్రేణి నిర్మాణంలో,
ఒక అని 'చెట్టు,' ఒక సాధారణ జాబితా కంటే ఎక్కువ సమాచారాన్ని కలిగి ఉంది.
మేము ప్రతి ఒక్కరూ మధ్య కుటుంబ సంబంధాలను తెలుసు
కేవలం చెట్టు పరీక్షించి.
అలాగే, ఇది వేగవంతం చేయవచ్చు
లుక్ అప్ సమయం అద్భుతంగా, చెట్టు డేటా క్రమబద్ధీకరించబడింది ఉంటే.
>> మేము ఇక్కడ ఆ ప్రయోజనాన్ని కానీ మేము త్వరలోనే ఈ ఒక ఉదాహరణ చూస్తారు.
ప్రతి వ్యక్తి చెట్టు మీద ఒక నోడ్ ప్రాతినిధ్యం వహిస్తుంది.
నోడ్స్ చైల్డ్ నోడ్స్ కలిగి
అలాగే ఒక పేరెంట్ నోడ్ వంటి.
ఈ సాంకేతిక పదాలు
కుటుంబాలు పాటు విషయాల కోసం చెట్లు ఉపయోగించినప్పుడు కూడా.
ఆలిస్ యొక్క నోడ్, 2 పిల్లలు మరియు తల్లిదండ్రులు ఉంది
చార్లీ యొక్క Node 3 పిల్లలు మరియు 1 మాతృ ఉండగా.
>> ఒక ఆకు నోడ్ ఏ పిల్లలు లేని ఒకటి
చెట్టు యొక్క బయటి అంచుకు న.
చెట్టు యొక్క చాలా ఎత్తైన నోడ్, రూట్ నోడ్,
ఏ పేరెంట్ ఉంది.
>> ఒక బైనరీ చెట్టు, చెట్టు యొక్క ఒక నిర్దిష్ట రకం
దీనిలో ప్రతి నోడ్, అత్యంత, 2 పిల్లలు.
ఇక్కడ C. ఒక బైనరీ చెట్టు ఒక నోడ్ యొక్క struct ఉంది
ప్రతి నోడ్ దాని సంబంధం కొన్ని డేటాను కలిగి ఉంది
ఇతర నోడ్స్ మరియు 2 పాయింటర్లు.
>> మా కుటుంబం చెట్టు లో,
సంబంధం డేటా ప్రతి వ్యక్తి యొక్క పేరు.
ఇది ఏదైనా కావచ్చు అయితే అది, ఒక పూర్ణాంకానికి ఉంది.
దీనిని టర్న్స్,
ఒక బైనరీ చెట్టు, ఒక కుటుంబం కోసం మంచి ప్రాతినిధ్యం కాదు
ప్రజలు తరచుగా కంటే ఎక్కువ 2 పిల్లలు నుండి.
>> ఒక బైనరీ శోధన చెట్టు
బైనరీ చెట్టు యొక్క ఒక ప్రత్యేక ఆదేశించాడు రకం
మాకు త్వరగా విలువలు చూడండి అనుమతిస్తుంది.
మీరు గమనించి ఉండవచ్చు
ఒక చెట్టు యొక్క root క్రింద ప్రతి నోడ్
మరొక చెట్టు యొక్క రూట్, ఒక 'subtree.' అంటారు
ఇక్కడ, చెట్టు యొక్క రూట్, 6
మరియు దాని బిడ్డ, 2, ఒక subtree యొక్క మూలం.
>> ఒక బైనరీ శోధన చెట్టు లో
ఒక నోడ్ యొక్క అన్ని విలువలను కుడి subtree యొక్క
నోడ్ యొక్క విలువ కంటే అధికంగా ఉంటాయి. ఇక్కడ: 6.
Well, ఒక కణుపు యొక్క ఎడమ subtree విలువలు
నోడ్ యొక్క విలువ కంటే తక్కువ.
మేము నకిలీ విలువలు నిర్వహించడానికి అవసరం ఉంటే,
మేము, ఒక వదులుగా అసమానత గానీ వారిలో మార్చవచ్చు
ఒకేలా విలువలు ఎడమ లేదా కుడి గాని వస్తుంది అర్థం,
కాలం మేము అంతా దాని గురించి స్థిరమైన ఉన్నారు.
ఈ చెట్టు ఒక బైనరీ శోధన వృక్షం
ఈ నిబంధనలను అనుసరించి ఎందుకంటే.
>> ఈ మేము సి structs అన్ని నోడ్స్ మారిన ఉంటే అది చూస్తారు ఎలా ఉంది.
గమనికను ఒక బిడ్డ లేదు,
పాయింటర్ NULL.
మేము ఎలా 7 చెట్టు లో ఉంటే చూడటానికి తనిఖీ చెయ్యాలి?
మేము root వద్ద ప్రారంభించండి.
అది చెట్టు లో ఉంటే ఏడు 6 కంటే ఎక్కువగా ఉంటుంది, అందువలన, కుడి వైపు ఉండాలి.
అప్పుడు 8 కంటే తక్కువ, కాబట్టి ఇది ఎడమ ఉండాలి.
ఇక్కడ, మేము 7 గుర్తించారు.
ఇప్పుడు మేము 5 తనిఖీ చేస్తాము.
ఐదు 6 కంటే తక్కువ, కాబట్టి ఇది ఎడమ ఉంటుంది.
ఐదు, 2 కంటే ఎక్కువ
అది కుడి ఉండాలి
మరియు అది కూడా 4 కంటే ఎక్కువ, కాబట్టి అది కుడి మళ్లీ ఉండాలి.
అయితే, ఏ చైల్డ్ ఇక్కడ ఉంది.
పాయింటర్ NULL.
ఈ 5 మా చెట్టు లో కాదు అర్థం.
>> మేము క్రింది కోడ్ బైనరీ చెట్టు శోధించవచ్చు:
ప్రతి కణుపు వద్ద, మేము కనుగొన్నాము లేదో తనిఖీ చెయ్యండి
మేము శోధిస్తున్న విలువ.
మేము దానిని కనుగొనేందుకు లేకపోతే అది ఉండాలి ఉంటే, మేము గుర్తించడానికి
ఎడమ లేదా కుడి మరియు ఆ subtree తనిఖీ.
ఈ లూప్ చెట్టు డౌన్ కొనసాగుతుంది
ఎడమ లేదా కుడి గాని ఎటువంటి చైల్డ్ నోడ్ వచ్చేవరకు.
>> 5 చెట్టు కాదు అని గుర్తుంచుకోండి.
మేము ఎలా అది ఇన్సర్ట్ చెయ్యాలి?
ప్రక్రియ అన్వేషణ పోలి ఉంది.
మేము, 6 నుంచి ప్రారంభమయ్యే చెట్టు డౌన్ iterate
2 ఎడమ,
4 హక్కు,
మరియు కుడి మళ్ళీ, కానీ 4 ఈ వైపు కాదు బిడ్డ ఉన్నాడు.
ఈ, 5 కోసం కొత్త స్థానము
మరియు అది పిల్లలు లేరు ప్రారంభమౌతుంది.
>> ఎంత వేగంగా ఒక బైనరీ శోధన చెట్టు మీద కార్యకలాపాలు ఉంటాయి?
Bigohnotation ఒక ఉన్నత బౌండ్ అందించడం SSA గుర్తుంచుకోండి.
చెత్త సందర్భంలో,
మా చెట్టు కేవలం అనుబంధ జాబితా ఉంటుంది
ఆ చొప్పించడం, తొలగింపు, మరియు శోధన అర్థం
చెట్టు లో నోడ్ ల సంఖ్య నిష్పత్తిలో సమయం పడుతుంది.
ఈ O (n) ఉంది.
>> ఉదాహరణకు, ఈ క్రింది చెల్లుబాటు అయ్యే బైనరీ శోధన వృక్షం.
అయితే, మేము 9 కనుగొనేందుకు ప్రయత్నించండి ఉంటే,
మేము ప్రతి నోడ్ ప్రయాణించేందుకు ఉన్నాయి.
ఇది ఒక లింక్ జాబితా కంటే ఉత్తమం.
సాధారణంగా, మేము ప్రతి నోడ్ కావాలో
మా బైనరీ శోధన చెట్టు యొక్క 2 పిల్లలు.
ఈ విధంగా, చొప్పించడం, తొలగింపు మరియు శోధన
, ఘోరంగా, O (n లాగ్) సమయం తీసుకుంటుంది.
ముందు నుండి చెట్టు, మరింత సంతులిత ఉంటుంది
దీన్ని ఇష్టపడుతున్నారు.
ఇప్పుడు, ఏ విలువ చూస్తూ 3 దశలు, అత్యంత వద్ద, పడుతుంది.
ఈ చెట్టు, సమతుల్య ఉంది
అని అర్థం కనీసపు లోతు ఉంది
ల సంఖ్య సంబంధించి.
>> సమతుల్య బైనరీ శోధన చెట్టు ఒక విలువ గురించి
ఒక క్రమబద్ధీకరించబడతాయి శ్రేణి ద్వియాంశ శోధన పోలి ఉంటుంది.
నిజానికి, మేము అంశాలను ఇన్సర్ట్ లేదా తొలగించవలసిన అవసరం లేకపోతే,
వారు అదే విధంగా ప్రవర్తిస్తాయి.
అయితే, ఒక చెట్టు నిర్మాణం బాగా ఉంది
నిర్వహణ ప్రక్షిప్తాలు మరియు తొలగింపులు కోసం
>> నా పేరు Bannus వాన్ డెర్ Kloot ఉంది.
ఈ CS50 ఉంది.