1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Jinsi gani unaweza kuwakilisha wanachama wote wako katika familia ya kompyuta?

2
00:00:10,790 --> 00:00:12,390
Tunaweza tu kutumia orodha,

3
00:00:12,390 --> 00:00:14,400
lakini kuna ngazi ya wazi hapa.

4
00:00:14,400 --> 00:00:17,110
>> Hebu sema tuko mwanzo na bibi kubwa-yako, Alice.

5
00:00:17,110 --> 00:00:19,030
Yeye ana wana 2, Bob

6
00:00:19,030 --> 00:00:21,310
na babu yako, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie ana watoto 3,

8
00:00:23,190 --> 00:00:26,730
mjomba wako, Dave, shangazi yako, Hawa, na baba yako, Fred.

9
00:00:26,730 --> 00:00:28,750
Wewe ni mtoto wa Fred tu.

10
00:00:28,750 --> 00:00:30,950
>> Kwa nini kuandaa familia yako kwa njia hii

11
00:00:30,950 --> 00:00:34,010
kuwa bora zaidi kuliko uwakilishi rahisi orodha?

12
00:00:34,010 --> 00:00:36,630
Moja ya sababu ni kwamba hii muundo wa kihierarkia,

13
00:00:36,630 --> 00:00:39,660
iitwayo 'mti,' ina habari zaidi kuliko orodha rahisi.

14
00:00:40,540 --> 00:00:43,520
Tunajua mahusiano ya kifamilia kati ya kila mtu

15
00:00:43,520 --> 00:00:45,440
tu kwa kuchunguza mti.

16
00:00:45,440 --> 00:00:47,250
Pia, inaweza kuharakisha

17
00:00:47,250 --> 00:00:50,010
kuangalia-up wakati kiasi kikubwa, kama data mti ni Iliyopangwa.

18
00:00:50,010 --> 00:00:53,850
>> Hatuwezi kuchukua faida ya kwamba hapa, lakini tutaweza kuona mfano wa hii hivi karibuni.

19
00:00:53,850 --> 00:00:56,150
Kila mtu ni kuwakilishwa na nodi kwenye mti.

20
00:00:56,680 --> 00:00:58,370
Nodes unaweza kuwa nodes mtoto

21
00:00:58,370 --> 00:01:00,350
kama vile nodi mzazi.

22
00:01:00,350 --> 00:01:02,390
Haya ni maneno ya kitaalamu

23
00:01:02,390 --> 00:01:05,220
hata wakati wa kutumia miti kwa ajili ya mambo badala ya familia.

24
00:01:05,220 --> 00:01:07,940
Nodi Alice ina watoto 2 na wazazi,

25
00:01:07,940 --> 00:01:11,500
wakati nodi Charlie ana watoto 3 na 1 mzazi.

26
00:01:11,500 --> 00:01:14,330
>> nodi jani ni moja kwamba hana watoto wowote

27
00:01:14,330 --> 00:01:16,410
makali ya nje ya mti.

28
00:01:16,410 --> 00:01:18,520
nodi topmost ya mti, nodi mizizi,

29
00:01:18,520 --> 00:01:20,240
hana mzazi.

30
00:01:20,240 --> 00:01:23,170
>> mti binary ni aina maalum ya mti,

31
00:01:23,170 --> 00:01:26,720
ambayo ina kila node, saa wengi, watoto 2.

32
00:01:26,720 --> 00:01:30,490
Hapa ni struct ya nodi ya mti binary katika C.

33
00:01:31,560 --> 00:01:34,530
Kila nodi ina baadhi ya data yanayohusiana na hayo

34
00:01:34,530 --> 00:01:36,520
na 2 kuyatumia kwa nodes nyingine.

35
00:01:36,520 --> 00:01:38,110
>> Katika familia mti wetu,

36
00:01:38,110 --> 00:01:40,900
data zinazohusiana ilikuwa jina la kila mtu.

37
00:01:40,900 --> 00:01:43,850
Hapa ni int, ingawa inaweza kuwa kitu chochote.

38
00:01:44,510 --> 00:01:46,200
Kama zinageuka,

39
00:01:46,200 --> 00:01:48,990
mti binary isingekuwa uwakilishi mzuri kwa ajili ya familia,

40
00:01:48,990 --> 00:01:51,960
tangu watu mara nyingi kuwa na watoto zaidi ya 2.

41
00:01:51,960 --> 00:01:53,510
>> tafuta binary mti

42
00:01:53,510 --> 00:01:56,380
ni maalum, aliamuru ya aina ya mti binary

43
00:01:56,380 --> 00:01:58,090
ambayo inaruhusu yetu kuangalia maadili haraka.

44
00:01:58,740 --> 00:02:00,050
Unaweza kuwa niliona

45
00:02:00,050 --> 00:02:02,010
kwamba kila nodi chini mizizi ya mti

46
00:02:02,010 --> 00:02:04,620
ni mizizi ya mti mwingine, aitwaye 'subtree.'

47
00:02:04,960 --> 00:02:07,090
Hapa, mizizi ya mti ni 6,

48
00:02:07,090 --> 00:02:09,860
na mtoto wake, 2, ni mizizi ya subtree.

49
00:02:09,860 --> 00:02:11,870
>> Katika mti binary tafuta

50
00:02:11,870 --> 00:02:15,790
maadili yote ya nodi haki subtree

51
00:02:15,790 --> 00:02:18,690
ni kubwa zaidi kuliko thamani ya nodi. Hapa: 6.

52
00:02:18,690 --> 00:02:22,640
Naam, maadili katika subtree nodi wa kushoto wa

53
00:02:24,540 --> 00:02:26,890
ni chini ya thamani ya nodi.

54
00:02:26,890 --> 00:02:28,620
Kama tunahitaji kushughulikia maadili duplicate,

55
00:02:28,620 --> 00:02:31,760
tunaweza kubadili aidha ya wale wa usawa wa huru,

56
00:02:31,760 --> 00:02:34,410
maana maadili kufanana unaweza kuanguka ama upande wa kushoto au kulia,

57
00:02:34,410 --> 00:02:37,400
muda mrefu kama sisi ni thabiti kuhusu hilo hela.

58
00:02:37,400 --> 00:02:39,620
Mti huu ni binary tafuta mti

59
00:02:39,620 --> 00:02:41,540
kwa kuwa inafuatia sheria hizi.

60
00:02:42,320 --> 00:02:46,020
>> Hii ni jinsi bila kuangalia kama sisi akageuka nodes wote katika structs C.

61
00:02:46,880 --> 00:02:48,410
Ona kwamba kama mtoto ni kukosa,

62
00:02:48,410 --> 00:02:50,340
pointer ni null.

63
00:02:50,340 --> 00:02:53,270
Jinsi gani sisi kuangalia kuona kama ni 7 katika mti?

64
00:02:53,270 --> 00:02:55,020
Sisi kuanza katika mizizi.

65
00:02:55,020 --> 00:02:58,690
Saba, ni mkubwa kuliko 6, hivyo kama ni katika mti, ni lazima kuwa na haki.

66
00:02:59,680 --> 00:03:03,650
Kisha, ni chini ya 8, hivyo ni lazima kushoto.

67
00:03:03,650 --> 00:03:06,210
Hapa, tumepata 7.

68
00:03:06,210 --> 00:03:08,160
Sasa, sisi itabidi kuangalia kwa 5.

69
00:03:08,160 --> 00:03:11,500
Tano ni chini ya 6, hivyo ni lazima kwa upande wa kushoto.

70
00:03:11,500 --> 00:03:13,460
Tano, ni mkubwa kuliko 2,

71
00:03:13,460 --> 00:03:15,010
hivyo ni lazima kuwa na haki,

72
00:03:15,010 --> 00:03:18,100
na pia ni mkuu kuliko 4, hivyo ni lazima haki tena.

73
00:03:18,100 --> 00:03:20,300
Hata hivyo, kuna mtoto yeyote hapa.

74
00:03:20,300 --> 00:03:22,000
pointer ni null.

75
00:03:22,000 --> 00:03:24,270
Hii ina maana kwamba ni 5 si katika mti wetu.

76
00:03:24,270 --> 00:03:27,250
>> Tunaweza kutafuta mti binary kwa kificho zifuatazo:

77
00:03:28,430 --> 00:03:31,140
Katika kila nodi, sisi kuangalia kuona kama tumepata

78
00:03:31,140 --> 00:03:33,020
thamani sisi ni kuangalia kwa.

79
00:03:33,020 --> 00:03:35,740
Kama hatuwezi kupata hiyo, sisi kuamua kama ni lazima kuwa na

80
00:03:35,740 --> 00:03:38,990
juu na kushoto au kulia kuangalia kwamba subtree.

81
00:03:38,990 --> 00:03:41,160
Kitanzi hii itaendelea chini ya mti

82
00:03:41,160 --> 00:03:44,190
mpaka hakuna nodi mtoto juu ya aidha kushoto au kulia.

83
00:03:45,190 --> 00:03:48,600
>> Kumbuka kwamba 5 hakuwa katika mti.

84
00:03:48,600 --> 00:03:50,460
Jinsi gani sisi kuingiza?

85
00:03:50,460 --> 00:03:52,370
mchakato inaonekana sawa na kutafuta.

86
00:03:52,370 --> 00:03:54,830
Sisi iterate chini mti kuanzia 6,

87
00:03:54,830 --> 00:03:57,040
kushoto na 2,

88
00:03:57,040 --> 00:03:59,140
haki ya 4,

89
00:03:59,140 --> 00:04:02,500
na haki tena, lakini hana mtoto 4 upande huu.

90
00:04:02,500 --> 00:04:06,090
Hii itakuwa ni nafasi mpya kwa ajili ya 5,

91
00:04:06,090 --> 00:04:08,500
na itakuwa kuanza na watoto.

92
00:04:09,020 --> 00:04:12,220
>> Jinsi ya kufunga ni shughuli ya juu ya mti binary search?

93
00:04:12,220 --> 00:04:15,410
Kumbuka kwamba Bigohnotation inataka kutoa amefungwa juu.

94
00:04:15,410 --> 00:04:17,390
Katika kesi mbaya,

95
00:04:17,390 --> 00:04:19,480
mti yetu inaweza tu kuwa orodha zilizounganishwa

96
00:04:19,480 --> 00:04:22,220
maana kwamba insertion, kufutwa, na tafuta

97
00:04:22,220 --> 00:04:25,380
inaweza kuchukua muda sawia na idadi ya pingili katika mti.

98
00:04:25,380 --> 00:04:27,380
Hii ni O (n).

99
00:04:27,380 --> 00:04:30,690
>> Kwa mfano, zifuatazo ni halali binary tafuta mti.

100
00:04:31,850 --> 00:04:34,020
Hata hivyo, kama sisi kujaribu kupata 9,

101
00:04:34,020 --> 00:04:36,760
tuna traverse kila nodi.

102
00:04:36,760 --> 00:04:39,120
Ni hakuna bora kuliko orodha zinazoungwa.

103
00:04:39,120 --> 00:04:41,410
Kimsingi, sisi wanataka kila nodi

104
00:04:41,410 --> 00:04:44,120
ya binary wetu mti tafuta kuwa na watoto 2.

105
00:04:44,120 --> 00:04:46,370
Kwa njia hii, insertion, kufuta na tafuta

106
00:04:46,370 --> 00:04:50,190
bila kuchukua, saa mbaya, O (logi n) wakati.

107
00:04:50,190 --> 00:04:52,470
mti mbele inaweza kuwa zaidi ya uwiano,

108
00:04:52,470 --> 00:04:54,140
kama hii.

109
00:04:54,140 --> 00:04:57,980
Sasa, akatazama juu thamani yoyote inachukua, saa wengi, 3 hatua.

110
00:04:57,980 --> 00:04:59,460
Mti huu ni sawa,

111
00:04:59,460 --> 00:05:01,190
maana kwamba ni ndogo ina kina

112
00:05:01,190 --> 00:05:03,680
jamaa na idadi ya nodi.

113
00:05:03,680 --> 00:05:06,300
>> Kuangalia kwa thamani katika mti uwiano binary tafuta

114
00:05:06,300 --> 00:05:09,540
ni sawa na tafuta binary kwenye safu Iliyopangwa.

115
00:05:09,540 --> 00:05:12,290
Kwa kweli, kama hatuna haja ya kuingiza au kufuta vitu,

116
00:05:12,290 --> 00:05:15,150
wanatenda hasa kwa njia hiyo.

117
00:05:15,150 --> 00:05:17,600
Hata hivyo, muundo wa mti ni bora

118
00:05:17,600 --> 00:05:19,530
kwa ajili ya kuchukua insertions na kufuta maneno

119
00:05:20,360 --> 00:05:22,670
>> Jina langu ni Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Hii ni CS50.