1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] మీరు ఒక కంప్యూటర్ లో మీ కుటుంబ సభ్యులు ఎలా ప్రాతినిధ్యం వహించే రీతిలో?

2
00:00:10,790 --> 00:00:12,390
మేము కేవలం, ఒక జాబితా ఉపయోగించవచ్చు

3
00:00:12,390 --> 00:00:14,400
కానీ స్పష్టమైన సోపానక్రమం ఇక్కడ ఉంది.

4
00:00:14,400 --> 00:00:17,110
>> లెట్ యొక్క మీ తాతమ్మ, ఆలిస్ ప్రారంభించి చేస్తున్నారు అనుకోండి.

5
00:00:17,110 --> 00:00:19,030
ఆమె 2 కుమారులు, బాబ్ ఉంది

6
00:00:19,030 --> 00:00:21,310
మరియు మీ తాత, చార్లీ.

7
00:00:21,310 --> 00:00:23,190
చార్లీ, 3 పిల్లలు

8
00:00:23,190 --> 00:00:26,730
మీ మామ, డేవ్, మీ అత్త, ఈవ్, మరియు మీ తండ్రి, ఫ్రెడ్.

9
00:00:26,730 --> 00:00:28,750
మీరు ఫ్రెడ్ యొక్క ఏకైక సంతానం ఉన్నారు.

10
00:00:28,750 --> 00:00:30,950
>> ఎందుకు ఈ విధంగా మీ కుటుంబ సభ్యులు నిర్వహించే చేస్తుంది

11
00:00:30,950 --> 00:00:34,010
సాధారణ జాబితా ప్రాతినిధ్యం కన్నా మెరుగుగా?

12
00:00:34,010 --> 00:00:36,630
ఒక కారణం అని ఈ తరతమ శ్రేణి నిర్మాణంలో,

13
00:00:36,630 --> 00:00:39,660
ఒక అని 'చెట్టు,' ఒక సాధారణ జాబితా కంటే ఎక్కువ సమాచారాన్ని కలిగి ఉంది.

14
00:00:40,540 --> 00:00:43,520
మేము ప్రతి ఒక్కరూ మధ్య కుటుంబ సంబంధాలను తెలుసు

15
00:00:43,520 --> 00:00:45,440
కేవలం చెట్టు పరీక్షించి.

16
00:00:45,440 --> 00:00:47,250
అలాగే, ఇది వేగవంతం చేయవచ్చు

17
00:00:47,250 --> 00:00:50,010
లుక్ అప్ సమయం అద్భుతంగా, చెట్టు డేటా క్రమబద్ధీకరించబడింది ఉంటే.

18
00:00:50,010 --> 00:00:53,850
>> మేము ఇక్కడ ఆ ప్రయోజనాన్ని కానీ మేము త్వరలోనే ఈ ఒక ఉదాహరణ చూస్తారు.

19
00:00:53,850 --> 00:00:56,150
ప్రతి వ్యక్తి చెట్టు మీద ఒక నోడ్ ప్రాతినిధ్యం వహిస్తుంది.

20
00:00:56,680 --> 00:00:58,370
నోడ్స్ చైల్డ్ నోడ్స్ కలిగి

21
00:00:58,370 --> 00:01:00,350
అలాగే ఒక పేరెంట్ నోడ్ వంటి.

22
00:01:00,350 --> 00:01:02,390
ఈ సాంకేతిక పదాలు

23
00:01:02,390 --> 00:01:05,220
కుటుంబాలు పాటు విషయాల కోసం చెట్లు ఉపయోగించినప్పుడు కూడా.

24
00:01:05,220 --> 00:01:07,940
ఆలిస్ యొక్క నోడ్, 2 పిల్లలు మరియు తల్లిదండ్రులు ఉంది

25
00:01:07,940 --> 00:01:11,500
చార్లీ యొక్క Node 3 పిల్లలు మరియు 1 మాతృ ఉండగా.

26
00:01:11,500 --> 00:01:14,330
>> ఒక ఆకు నోడ్ ఏ పిల్లలు లేని ఒకటి

27
00:01:14,330 --> 00:01:16,410
చెట్టు యొక్క బయటి అంచుకు న.

28
00:01:16,410 --> 00:01:18,520
చెట్టు యొక్క చాలా ఎత్తైన నోడ్, రూట్ నోడ్,

29
00:01:18,520 --> 00:01:20,240
ఏ పేరెంట్ ఉంది.

30
00:01:20,240 --> 00:01:23,170
>> ఒక బైనరీ చెట్టు, చెట్టు యొక్క ఒక నిర్దిష్ట రకం

31
00:01:23,170 --> 00:01:26,720
దీనిలో ప్రతి నోడ్, అత్యంత, 2 పిల్లలు.

32
00:01:26,720 --> 00:01:30,490
ఇక్కడ C. ఒక బైనరీ చెట్టు ఒక నోడ్ యొక్క struct ఉంది

33
00:01:31,560 --> 00:01:34,530
ప్రతి నోడ్ దాని సంబంధం కొన్ని డేటాను కలిగి ఉంది

34
00:01:34,530 --> 00:01:36,520
ఇతర నోడ్స్ మరియు 2 పాయింటర్లు.

35
00:01:36,520 --> 00:01:38,110
>> మా కుటుంబం చెట్టు లో,

36
00:01:38,110 --> 00:01:40,900
సంబంధం డేటా ప్రతి వ్యక్తి యొక్క పేరు.

37
00:01:40,900 --> 00:01:43,850
ఇది ఏదైనా కావచ్చు అయితే అది, ఒక పూర్ణాంకానికి ఉంది.

38
00:01:44,510 --> 00:01:46,200
దీనిని టర్న్స్,

39
00:01:46,200 --> 00:01:48,990
ఒక బైనరీ చెట్టు, ఒక కుటుంబం కోసం మంచి ప్రాతినిధ్యం కాదు

40
00:01:48,990 --> 00:01:51,960
ప్రజలు తరచుగా కంటే ఎక్కువ 2 పిల్లలు నుండి.

41
00:01:51,960 --> 00:01:53,510
>> ఒక బైనరీ శోధన చెట్టు

42
00:01:53,510 --> 00:01:56,380
బైనరీ చెట్టు యొక్క ఒక ప్రత్యేక ఆదేశించాడు రకం

43
00:01:56,380 --> 00:01:58,090
మాకు త్వరగా విలువలు చూడండి అనుమతిస్తుంది.

44
00:01:58,740 --> 00:02:00,050
మీరు గమనించి ఉండవచ్చు

45
00:02:00,050 --> 00:02:02,010
ఒక చెట్టు యొక్క root క్రింద ప్రతి నోడ్

46
00:02:02,010 --> 00:02:04,620
మరొక చెట్టు యొక్క రూట్, ఒక 'subtree.' అంటారు

47
00:02:04,960 --> 00:02:07,090
ఇక్కడ, చెట్టు యొక్క రూట్, 6

48
00:02:07,090 --> 00:02:09,860
మరియు దాని బిడ్డ, 2, ఒక subtree యొక్క మూలం.

49
00:02:09,860 --> 00:02:11,870
>> ఒక బైనరీ శోధన చెట్టు లో

50
00:02:11,870 --> 00:02:15,790
ఒక నోడ్ యొక్క అన్ని విలువలను కుడి subtree యొక్క

51
00:02:15,790 --> 00:02:18,690
నోడ్ యొక్క విలువ కంటే అధికంగా ఉంటాయి. ఇక్కడ: 6.

52
00:02:18,690 --> 00:02:22,640
Well, ఒక కణుపు యొక్క ఎడమ subtree విలువలు

53
00:02:24,540 --> 00:02:26,890
నోడ్ యొక్క విలువ కంటే తక్కువ.

54
00:02:26,890 --> 00:02:28,620
మేము నకిలీ విలువలు నిర్వహించడానికి అవసరం ఉంటే,

55
00:02:28,620 --> 00:02:31,760
మేము, ఒక వదులుగా అసమానత గానీ వారిలో మార్చవచ్చు

56
00:02:31,760 --> 00:02:34,410
ఒకేలా విలువలు ఎడమ లేదా కుడి గాని వస్తుంది అర్థం,

57
00:02:34,410 --> 00:02:37,400
కాలం మేము అంతా దాని గురించి స్థిరమైన ఉన్నారు.

58
00:02:37,400 --> 00:02:39,620
ఈ చెట్టు ఒక బైనరీ శోధన వృక్షం

59
00:02:39,620 --> 00:02:41,540
ఈ నిబంధనలను అనుసరించి ఎందుకంటే.

60
00:02:42,320 --> 00:02:46,020
>> ఈ మేము సి structs అన్ని నోడ్స్ మారిన ఉంటే అది చూస్తారు ఎలా ఉంది.

61
00:02:46,880 --> 00:02:48,410
గమనికను ఒక బిడ్డ లేదు,

62
00:02:48,410 --> 00:02:50,340
పాయింటర్ NULL.

63
00:02:50,340 --> 00:02:53,270
మేము ఎలా 7 చెట్టు లో ఉంటే చూడటానికి తనిఖీ చెయ్యాలి?

64
00:02:53,270 --> 00:02:55,020
మేము root వద్ద ప్రారంభించండి.

65
00:02:55,020 --> 00:02:58,690
అది చెట్టు లో ఉంటే ఏడు 6 కంటే ఎక్కువగా ఉంటుంది, అందువలన, కుడి వైపు ఉండాలి.

66
00:02:59,680 --> 00:03:03,650
అప్పుడు 8 కంటే తక్కువ, కాబట్టి ఇది ఎడమ ఉండాలి.

67
00:03:03,650 --> 00:03:06,210
ఇక్కడ, మేము 7 గుర్తించారు.

68
00:03:06,210 --> 00:03:08,160
ఇప్పుడు మేము 5 తనిఖీ చేస్తాము.

69
00:03:08,160 --> 00:03:11,500
ఐదు 6 కంటే తక్కువ, కాబట్టి ఇది ఎడమ ఉంటుంది.

70
00:03:11,500 --> 00:03:13,460
ఐదు, 2 కంటే ఎక్కువ

71
00:03:13,460 --> 00:03:15,010
అది కుడి ఉండాలి

72
00:03:15,010 --> 00:03:18,100
మరియు అది కూడా 4 కంటే ఎక్కువ, కాబట్టి అది కుడి మళ్లీ ఉండాలి.

73
00:03:18,100 --> 00:03:20,300
అయితే, ఏ చైల్డ్ ఇక్కడ ఉంది.

74
00:03:20,300 --> 00:03:22,000
పాయింటర్ NULL.

75
00:03:22,000 --> 00:03:24,270
ఈ 5 మా చెట్టు లో కాదు అర్థం.

76
00:03:24,270 --> 00:03:27,250
>> మేము క్రింది కోడ్ బైనరీ చెట్టు శోధించవచ్చు:

77
00:03:28,430 --> 00:03:31,140
ప్రతి కణుపు వద్ద, మేము కనుగొన్నాము లేదో తనిఖీ చెయ్యండి

78
00:03:31,140 --> 00:03:33,020
మేము శోధిస్తున్న విలువ.

79
00:03:33,020 --> 00:03:35,740
మేము దానిని కనుగొనేందుకు లేకపోతే అది ఉండాలి ఉంటే, మేము గుర్తించడానికి

80
00:03:35,740 --> 00:03:38,990
ఎడమ లేదా కుడి మరియు ఆ subtree తనిఖీ.

81
00:03:38,990 --> 00:03:41,160
ఈ లూప్ చెట్టు డౌన్ కొనసాగుతుంది

82
00:03:41,160 --> 00:03:44,190
ఎడమ లేదా కుడి గాని ఎటువంటి చైల్డ్ నోడ్ వచ్చేవరకు.

83
00:03:45,190 --> 00:03:48,600
>> 5 చెట్టు కాదు అని గుర్తుంచుకోండి.

84
00:03:48,600 --> 00:03:50,460
మేము ఎలా అది ఇన్సర్ట్ చెయ్యాలి?

85
00:03:50,460 --> 00:03:52,370
ప్రక్రియ అన్వేషణ పోలి ఉంది.

86
00:03:52,370 --> 00:03:54,830
మేము, 6 నుంచి ప్రారంభమయ్యే చెట్టు డౌన్ iterate

87
00:03:54,830 --> 00:03:57,040
2 ఎడమ,

88
00:03:57,040 --> 00:03:59,140
4 హక్కు,

89
00:03:59,140 --> 00:04:02,500
మరియు కుడి మళ్ళీ, కానీ 4 ఈ వైపు కాదు బిడ్డ ఉన్నాడు.

90
00:04:02,500 --> 00:04:06,090
ఈ, 5 కోసం కొత్త స్థానము

91
00:04:06,090 --> 00:04:08,500
మరియు అది పిల్లలు లేరు ప్రారంభమౌతుంది.

92
00:04:09,020 --> 00:04:12,220
>> ఎంత వేగంగా ఒక బైనరీ శోధన చెట్టు మీద కార్యకలాపాలు ఉంటాయి?

93
00:04:12,220 --> 00:04:15,410
Bigohnotation ఒక ఉన్నత బౌండ్ అందించడం SSA గుర్తుంచుకోండి.

94
00:04:15,410 --> 00:04:17,390
చెత్త సందర్భంలో,

95
00:04:17,390 --> 00:04:19,480
మా చెట్టు కేవలం అనుబంధ జాబితా ఉంటుంది

96
00:04:19,480 --> 00:04:22,220
ఆ చొప్పించడం, తొలగింపు, మరియు శోధన అర్థం

97
00:04:22,220 --> 00:04:25,380
చెట్టు లో నోడ్ ల సంఖ్య నిష్పత్తిలో సమయం పడుతుంది.

98
00:04:25,380 --> 00:04:27,380
ఈ O (n) ఉంది.

99
00:04:27,380 --> 00:04:30,690
>> ఉదాహరణకు, ఈ క్రింది చెల్లుబాటు అయ్యే బైనరీ శోధన వృక్షం.

100
00:04:31,850 --> 00:04:34,020
అయితే, మేము 9 కనుగొనేందుకు ప్రయత్నించండి ఉంటే,

101
00:04:34,020 --> 00:04:36,760
మేము ప్రతి నోడ్ ప్రయాణించేందుకు ఉన్నాయి.

102
00:04:36,760 --> 00:04:39,120
ఇది ఒక లింక్ జాబితా కంటే ఉత్తమం.

103
00:04:39,120 --> 00:04:41,410
సాధారణంగా, మేము ప్రతి నోడ్ కావాలో

104
00:04:41,410 --> 00:04:44,120
మా బైనరీ శోధన చెట్టు యొక్క 2 పిల్లలు.

105
00:04:44,120 --> 00:04:46,370
ఈ విధంగా, చొప్పించడం, తొలగింపు మరియు శోధన

106
00:04:46,370 --> 00:04:50,190
, ఘోరంగా, O (n లాగ్) సమయం తీసుకుంటుంది.

107
00:04:50,190 --> 00:04:52,470
ముందు నుండి చెట్టు, మరింత సంతులిత ఉంటుంది

108
00:04:52,470 --> 00:04:54,140
దీన్ని ఇష్టపడుతున్నారు.

109
00:04:54,140 --> 00:04:57,980
ఇప్పుడు, ఏ విలువ చూస్తూ 3 దశలు, అత్యంత వద్ద, పడుతుంది.

110
00:04:57,980 --> 00:04:59,460
ఈ చెట్టు, సమతుల్య ఉంది

111
00:04:59,460 --> 00:05:01,190
అని అర్థం కనీసపు లోతు ఉంది

112
00:05:01,190 --> 00:05:03,680
ల సంఖ్య సంబంధించి.

113
00:05:03,680 --> 00:05:06,300
>> సమతుల్య బైనరీ శోధన చెట్టు ఒక విలువ గురించి

114
00:05:06,300 --> 00:05:09,540
ఒక క్రమబద్ధీకరించబడతాయి శ్రేణి ద్వియాంశ శోధన పోలి ఉంటుంది.

115
00:05:09,540 --> 00:05:12,290
నిజానికి, మేము అంశాలను ఇన్సర్ట్ లేదా తొలగించవలసిన అవసరం లేకపోతే,

116
00:05:12,290 --> 00:05:15,150
వారు అదే విధంగా ప్రవర్తిస్తాయి.

117
00:05:15,150 --> 00:05:17,600
అయితే, ఒక చెట్టు నిర్మాణం బాగా ఉంది

118
00:05:17,600 --> 00:05:19,530
నిర్వహణ ప్రక్షిప్తాలు మరియు తొలగింపులు కోసం

119
00:05:20,360 --> 00:05:22,670
>> నా పేరు Bannus వాన్ డెర్ Kloot ఉంది.

120
00:05:22,670 --> 00:05:24,030
ఈ CS50 ఉంది.