1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [బైనరీ శోధన]

2
00:00:02,000 --> 00:00:04,000
[పాట్రిక్ స్చ్మిడ్ - హార్వర్డ్ యూనివర్శిటీ]

3
00:00:04,000 --> 00:00:07,000
[ఈ CS50 ఉంది. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> నేను అక్షర క్రమంలో మీరు డిస్నీ పాత్ర పేర్లు జాబితా ఇచ్చారు ఉంటే

5
00:00:09,000 --> 00:00:11,000
మరియు, మిక్కీ మౌస్ కనుగొనేందుకు మీరు అడిగారు

6
00:00:11,000 --> 00:00:13,000
మీరు ఈ చేయడం గురించి పాటు?

7
00:00:13,000 --> 00:00:15,000
ఒక స్పష్టమైన మార్గం ప్రారంభం నుండి జాబితా స్కాన్ ఉంటుంది

8
00:00:15,000 --> 00:00:18,000
మరియు అది మిక్కీ అని తెలుసుకోవడానికి ప్రతి పేరును తనిఖీ.

9
00:00:18,000 --> 00:00:22,000
అయితే మీరు ముందుకు అలాద్దీన్, ఆలిస్, ఏరియల్, చదివి వంటి,

10
00:00:22,000 --> 00:00:25,000
మీరు త్వరగా జాబితా ముందు వద్ద ప్రారంభమై మంచి ఆలోచన కాదు అని ఉంటుంది.

11
00:00:25,000 --> 00:00:29,000
సరే, బహుశా మీరు జాబితా ముగింపు నుండి వెనక్కి పని ప్రారంభిస్తుంది.

12
00:00:29,000 --> 00:00:33,000
ఇప్పుడు మీరు టార్జాన్, స్టిచ్, స్నో వైట్, మొదలైనవి చదవండి.

13
00:00:33,000 --> 00:00:36,000
ఇంకా, ఈ దాని గురించి వెళ్ళడానికి ఉత్తమ మార్గం వంటి కనిపించడం లేదు.

14
00:00:36,000 --> 00:00:38,000
>> సరే, మీరు ఇలా గురించి వెళ్ళటానికి మరొక మార్గం తగ్గించండి ప్రయత్నించాలి

15
00:00:38,000 --> 00:00:41,000
మీరు చూసే కలిగి పేర్ల జాబితా.

16
00:00:41,000 --> 00:00:43,000
మీరు అవి అక్షర క్రమంలో అని తెలుసు కాబట్టి,

17
00:00:43,000 --> 00:00:45,000
మీరు జాబితా మధ్యలో పేర్లు వద్ద కనిపించాలి

18
00:00:45,000 --> 00:00:49,000
మిక్కీ మౌస్ ఈ పేరు ముందు లేదా తర్వాత ఉంటే మరియు తనిఖీ.

19
00:00:49,000 --> 00:00:51,000
రెండవ వరుసలో చివరి పేరు వద్ద గురించి

20
00:00:51,000 --> 00:00:54,000
మీరు, మిక్కీ కోసం M జాస్మిన్ కోసం J తర్వాత వస్తుంది తెలుసుకుంటారు భావిస్తున్న

21
00:00:54,000 --> 00:00:57,000
కాబట్టి మీరు కేవలం జాబితా యొక్క మొదటి సగం విస్మరించండి భావిస్తున్న.

22
00:00:57,000 --> 00:00:59,000
అప్పుడు మీరు బహుశా చివరి కాలమ్ ఎగువన చూడండి భావిస్తున్న

23
00:00:59,000 --> 00:01:02,000
మరియు అది Rapunzel తో ఆరంభమయ్యి చూడండి.

24
00:01:02,000 --> 00:01:06,000
మిక్కీ Rapunzel ముందు వస్తుంది; మేము అదే చివరి కాలమ్ విస్మరించవచ్చు కనిపిస్తోంది.

25
00:01:06,000 --> 00:01:08,000
శోధన వ్యూహం కొనసాగిస్తూ, మీరు త్వరగా చూస్తారు మిక్కీ

26
00:01:08,000 --> 00:01:11,000
పేర్లు మిగిలిన జాబితా యొక్క మొదటి సగం లో ఉంది

27
00:01:11,000 --> 00:01:14,000
చివరకు మిక్కీ మెర్లిన్ మరియు మిన్నియే మధ్య దాచి ఇక్కడ చూడండి.

28
00:01:14,000 --> 00:01:17,000
>> మీరు ఏమి ప్రధానంగా బైనరీ శోధన ఉంది.

29
00:01:17,000 --> 00:01:22,000
ఈ పేరు సూచిస్తుంది, ఇది ఒక బైనరీ విషయం లో శోధన వ్యూహం అమలు చేస్తుంది.

30
00:01:22,000 --> 00:01:24,000
దీని అర్థం ఏమిటి?

31
00:01:24,000 --> 00:01:27,000
Well, క్రమబద్ధీకరించబడింది అంశాల జాబితా ఇవ్వబడింది, బైనరీ శోధన అల్గోరిథం ఒక బైనరీ నిర్ణయం చేస్తుంది -

32
00:01:27,000 --> 00:01:33,000
ఎడమ లేదా కుడి, కంటే ఎక్కువ లేదా తక్కువ ముందు లేదా తర్వాత అక్షర, కంటే - ప్రతి పాయింట్ వద్ద.

33
00:01:33,000 --> 00:01:35,000
ఇప్పుడు మేము ఈ శోధన అల్గోరిథం పాటు వెళ్ళే ఒక పేరు కలిగి,

34
00:01:35,000 --> 00:01:38,000
యొక్క మరొక ఉదాహరణ చూద్దాం, కానీ ఈ సమయంలో క్రమబద్ధీకరించబడతాయి సంఖ్యల జాబితాను.

35
00:01:38,000 --> 00:01:43,000
మేము క్రమబద్ధీకరించబడతాయి సంఖ్యల ఈ జాబితాలో సంఖ్య 144 శోధిస్తున్న సే.

36
00:01:43,000 --> 00:01:46,000
ముందు వలె, మేము మధ్య ఉందని సంఖ్య ఉద్యోగాలు -

37
00:01:46,000 --> 00:01:50,000
ఈ కేసులో 13 - మరియు 144 కంటే ఎక్కువ లేదా 13 కంటే తక్కువ ఉంటే చూడండి.

38
00:01:50,000 --> 00:01:54,000
ఇది 13 కంటే ఎక్కువ స్పష్టంగా నుంచి, మేము 13 లేదా తక్కువ అని ప్రతిదీ విస్మరించవచ్చు

39
00:01:54,000 --> 00:01:57,000
మరియు కేవలం మిగిలిన సగం పైన దృష్టి.

40
00:01:57,000 --> 00:01:59,000
మేము ఇప్పుడు ఎడమ అంశాలను యొక్క సరి సంఖ్య కలిగి నుండి

41
00:01:59,000 --> 00:02:01,000
మేము కేవలం మధ్య దగ్గరగా ఉందని అనేక ఎంచుకోండి.

42
00:02:01,000 --> 00:02:03,000
ఈ సందర్భంలో మనం 55 ఎంచుకోండి.

43
00:02:03,000 --> 00:02:06,000
మేము సులభంగా 89 ఎంచుకున్న కాలేదు.

44
00:02:06,000 --> 00:02:11,000
సరే. మరలా, 144 55 కంటే ఎక్కువ, కాబట్టి మేము కుడి వెళ్ళండి.

45
00:02:11,000 --> 00:02:14,000
అదృష్టవశాత్తూ మాకు, తర్వాత మధ్య సంఖ్య, 144 ఉంది

46
00:02:14,000 --> 00:02:16,000
మేము చూస్తున్న ఒక.

47
00:02:16,000 --> 00:02:21,000
ఒక బైనరీ శోధన ఉపయోగించి 144 కనుగొనేందుకు కాబట్టి, మేము మాత్రమే 3 దశల్లో దానిని కనుగొనేందుకు చూడగలరని.

48
00:02:21,000 --> 00:02:24,000
మేము ఇక్కడ సరళ శోధన ఉపయోగించారు అనుకుంటే, అది మాకు 12 చర్యలు చేపట్టాయి చేస్తుంది.

49
00:02:24,000 --> 00:02:28,000
వాస్తవానికి, ఈ నుంచి ఈ శోధన పద్ధతి అంశాల సంఖ్య విభజించటం

50
00:02:28,000 --> 00:02:31,000
ఇది ప్రతి దశ కు ఉంది, అది శోధించే అంశం కనుగొంటారు

51
00:02:31,000 --> 00:02:35,000
జాబితాలో అంశాల సంఖ్య యొక్క లాగ్ గురించి లో.

52
00:02:35,000 --> 00:02:37,000
ఇప్పుడు మేము 2 ఉదాహరణలు చూసిన ఆ, యొక్క పరిశీలించి తెలియజేయండి

53
00:02:37,000 --> 00:02:41,000
బైనరీ శోధన అమలు ఒక పునరావృత ఫంక్షన్ కోసం కొన్ని pseudocode.

54
00:02:41,000 --> 00:02:44,000
ఎగువన మొదలు, మేము మేము 4 వాదనలు పడుతుంది ఒక చర్యను కనుగొనడం కలిగి చూడండి:

55
00:02:44,000 --> 00:02:47,000
కీ, అర్రే, మిన్, మరియు మాక్స్.

56
00:02:47,000 --> 00:02:51,000
కీ మేము మునుపటి ఉదాహరణ అలా 144, శోధిస్తున్న ఆ సంఖ్య.

57
00:02:51,000 --> 00:02:54,000
అర్రే మనం శోధిస్తున్న సంఖ్యల జాబితా ఉంది.

58
00:02:54,000 --> 00:02:57,000
Min మరియు మాక్స్ కనీస, గరిష్ట స్థానాల సూచికలు

59
00:02:57,000 --> 00:02:59,000
మేము ప్రస్తుతం చూస్తున్నారు ఆ.

60
00:02:59,000 --> 00:03:03,000
కాబట్టి మేము ప్రారంభించినప్పుడు, min సున్నా ఉంటుంది మరియు గరిష్టంగా శ్రేణి యొక్క గరిష్ట సూచిక ఉంటుంది.

61
00:03:03,000 --> 00:03:07,000
మేము శోధనను కుదించండి, మేము min మరియు మాక్స్ అప్ డేట్

62
00:03:07,000 --> 00:03:10,000
మేము ఇంకా సైన్ చూస్తున్నాయి మాత్రమే శ్రేణి అని

63
00:03:10,000 --> 00:03:12,000
>> మొదటి ఆసక్తికరమైన భాగంగా జె లెట్.

64
00:03:12,000 --> 00:03:14,000
మేము మొదటి విషయం, midpoint కనుగొనడం

65
00:03:14,000 --> 00:03:19,000
సగం మేము ఇప్పటికీ ఆలోచిస్తున్నాయి ఆ శ్రేణిని min మరియు మాక్స్ మధ్య అని సూచిక.

66
00:03:19,000 --> 00:03:22,000
అప్పుడు మేము ఆ midpoint స్థానంలో శ్రేణి యొక్క విలువ చూడండి

67
00:03:22,000 --> 00:03:25,000
మేము శోధిస్తున్న ఆ సంఖ్యను ఆ కీ కంటే తక్కువ ఉంటే మరియు చూడండి.

68
00:03:25,000 --> 00:03:27,000
ఆ స్థానంలో సంఖ్య తక్కువ ఉంటే,

69
00:03:27,000 --> 00:03:31,000
అప్పుడు కీ ఆ స్థానం యొక్క ఎడమ అన్ని సంఖ్యలు కంటే పెద్దదిగా ఉంటుంది అర్థం.

70
00:03:31,000 --> 00:03:33,000
కాబట్టి మేము, మళ్ళీ బైనరీ శోధన ఫంక్షన్ కాల్ చేయవచ్చు

71
00:03:33,000 --> 00:03:36,000
కానీ ఈ సమయంలో కేవలం సగం చదవడానికి min మరియు మాక్స్ పారామితులు నవీకరించడాన్ని

72
00:03:36,000 --> 00:03:40,000
కంటే ఎక్కువ లేదా మేము చూసాము విలువకు సమానము.

73
00:03:40,000 --> 00:03:44,000
మరోవైపు, కీ శ్రేణి యొక్క ప్రస్తుత midpoint వద్ద సంఖ్య కంటే తక్కువ ఉంటే,

74
00:03:44,000 --> 00:03:47,000
మేము ఎడమ వెళ్ళండి మరియు ఎక్కువ అన్ని సంఖ్యలు విస్మరించండి మీరు.

75
00:03:47,000 --> 00:03:52,000
మళ్లీ, మేము min మరియు మాక్స్ నవీకరించారు పరిధికి బైనరీ శోధన కానీ ఈ సమయంలో కాల్

76
00:03:52,000 --> 00:03:54,000
కేవలం దిగువ సగం చేర్చడానికి.

77
00:03:54,000 --> 00:03:57,000
అర్రే ప్రస్తుత midpoint వద్ద విలువ కాదు ఉంటే

78
00:03:57,000 --> 00:04:01,000
కంటే పెద్ద లేదా కీ కంటే చిన్న, అది కీ సమానంగా ఉండాలి.

79
00:04:01,000 --> 00:04:05,000
ఆ విధంగా, మనం కేవలం ప్రస్తుత midpoint ఇండెక్స్ తిరిగి, మరియు మేము పూర్తి చేసిన.

80
00:04:05,000 --> 00:04:09,000
చివరగా, ఇక్కడ ఈ చెక్ కేసు అని సంఖ్య

81
00:04:09,000 --> 00:04:11,000
మేము శోధిస్తున్నారు సంఖ్యల శ్రేణి నిజానికి కాదు.

82
00:04:11,000 --> 00:04:14,000
మేము శోధిస్తున్న ఉంటాయి గరిష్ట సూచిక

83
00:04:14,000 --> 00:04:17,000
కనీస కంటే ఎప్పుడూ తక్కువ, మేము చాలా దూరం మారారు అంటే.

84
00:04:17,000 --> 00:04:20,000
సంఖ్య ఇన్పుట్ శ్రేణి కాదు కాబట్టి, మేము -1 తిరిగి

85
00:04:20,000 --> 00:04:24,000
ఆ ఏమీ సూచించడానికి కనుగొనబడింది.

86
00:04:24,000 --> 00:04:26,000
>> మీరు ఈ అల్గోరిథం పని కోసం గమనించి ఉండవచ్చు

87
00:04:26,000 --> 00:04:28,000
సంఖ్యల జాబితా వేరు ఉంటుంది.

88
00:04:28,000 --> 00:04:31,000
ఇతర మాటల్లో చెప్పాలంటే, కేవలం బైనరీ శోధన ఉపయోగించి 144 పొందవచ్చు

89
00:04:31,000 --> 00:04:34,000
అన్ని సంఖ్యలు అత్యల్ప నుండి అత్యధిక ఆదేశాలు ఉంటే.

90
00:04:34,000 --> 00:04:38,000
ఈ సందర్భంలో కాకపోయి ఉంటే, మేము ప్రతి దశ సంఖ్యలు సగం మినహాయించాలని ఎంతమాత్రం ఉండదు.

91
00:04:38,000 --> 00:04:40,000
కాబట్టి మేము 2 ఎంపికలు ఉన్నాయి.

92
00:04:40,000 --> 00:04:43,000
మేము, బైనరీ శోధన ఉపయోగించి ముందు ఒక క్రమబద్ధీకరించనిది జాబితా తీసుకుని దానికి క్రమం చేయవచ్చు

93
00:04:43,000 --> 00:04:48,000
లేదా మేము దానికి సంఖ్యలు జోడించడానికి వంటి సంఖ్యల జాబితా క్రమబద్ధీకరించబడింది ఖచ్చితంగా చేయవచ్చు.

94
00:04:48,000 --> 00:04:50,000
అందువలన, బదులుగా మేము శోధించడానికి కలిగి కేవలం ఉన్నప్పుడు విభజన,

95
00:04:50,000 --> 00:04:53,000
ఎందుకు అన్ని సమయాల్లో క్రమబద్ధీకరించబడతాయి జాబితా భద్రపరచలేదు?

96
00:04:53,000 --> 00:04:57,000
>> ఒకేసారి అనుమతించేటప్పుడు సంఖ్యల జాబితా ఉంచడానికి ఒక మార్గం క్రమబద్ధీకరించబడింది

97
00:04:57,000 --> 00:04:59,000
ఈ జాబితా నుండి సంఖ్యలు జోడించడానికి లేదా తరలించడానికి

98
00:04:59,000 --> 00:05:02,000
ఒక బైనరీ శోధన చెట్టు అనే ఉపయోగిస్తారు.

99
00:05:02,000 --> 00:05:05,000
ఒక బైనరీ శోధన చెట్టు 3 లక్షణాలను కలిగి ఉండే ఒక డేటా నిర్మాణం.

100
00:05:05,000 --> 00:05:09,000
మొదటి, ఏ నోడ్ యొక్క ఎడమ subtree కంటే తక్కువ మాత్రమే విలువలను కలిగి

101
00:05:09,000 --> 00:05:11,000
లేదా నోడ్ యొక్క విలువకు సమానంగా.

102
00:05:11,000 --> 00:05:15,000
రెండవది, ఒక కణుపు యొక్క కుడి subtree మాత్రమే కంటే ఎక్కువ విలువలను కలిగి

103
00:05:15,000 --> 00:05:17,000
లేదా నోడ్ యొక్క విలువకు సమానంగా.

104
00:05:17,000 --> 00:05:20,000
అన్ని నోడ్ల మరియు, చివరకు, ఎడమ మరియు కుడి subtrees రెండు

105
00:05:20,000 --> 00:05:23,000
కూడా బైనరీ శోధన చెట్లు ఉన్నాయి.

106
00:05:23,000 --> 00:05:26,000
మేము ఇంతకు ముందు ఉపయోగించిన ఒకే సంఖ్యలో ఒక ఉదాహరణ చూడండి యొక్క లెట్.

107
00:05:26,000 --> 00:05:30,000
ఒక కంప్యూటర్ సైన్స్ చెట్టు ముందు ఎప్పుడూ చేసిన మీరు ఆ కోసం,

108
00:05:30,000 --> 00:05:34,000
నాకు కంప్యూటర్ సైన్స్ చెట్టు క్రిందికి చేర్చుతూ మీరు చెబుతూ ప్రారంభించండి.

109
00:05:34,000 --> 00:05:36,000
అవును, మీరు అభిమానం ఉంటాయి చెట్లు కాకుండా,

110
00:05:36,000 --> 00:05:38,000
ఒక కంప్యూటర్ సైన్స్ చెట్టు యొక్క రూట్, ఎగువన

111
00:05:38,000 --> 00:05:41,000
మరియు ఆకులు దిగువన ఉన్నాయి.

112
00:05:41,000 --> 00:05:45,000
ప్రతి చిన్న పెట్టెలో ఒక నోడ్ అంటారు, మరియు నోడ్స్ అంచులు ద్వారా ప్రతి ఇతర కనెక్ట్ చేసారు.

113
00:05:45,000 --> 00:05:48,000
కాబట్టి ఈ చెట్టు యొక్క రూట్, విలువ 13 తో నోడ్ విలువ

114
00:05:48,000 --> 00:05:52,000
ఇది విలువలు 5 మరియు 34 2 పిల్లలు నోడ్ లను కలిగి ఉంది.

115
00:05:52,000 --> 00:05:57,000
ఒక subtree కేవలం మొత్తం చెట్టు యొక్క ఒక ఉప చూడటం ద్వారా ఏర్పడుతుంది ఆ వృక్షం.

116
00:05:57,000 --> 00:06:03,000
>> ఉదాహరణకు, నోడ్ 3 యొక్క ఎడమ subtree నోడ్స్ 0, 1, 2 మరియు రూపొందించినవారు వృక్షం.

117
00:06:03,000 --> 00:06:06,000
కాబట్టి, మేము ఒక బైనరీ శోధన చెట్టు యొక్క లక్షణాలు తిరిగి వెళ్ళడానికి ఉంటే,

118
00:06:06,000 --> 00:06:09,000
మేము, వృక్షంలో ఉండే ప్రతి కణుపు అవి అన్ని 3 లక్షణాలు, నిర్ధారిస్తుందని చూడండి

119
00:06:09,000 --> 00:06:15,000
ఎడమ subtree మాత్రమే కంటే తక్కువ లేదా నోడ్ యొక్క విలువకు సమానంగా విలువలను కలిగి;

120
00:06:15,000 --> 00:06:16,000
అన్ని నోడ్ల కుడి subtree

121
00:06:16,000 --> 00:06:19,000
మాత్రమే కంటే ఎక్కువ లేదా నోడ్ యొక్క విలువకు సమానంగా విలువలను కలిగి; మరియు

122
00:06:19,000 --> 00:06:25,000
అన్ని నోడ్ల ఎడమ మరియు కుడి రెండు subtrees కూడా బైనరీ శోధన చెట్లు ఉన్నాయి.

123
00:06:25,000 --> 00:06:28,000
ఈ చెట్టు వ్యత్యాసంతో ఉంటుంది అయినప్పటికీ, ఇది సరైన బైనరీ శోధన వృక్షం

124
00:06:28,000 --> 00:06:30,000
సంఖ్యల అదే కోసం.

125
00:06:30,000 --> 00:06:32,000
వాస్తవానికి, మీరు సృష్టించవచ్చు అనేక సాధ్యం మార్గాలు ఉన్నాయి

126
00:06:32,000 --> 00:06:35,000
ఈ సంఖ్యలు నుండి చెల్లుబాటు అయ్యే బైనరీ శోధన చెట్టు.

127
00:06:35,000 --> 00:06:38,000
సరే, మేము సృష్టించిన మొదటి ఒక తిరిగి వదలి వేస్తారు.

128
00:06:38,000 --> 00:06:40,000
కాబట్టి మేము ఈ చెట్లు ఏమి చేయగలను?

129
00:06:40,000 --> 00:06:44,000
Well, మేము చాలా సరళంగా కనీస, గరిష్ట విలువలు కనుగొనవచ్చు.

130
00:06:44,000 --> 00:06:46,000
కనీస విలువలు ఎప్పుడూ ఎడమ వెళ్ళి చూడవచ్చు

131
00:06:46,000 --> 00:06:48,000
సందర్శించడానికి no more నోడ్స్ ఉన్నాయి వరకు.

132
00:06:48,000 --> 00:06:53,000
దీనికి విరుద్ధంగా, గరిష్ట ఒక కనుగొనడానికి కేవలం కేవలం ప్రతి సమయంలో సరైన క్రిందికి వెళుతుంది.

133
00:06:54,000 --> 00:06:56,000
>> ఇతర సంఖ్య ఫైండింగ్ కనిష్ట లేదా గరిష్ట కాదని

134
00:06:56,000 --> 00:06:58,000
కేవలం సులభం.

135
00:06:58,000 --> 00:07:00,000
మేము సంఖ్య 89 చూస్తున్న సే.

136
00:07:00,000 --> 00:07:03,000
మేము కేవలం, ప్రతి నోడ్ యొక్క విలువ తనిఖీ మరియు ఎడమ లేదా కుడి వెళ్ళండి

137
00:07:03,000 --> 00:07:06,000
నోడ్ యొక్క విలువ కంటే తక్కువ లేదా ఎక్కువ దాని పై ఆధారపడి

138
00:07:06,000 --> 00:07:08,000
మేము చూస్తున్న ఒక.

139
00:07:08,000 --> 00:07:11,000
కాబట్టి, 13 యొక్క మూలంలో మొదలు, మేము, 89 గొప్ప అని చూడండి

140
00:07:11,000 --> 00:07:13,000
అందువలన మేము వెళ్ళండి.

141
00:07:13,000 --> 00:07:16,000
అప్పుడు మేము 34 కోసం నోడ్ చూడండి, మరియు తిరిగి మేము వెళ్ళండి.

142
00:07:16,000 --> 00:07:20,000
89 ఇంకా 55 కంటే ఎక్కువ, కాబట్టి మేము వెళ్ళి కొనసాగిస్తారు.

143
00:07:20,000 --> 00:07:24,000
మేము అప్పుడు 144 విలువ ఒక నోడ్ ఆలోచన మరియు ఎడమ వెళ్ళండి.

144
00:07:24,000 --> 00:07:26,000
తక్కువ మరియు ఆగండి, 89 అక్కడే ఉంది.

145
00:07:26,000 --> 00:07:31,000
>> మేము మరొక విషయమేమంటే ఒక inorder ట్రావెర్సల్ చేయడం ద్వారా అన్ని సంఖ్యలు ముద్రించాలా ఉంది.

146
00:07:31,000 --> 00:07:35,000
ఒక inorder ట్రావెర్సల్ ఎడమ subtree ప్రతిదీ ముద్రించాలా అర్థం

147
00:07:35,000 --> 00:07:37,000
నోడ్ కూడా ముద్రణకు తరువాత

148
00:07:37,000 --> 00:07:40,000
మరియు సరైన subtree ప్రతిదీ ముద్రించిన తర్వాత.

149
00:07:40,000 --> 00:07:43,000
ఉదాహరణకు, యొక్క మా అభిమాన బైనరీ శోధన చెట్టు తీసుకుందాం

150
00:07:43,000 --> 00:07:46,000
మరియు క్రమబద్ధీకరించబడతాయి క్రమంలో సంఖ్యలు ముద్రించాలా.

151
00:07:46,000 --> 00:07:49,000
మేము 13 యొక్క root ప్రారంభమవుతాయి కాని ముద్రణ 13 ముందు మేము ముద్రించాలా కలిగి

152
00:07:49,000 --> 00:07:51,000
ఎడమ subtree ప్రతిదీ.

153
00:07:51,000 --> 00:07:55,000
కాబట్టి మేము 5 వెళ్ళండి. మేము ఇంకా, మేము ఎడమ అత్యంత నోడ్ కనుగొనేందుకు వరకు చెట్టు మరింత తగ్గుముఖం పడతాయని కలిగి

154
00:07:55,000 --> 00:07:57,000
ఇది సున్నా.

155
00:07:57,000 --> 00:08:00,000
ముద్రణ సున్నా తరువాత, మేము 1 వరకు తిరిగి వెళ్లి ఆ ప్రింట్.

156
00:08:00,000 --> 00:08:03,000
అప్పుడు మేము 2 ఇది కుడి subtree వెళ్లి, ఆ ప్రింట్.

157
00:08:03,000 --> 00:08:05,000
ఇప్పుడు మనము ఆ subtree పూర్తి చేసిన

158
00:08:05,000 --> 00:08:07,000
మేము 3 తిరిగి పెరుగుతుంది మరియు దీనిని ముద్రించవచ్చు.

159
00:08:07,000 --> 00:08:11,000
అప్ తిరిగి కొనసాగిస్తూ, మేము 8 అప్పుడు 5 ప్రింట్ మరియు.

160
00:08:11,000 --> 00:08:13,000
ఇప్పుడు మేము మొత్తం పూర్తి చేశారు, subtree వదిలి

161
00:08:13,000 --> 00:08:17,000
మేము 13 ముద్రించాలా మరియు కుడి subtree పని ప్రారంభించవచ్చు.

162
00:08:17,000 --> 00:08:21,000
మేము 34 క్రిందికి హాప్, కాని ముద్రణ 34 ముందు మేము దాని ఎడమ subtree ముద్రించాలా ఉన్నాయి.

163
00:08:21,000 --> 00:08:27,000
కాబట్టి మేము 21 ముద్రించాలా; అప్పుడు మేము 34 ముద్రించాలా మరియు దాని కుడి subtree సందర్శించండి ను.

164
00:08:27,000 --> 00:08:31,000
55 ఏ ఎడమ subtree కలిగి ఉంటుంది, మేము దాన్ని ప్రింట్ మరియు దాని కుడి subtree లో కొనసాగుతుంది.

165
00:08:31,000 --> 00:08:36,000
144 ఎడమ subtree, అందువలన మేము, 144 తర్వాత, 89 అవ్ట్ ప్రింట్

166
00:08:36,000 --> 00:08:39,000
233 యొక్క చివరకు కుడి అత్యంత నోడ్.

167
00:08:39,000 --> 00:08:44,000
అక్కడ మీరు కలిగి ఉన్నారు; అన్ని సంఖ్యలు అత్యల్ప నుండి అత్యధిక చేయడానికి లో ముద్రించబడి ఉంటాయి.

168
00:08:44,000 --> 00:08:47,000
>> చెట్టు ఏదో కలుపుతోంది అలాగే చాలా సున్నితంగా ఉంటుంది.

169
00:08:47,000 --> 00:08:51,000
మేము అన్ని మేము 3 బైనరీ శోధన చెట్టు లక్షణాలు అనుసరించండి నిర్ధారించుకోండి ఉంది

170
00:08:51,000 --> 00:08:53,000
ఖాళీ ఉన్న మరియు తరువాత విలువను చేర్చండి.

171
00:08:53,000 --> 00:08:55,000
లెట్ యొక్క మేము 7 యొక్క విలువను చేర్చండి అనుకుందాం.

172
00:08:55,000 --> 00:08:58,000
7 కంటే తక్కువ 13 కనుక, మేము ఎడమ వెళ్ళండి.

173
00:08:58,000 --> 00:09:01,000
కానీ 5 కంటే ఎక్కువ, కనుక మేము కుడి సంచరిస్తారు.

174
00:09:01,000 --> 00:09:04,000
అది 8 మరియు 8 ఒక ఆకు నోడ్ కంటే తక్కువగా ఉంటుంది నుంచి, మేము 8 యొక్క ఎడమ బిడ్డకు 7 జోడించండి.

175
00:09:04,000 --> 00:09:09,000
Voila! మేము మా బైనరీ శోధన చెట్టు అనేక జోడించిన.

176
00:09:09,000 --> 00:09:12,000
>> మేము విషయాలు జోడించవచ్చు, మేము మంచి అదే విషయాలు తొలగించలేరు.

177
00:09:12,000 --> 00:09:14,000
దురదృష్టవశాత్తు మాకు, తొలగించడం కొద్దిగా మరింత సంక్లిష్టమైనది -

178
00:09:14,000 --> 00:09:16,000
చాలా, కానీ కొద్దిగా లేదు.

179
00:09:16,000 --> 00:09:18,000
మేము పరిగణించాలి ఆ 3 వివిధ పరిస్థితులలో ఉన్నాయి

180
00:09:18,000 --> 00:09:21,000
బైనరీ శోధన చెట్లు నుండి కారకాలను తొలగించడం ఉన్నప్పుడు.

181
00:09:21,000 --> 00:09:24,000
మొదటి, సులభమైన సందర్భంలో మూలకం ఒక ఆకు నోడ్ ఉంటుంది.

182
00:09:24,000 --> 00:09:27,000
ఈ సందర్భంలో, మనం కేవలం తొలగించండి మరియు మా వ్యాపార తో వెళ్ళండి.

183
00:09:27,000 --> 00:09:30,000
మేము కేవలం జోడించిన 7 తొలగించాలనుకుంటున్నారా సే.

184
00:09:30,000 --> 00:09:34,000
Well, మేము కేవలం దానిని కనుగొనేందుకు, దాన్ని తొలగించండి, అంతే.

185
00:09:35,000 --> 00:09:37,000
నోడ్ మాత్రమే 1 బాల ఉంటే తదుపరి సందర్భంలో.

186
00:09:37,000 --> 00:09:40,000
ఇక్కడ మేము నోడ్ తొలగించగలరు, కాని మేము మొదటి నిర్ధారించడానికి కలిగి

187
00:09:40,000 --> 00:09:42,000
ఇప్పుడు తల్లిదండ్రులు వదిలేస్తే ఆ subtree కనెక్ట్

188
00:09:42,000 --> 00:09:44,000
నోడ్ యొక్క మాతృ కు మేము తొలగించారు.

189
00:09:44,000 --> 00:09:47,000
మేము మా చెట్టు నుండి 3 తొలగించాలనుకుంటున్నారా సే.

190
00:09:47,000 --> 00:09:50,000
మేము ఆ నోడ్ యొక్క బాల మూలకం తీసుకొని నోడ్ యొక్క మాతృ దానిని జోడించండి.

191
00:09:50,000 --> 00:09:54,000
ఈ సందర్భంలో, మనం ఇప్పుడు 5 1 అటాచ్ చేస్తున్నారు.

192
00:09:54,000 --> 00:09:57,000
మేము తెలిసినందున ఈ, బైనరీ శోధన చెట్టు ఆస్తిని అనుసరించి, ఒక సమస్య లేకుండా పనిచేస్తుంది

193
00:09:57,000 --> 00:10:01,000
3 యొక్క ఎడమ subtree లో ప్రతిదీ కంటే తక్కువ 5 ఉంది.

194
00:10:01,000 --> 00:10:05,000
3 యొక్క subtree యొక్క రక్షణ తీసుకుంటారు ఇప్పుడు, మనం దానిని తొలగించవచ్చు.

195
00:10:05,000 --> 00:10:08,000
మూడవ మరియు ఆఖరి వ్యాజ్యం చాలా సంక్లిష్టంగా ఉంటుంది.

196
00:10:08,000 --> 00:10:11,000
మేము తొలగించాలనుకుంటున్నారా నోడ్ 2 పిల్లలు ఈ సందర్భంలో.

197
00:10:11,000 --> 00:10:15,000
ఈ చేయడానికి, మేము మొదటి, తరువాతి అతిపెద్ద విలువ కలిగి నోడ్ కనుగొనేందుకు కలిగి

198
00:10:15,000 --> 00:10:18,000
రెండు స్వాప్ మరియు తరువాత ప్రశ్న లో నోడ్ తొలగించండి.

199
00:10:18,000 --> 00:10:22,000
తరువాతి అతిపెద్ద విలువ 2 పిల్లలు కూడా ఉండకూడదు కలిగి నోడ్ గమనించండి

200
00:10:22,000 --> 00:10:26,000
దాని ఎడమ చైల్డ్ తరువాతి అతిపెద్ద కోసం ఒక మంచి అభ్యర్థి కనుక.

201
00:10:26,000 --> 00:10:30,000
అందువలన, 2 పిల్లలతో ఒక నోడ్ తొలగించడం, 2 ల ఇచ్చిపుచ్చుకోవడంతో మొత్తాలను

202
00:10:30,000 --> 00:10:33,000
మరియు తర్వాత తొలగించడం 2 పైన పేర్కొన్న నిబంధనలను 1 నిర్వహించబడుతుంది.

203
00:10:33,000 --> 00:10:37,000
ఉదాహరణకు, లెట్స్ మేము రూట్ నోడ్, 13 తొలగించండి అనుకుందాం.

204
00:10:37,000 --> 00:10:39,000
మేము మొదటి విషయం మేము చెట్టు తదుపరి అతిపెద్ద విలువ కనుగొనడం

205
00:10:39,000 --> 00:10:41,000
ఇది ఈ సందర్భంలో, 21.

206
00:10:41,000 --> 00:10:46,000
మేము అప్పుడు 13 ఒక ఆకు మరియు 21 మధ్య సమూహం నోడ్ దీనితో 2 నోడ్స్ స్వాప్.

207
00:10:46,000 --> 00:10:49,000
ఇప్పుడు మేము కేవలం 13 తొలగించవచ్చు.

208
00:10:50,000 --> 00:10:53,000
>> ముందుగా పేర్కొన్నట్లు, చెల్లుబాటు అయ్యే బైనరీ శోధన చెట్టు చేయడానికి అనేక సాధ్యం మార్గాలు ఉన్నాయి.

209
00:10:53,000 --> 00:10:56,000
దురదృష్టవశాత్తు మాకు కొందరు కంటే అధ్వాన్నంగా ఉంటాయి.

210
00:10:56,000 --> 00:10:59,000
మేము ఒక బైనరీ శోధన చెట్టు నిర్మించడానికి ఉదాహరణకు, ఏమి జరుగుతుందనే

211
00:10:59,000 --> 00:11:01,000
సంఖ్యల క్రమబద్ధీకరించబడతాయి జాబితా నుండి?

212
00:11:01,000 --> 00:11:04,000
అన్ని సంఖ్యలు కేవలం ప్రతి దశ కుడి జోడించబడ్డాయి.

213
00:11:04,000 --> 00:11:06,000
మేము అనేక శోది ఉంటుంది,

214
00:11:06,000 --> 00:11:08,000
మేము వేరే ఎంపిక లేదు మాత్రమే ప్రతి దశ కుడి కు.

215
00:11:08,000 --> 00:11:11,000
ఈ అన్ని వద్ద సరళ శోధన కంటే మెరుగైన లేదు.

216
00:11:11,000 --> 00:11:13,000
మేము వాటిని ఇక్కడ కవర్ కాకపోయినప్పటికీ,, క్లిష్టమైన, ఇతర ఉన్నాయి

217
00:11:13,000 --> 00:11:16,000
ఈ జరిగే లేదని చేసే డేటా నిర్మాణాలు.

218
00:11:16,000 --> 00:11:18,000
అయితే, ఈ నివారించడానికి చేయవచ్చు ఒక సులభమైన విషయం

219
00:11:18,000 --> 00:11:21,000
కేవలం యాదృచ్చికంగా షఫుల్ ఇన్పుట్ విలువలకు.

220
00:11:21,000 --> 00:11:26,000
ఇది యాదృచ్ఛిక అవకాశం ద్వారా సంఖ్యల దిగి జాబితా క్రమబద్ధీకరించబడింది ఆ అంతగా లేదు.

221
00:11:26,000 --> 00:11:29,000
ఒకవేళ ఇదే జరిగితే, కాసినోలు కాలం వ్యాపారంలో నిలదొక్కుకోవడానికి కాదు.

222
00:11:29,000 --> 00:11:31,000
>> అక్కడ మీరు కలిగి ఉన్నారు.

223
00:11:31,000 --> 00:11:34,000
మీరు ఇప్పుడు బైనరీ శోధన మరియు బైనరీ శోధన చెట్లు గురించి తెలుసు.

224
00:11:34,000 --> 00:11:36,000
నేను పాట్రిక్ స్చ్మిడ్ ఉన్నాను, మరియు ఈ CS50 ఉంది.

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
ఒక స్పష్టమైన మార్గం నుండి జాబితా స్కాన్ ఉంటుంది ... [బీప్]

227
00:11:43,000 --> 00:11:46,000
... అంశాల సంఖ్య ... YEP

228
00:11:46,000 --> 00:11:50,000
[నవ్విన]

229
00:11:50,000 --> 00:11:55,000
... 234 ... augh యొక్క నోడ్ పోస్ట్.

230
00:11:55,000 --> 00:11:58,000
>> అవును! అది -