కెవిన్ స్చ్మిడ్: కొన్నిసార్లు, నిర్మాణ సమయంలో ఒక కార్యక్రమం, మీరు ఉపయోగించుకుంటాయి అనుకోవచ్చు ఒక ఒక నిఘంటువు పిలుస్తారు డేటా నిర్మాణం. ఇవి ఒక నిఘంటువు మాన కీలు, సాధారణంగా తీగలను, విలువలకు, ints, అక్షరాలు, కొన్ని వస్తువు ఒక పాయింటర్, మేము కావలసిన. ఇది కేవలం సాధారణ నిఘంటువులు వంటిది నిర్వచనాలు ద్వారా ఆ చిహ్నం పదాలు. 

నిఘంటువులు అందించండి సమాచారం నిల్వ సామర్థ్యం ఏదో సంబంధం మరియు తరువాత దానిని చూసి. కాబట్టి మేము ఎలా వాస్తవానికి అమలు చెయ్యాలి ఒక సి కోడ్, సే, నిఘంటువు అని మేము మా కార్యక్రమాలు ఒకటి ఉపయోగించడానికి? బాగా, ఎన్నోవిధాలుగా ఉన్నాయి మేము ఒక నిఘంటువు అమలు కాలేదు. 

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

ఇప్పుడు కోసం, యొక్క మేము ఊహించుకోవటం కీలు వంటి తీగలను ఉపయోగించాలనుకుంటున్నాను. యొక్క ఒక అవకాశం గురించి చూద్దాం, ఒక డేటా నిర్మాణం ఒక trie అని. ఇక్కడ ఒక దృశ్య ఉంది ఒక trie. 

చిత్రాన్ని, ఒక trie సూచించినట్లుగా ఒక చెట్టు డేటా నిర్మాణం నోడ్స్ కలిసి లింక్. మేము రూట్ స్పష్టంగా ఉందని చూడండి కొన్ని లింకులు వరకు తో నోడ్ ఇతర నోడ్స్. కానీ ప్రతి నోడ్ ఏ ఉంటాయి లేదు? మేము కీలు నిల్వ చేస్తున్న ఊహించుకుంటే మాత్రమే అక్షరమాల అక్షరాలు, మరియు తో మేము క్యాపిటలైజేషన్ గురించి పట్టించుకోను, ఇక్కడ ఒక నోడ్ యొక్క నిర్వచనం ఆ తగినంత ఉంటుంది. 

దీని రకం ఒక వస్తువు struct ఉంది నోడ్ రెండు భాగాలుంటాయి డేటా మరియు పిల్లలు అని. మేము వ్యాఖ్య అని డేటా భాగంగా నిష్క్రమించారు ఒక భాగం స్థానంలో struct నోడ్ ఉన్నప్పుడు ప్రకటన ఒక సి ప్రవేశపెట్టారు. ఒక నోడ్ యొక్క డేటా భాగంగా ఒక కావచ్చు సూచించడానికి బూలియన్ విలువ లేదో కాదు నోడ్ పూర్తి సూచిస్తుంది ఒక నిఘంటువు కీ లేదా ఒక కావచ్చు నిర్వచనం ప్రాతినిధ్యం స్ట్రింగ్ నిఘంటువు లో ఒక పదం యొక్క. 

మేము సూచించడానికి ఒక స్మైలీ ముఖం ఉపయోగిస్తాము డేటా ఒక నోడ్ లేనపుడు. లో 26 అంశాలను ఉన్నాయి మా పిల్లలు శ్రేణి, ఒక ఇండెక్స్ అక్షరమాల పాత్ర శాతం. మేము ప్రాముఖ్యత చూస్తారు త్వరలో ఈ. 

యొక్క రూట్ నోడ్ ఒక సమీప వీక్షణ లెట్ మా రేఖాచిత్రం లో, ఏ డేటా ఉంది ద్వారా సూచించిన, ఇది సంబంధం లో స్మైలీ ముఖం లేకపోవడం డేటా భాగం. భాగాలు నుండి విస్తరించి బాణాలు పిల్లలు శ్రేణి కాని నోడ్ ప్రాతినిధ్యం ఇతర కణుపులకు గమనికలు. ఉదాహరణకు, బాణం వరకు విస్తరించి పిల్లల రెండవ మూలకం లేఖ B సూచిస్తుంది ఒక నిఘంటువు కీ లో. మరియు పెద్ద రేఖాచిత్రం మేము ఒక B. తో లేబుల్ 

, పెద్ద రేఖాచిత్రం గమనించండి మేము మరొక నోడ్ ఒక పాయింటర్ డ్రా, ఇది పట్టింపు లేదు పేరు యారో హెడ్ ఇతర నోడ్ కలుస్తుంది. మా నమూనా నిఘంటువు trie కలిగి రెండు పదాలు, మరియు జూమ్. యొక్క ఒక ఉదాహరణ నడవడానికి లెట్ కీలక కోసం డేటా చూస్తూ. 

మేము చూసేందుకు కోరుకున్నారు అనుకుందాం కీ స్నానమునకు విలువ సంబంధిత. మేము మా రూపాన్ని అప్ చేస్తాము రూట్ నోడ్ వద్ద. అప్పుడు మేము మా మొదటి లేఖ తీసుకొని వెళ్తాము , కీ B, మరియు సంబంధిత కనుగొనేందుకు మా పిల్లలు శ్రేణి లో గుర్తించడం. ఖచ్చితంగా 26 మచ్చలు ఉన్నాయి గమనించి శ్రేణి, ప్రతి అక్షరానికి ఒక వర్ణమాల. మరియు మేము మచ్చలు ప్రాతినిధ్యం ఉంటుంది క్రమంలో అక్షరాలు. 

మేము, రెండవ సూచిక వద్ద పరిశీలిస్తాము సాధారణంగా B. కోసం సూచిక ఒకటి,, మేము కొన్ని అక్షర పాత్ర C మనం ఇదే స్పాట్ నిశ్చయిస్తాడు ఉపయోగించి పిల్లలు శ్రేణి లో ఈ వంటి ఒక గణన. మేము ఒక పెద్ద పిల్లలు ఉపయోగిస్తారు చేశారు మేము లుక్ అప్ అందిస్తాయి కోరుకున్నారు శ్రేణి ఉంటే అక్షరాలు విస్తృతిలో తో కీలు, ఇటువంటి మొత్తం వంటి ASCII పాత్ర సెట్. 

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

ఇప్పుడు, మేము రెండవ లేఖ తీసుకొని వెళ్తాము మా కీ, ఒక, కొనసాగించడానికి క్రింది ఈ విధంగా గమనికలు మేము వరకు మా కీ ముగింపు చేరుకోవడానికి. మేము లేకుండా కీ ముగింపు చేరుకోవడానికి ఉంటే ఏ మిథునం కొట్టిన శూన్య గమనికలు, కేసు ఇక్కడ ఉంది, అప్పుడు మేము మాత్రమే మరో విషయం తనిఖీ ఉంటుంది. ఈ కీ నిజానికి నిఘంటువు లో? 

అలా అయితే, మేము ఒక, ఒక విలువ కనుగొనేందుకు ఉండాలి మా రేఖాచిత్రం లో స్మైలీ ముఖం చిహ్నం పేరు పదం ముగుస్తుంది. తో నిల్వ వేరే ఏదో ఉంది ఉంటే డేటా, అప్పుడు మేము అది తిరిగి. ఉదాహరణకు, కీ జూలో కాదు మేము కలిగి అయినప్పటికీ నిఘంటువు, ఎప్పుడూ లేకుండా ఈ కీ చేరుకుంది , ఒక నల్ పాయింటర్ కొట్టిన మనం trie ద్వారా iterate. 

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

యొక్క కీ ఇన్సర్ట్ లెట్ మా trie లోకి జూ. గుర్తు ఒక నోడ్ ఒక నవ్వుతున్న ముఖం ఒక సాధారణ కోడ్ లో అనుగుణంగా కాలేదు ఆ జూ సూచించడానికి బూలియన్ విలువ నిఘంటువు లో ఉంది లేదా చేయగలిగే మరింత సమాచారం అనుగుణ్యమైన మేము కీ జూ అనుబంధం అనుకుంటున్నారా, నిర్వచనం వంటి పదం లేదా ఏదో. కొన్ని మార్గాల్లో, ప్రక్రియ ఇన్సర్ట్ ఒక trie దేన్నైనా పోలి ఉంటుంది ఒక trie లో ఏదో చూస్తూ. 

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

మేము సూచించడానికి నోడ్ సవరించవచ్చు దారితీసింది అక్షరాలు మార్గం ఇది చేస్తుంది మా నిఘంటువులో కీలక సూచిస్తుంది. ఇప్పుడు, యొక్క ఇన్సర్ట్ ప్రయత్నించండి trie లోకి కీ BATH. మేము రూట్ నోడ్ వద్ద ప్రారంభిస్తాము మళ్ళీ గమనికలు అనుసరించండి. కానీ ఈ పరిస్థితి లో, మేము ఒక చనిపోయిన హిట్ మేము ను చూడగలరని ముందు ముగింపు కీ ముగింపు. ఇప్పుడు, మేము కొన్ని కొత్త కేటాయించే అవసరం నోడ్స్ ఒక కొత్త కేటాయించాల్సిన అవసరం ఉంటుంది ప్రతి మిగిలిన కోసం నోడ్ మా కీ యొక్క లేఖ. 

ఈ సందర్భంలో, మేము అవసరం ఒక కొత్త నోడ్ కేటాయించే. అప్పుడు మేము H ఇండెక్స్ చేయాలి ఈ కొత్త నోడ్ సూచన. మరోసారి మేము నోడ్ సవరించవచ్చు సూచిస్తున్నాయి అక్షరాలు మార్గం ఇది దారితీసింది ఒక సూచిస్తుంది మా నిఘంటువులో లో కీ. యొక్క asymptotic గురించి కారణం లెట్ ఈ కోసం మా విధానాలు సంక్లిష్టత రెండు ప్రక్రియలు. 

మనం రెండు సందర్భాల్లో సంఖ్య మా అల్గోరిథం పట్టింది వేసింది సంఖ్య నిష్పత్తిలో కీవర్డ్ లో అక్షరాలు. కుడివైపు. మీరు ఒక ఒక పదాన్ని చూడండి అనుకుంటున్నారా ఉన్నప్పుడు trie మీరు ద్వారా iterate అవసరం అక్షరాలు ఒక మీరు వరకు గాని పదం యొక్క చివరి లేదా చేరుకోవడానికి trie లో ఒక డెడ్ ఎండ్ హిట్. 

మరియు మీరు ఒక కీ ఇన్సర్ట్ అనుకుంటున్నారా ఉన్నప్పుడు ఉపయోగించి ఒక trie లోకి విలువ జంట విధానం మేము, చెత్త విషయంలో చర్చించారు మీరు ఒక కొత్త నోడ్ పెడుతోంది ఉంటుంది ప్రతి అక్షరానికి. మరియు మేము రామకృష్ణ ఊహించుకోవటం చేస్తాము స్థిరమైన సమయం ఆపరేషన్ ఉంది. మేము కీ పొడవు భావించవలసి అయితే ఒక స్థిర స్థిరమైన, రెండు హద్దుగా చొప్పించడం మరియు వెతకండి స్థిరాంకం ఒక trie కోసం నిర్వహించకుండా. 

మేము ఈ ఊహ లేకపోతే ఆ కీ పొడవు ఒక స్థిర హద్దుగా స్థిరమైన, అప్పుడు చొప్పించడం మరియు చూసేందుకు, చెత్త సందర్భంలో, సరళంగా ఉంటాయి కీ పొడవు. అంశాల సంఖ్య నిల్వ గమనించండి trie లో లుక్ అప్ ప్రభావితం లేదు లేదా చొప్పించడం సమయం. ఇది మాత్రమే ప్రభావం యొక్క కీ పొడవు. 

దీనికి విరుద్ధంగా, సే, ఇక్కడ ఎంట్రీలను జోడించడం, ఒక హాష్ పట్టిక తయారు ఉంటుంది భవిష్యత్తులో నెమ్మదిగా వెతకండి. ఈ మొదటి వద్ద విజ్ఞప్తి ధ్వని, అయితే మేము గుర్తుపెట్టుకోవాలి ఒక అనుకూలమైన asymptotic సంక్లిష్టత లేదు అర్థం చెప్పొద్దూ డేటా నిర్మాణం తప్పనిసరిగా ఉంది నింద మించి. మేము కూడా నిల్వ భావించాలి ఒక చెత్త లో మేము అవసరం ఒక trie, లో పదం కేసు, నోడ్స్ యొక్క సంఖ్య నిష్పత్తిలో పదం యొక్క పొడవు. 

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

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

ఒక డేటా ఎంచుకునే సమయంలో, గుర్తుంచుకోండి కొంత పని కోసం నిర్మాణం, మేము భావించాలని ఏ రకాల కార్యకలాపాలు డేటా నిర్మాణం అవసరం మద్దతు మరియు ఎంత ప్రదర్శన ఆ ప్రతి మాకు కార్యకలాపాలు విషయాలను. ఈ ఆపరేషన్లు కూడా మారవచ్చు కేవలం దాటి విస్తరించడానికి ప్రాథమిక లుక్ అప్ మరియు చొప్పించడం. మేము ఒక రకమైన అమలు కోరుకున్నారు అనుకుందాం స్వీయపూర్తి కార్యాచరణ యొక్క, చాలా వంటి Google శోధన ఇంజిన్ చేస్తుంది. అంటే, అన్ని కీలను తిరిగి మరియు సమర్థవంతంగా విలువలు ఇది ఒక ఉపసర్గ కలిగి. 

ఒక trie ప్రత్యేకంగా ఉపయోగపడుతుంది ఈ ఆపరేషన్ కోసం. ఇది ద్వారా iterate సూటిగా ఉంది ప్రతి పాత్ర యొక్క కోసం trie ఉపసర్గ. కేవలం, ఒక వెతకండి ఆపరేషన్ వంటి మేము గమనికలు అనుసరించండి కాలేదు పాత్ర పాత్ర. అప్పుడు, మేము చివరిలో వచ్చినప్పుడు ఉపసర్గ, మేము ద్వారా iterate కాలేదు డేటా నిర్మాణం యొక్క మిగిలిన భాగాన్ని కీలు ఏ దాటి నుండి ఈ పాయింట్ ఉపసర్గ కలిగి. 

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

ఆహ్, ఈ ప్రారంభం తిరోగమనం. క్షమించండి. క్షమించాలి. క్షమించాలి. క్షమించాలి. 

నాలుగు సమ్మె. నేను ఉన్నాను. క్షమించాలి. క్షమించాలి. క్షమించాలి. వ్యక్తి మమ్మల్ని ఎవరు ఈ గో క్రేజీ సవరించడానికి ఉంది. 

క్షమించాలి. క్షమించాలి. క్షమించాలి. క్షమించాలి. 

SPEAKER 1: అభినందనలు. ఆ నిజంగా బాగా పని.