1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Kif inti tirrappreżenta l-membri kollha tal-familja tiegħek fil-kompjuter?

2
00:00:10,790 --> 00:00:12,390
Aħna jista 'sempliċement jużaw lista,

3
00:00:12,390 --> 00:00:14,400
iżda hemm ġerarkija ċara hawnhekk.

4
00:00:14,400 --> 00:00:17,110
>> Ejja ngħidu aħna qed jibdew bil tiegħek great-nanna, Alice.

5
00:00:17,110 --> 00:00:19,030
Hija għandha 2 wlied, Bob

6
00:00:19,030 --> 00:00:21,310
u grandfather tiegħek, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie għandha 3-tfal,

8
00:00:23,190 --> 00:00:26,730
ziju tiegħek, Dave, zija tiegħek, Eve, u missierek, Fred.

9
00:00:26,730 --> 00:00:28,750
Inti tifel biss Fred s.

10
00:00:28,750 --> 00:00:30,950
>> Għaliex kieku jorganizza membri tal-familja tiegħek b'dan il-mod

11
00:00:30,950 --> 00:00:34,010
tkun aħjar minn-rappreżentanza lista sempliċi?

12
00:00:34,010 --> 00:00:36,630
Raġuni waħda hija li dan ġerarkika istruttura,

13
00:00:36,630 --> 00:00:39,660
imsejħa "siġra," fih informazzjoni aktar minn sempliċi lista.

14
00:00:40,540 --> 00:00:43,520
Nafu r-relazzjonijiet familjali bejn kulħadd

15
00:00:43,520 --> 00:00:45,440
biss billi teżamina l-siġra.

16
00:00:45,440 --> 00:00:47,250
Ukoll, jista 'tħaffef

17
00:00:47,250 --> 00:00:50,010
ħarsa-up time bil-kbir, jekk id-data tas-siġar huwa magħżul.

18
00:00:50,010 --> 00:00:53,850
>> Aħna ma jistgħux jieħdu vantaġġ ta 'dak hawn, imma aħna ser tara eżempju ta' dan dalwaqt.

19
00:00:53,850 --> 00:00:56,150
Kull persuna hija rrappreżentata minn nodu fuq is-siġra.

20
00:00:56,680 --> 00:00:58,370
Lymph nodes jista 'jkollhom tfal

21
00:00:58,370 --> 00:01:00,350
kif ukoll node ġenitur.

22
00:01:00,350 --> 00:01:02,390
Dawn huma t-termini tekniċi,

23
00:01:02,390 --> 00:01:05,220
anke meta jużaw siġar għall-affarijiet minbarra familji.

24
00:01:05,220 --> 00:01:07,940
Node Alice għandu 2 tfal u l-ebda ġenituri,

25
00:01:07,940 --> 00:01:11,500
filwaqt node Charlie ma għandha 3 itfal u 1 ġenitur.

26
00:01:11,500 --> 00:01:14,330
>> A node werqa huwa wieħed li ma jkollu ebda tfal

27
00:01:14,330 --> 00:01:16,410
fuq il-tarf ta 'barra tas-siġra.

28
00:01:16,410 --> 00:01:18,520
Il-node topmost tas-siġra, il-node għerq,

29
00:01:18,520 --> 00:01:20,240
m'għandha l-ebda ġenitur.

30
00:01:20,240 --> 00:01:23,170
>> A siġra binarju huwa tip speċifiku ta 'siġra,

31
00:01:23,170 --> 00:01:26,720
fejn kull node għandha, l-aktar, 2 tfal.

32
00:01:26,720 --> 00:01:30,490
Hawn hu l-Struct ta 'nodu ta' siġra binarju fil C.

33
00:01:31,560 --> 00:01:34,530
Kull node għandha xi data assoċjata magħha

34
00:01:34,530 --> 00:01:36,520
u 2 pointers għal punti strateġiċi oħra.

35
00:01:36,520 --> 00:01:38,110
>> Fil siġra tal-familja tagħna,

36
00:01:38,110 --> 00:01:40,900
id-dejta assoċjata kien l-isem ta 'kull persuna.

37
00:01:40,900 --> 00:01:43,850
Hawnhekk huwa int, għalkemm tista 'tkun xi ħaġa.

38
00:01:44,510 --> 00:01:46,200
Kif jirriżulta,

39
00:01:46,200 --> 00:01:48,990
siġra binarju ma tkunx rappreżentazzjoni tajba għal familja,

40
00:01:48,990 --> 00:01:51,960
billi n-nies spiss ikollhom aktar minn 2 tfal.

41
00:01:51,960 --> 00:01:53,510
>> A siġra tfittxija binarju

42
00:01:53,510 --> 00:01:56,380
huwa speċjali, tip ordnat ta 'siġra binarju

43
00:01:56,380 --> 00:01:58,090
li jippermetti li tħares lejn il-valuri malajr.

44
00:01:58,740 --> 00:02:00,050
Inti jista 'jkollok ndunat

45
00:02:00,050 --> 00:02:02,010
li kull node taħt l-għerq ta 'siġra

46
00:02:02,010 --> 00:02:04,620
huwa l-għerq ta 'xi siġar, imsejħa "subtree."

47
00:02:04,960 --> 00:02:07,090
Hawnhekk, l-għerq tal-siġra hija 6,

48
00:02:07,090 --> 00:02:09,860
u tat-tfal tagħha, 2, hija l-għerq ta 'subtree.

49
00:02:09,860 --> 00:02:11,870
>> Fil siġra tfittxija binarju

50
00:02:11,870 --> 00:02:15,790
il-valuri kollha ta 'node id-dritt subtree

51
00:02:15,790 --> 00:02:18,690
huma akbar mill-valur tal-node s. Hawn: 6.

52
00:02:18,690 --> 00:02:22,640
Ukoll, il-valuri fil subtree xellug node s

53
00:02:24,540 --> 00:02:26,890
huma inqas mill-valur tal-node s.

54
00:02:26,890 --> 00:02:28,620
Jekk għandna bżonn biex jimmaniġġaw valuri duplikati,

55
00:02:28,620 --> 00:02:31,760
nistgħu nbiddlu jew ta 'dawk għal inugwaljanza laxka,

56
00:02:31,760 --> 00:02:34,410
jfisser il-valuri identiċi jista 'jaqa' jew fuq il-lemin jew xellug,

57
00:02:34,410 --> 00:02:37,400
sakemm aħna konsistenti dwar dan kollu.

58
00:02:37,400 --> 00:02:39,620
Dan siġra hija siġra tfittxija binarju

59
00:02:39,620 --> 00:02:41,540
għaliex isegwi dawn ir-regoli.

60
00:02:42,320 --> 00:02:46,020
>> Dan huwa kif ser tfittex jekk aħna mdawwar l-lymph fis structs Ċ.

61
00:02:46,880 --> 00:02:48,410
Avviż li jekk xi tifel ikun nieqes,

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

63
00:02:50,340 --> 00:02:53,270
Kif nistgħu tikkontrolla biex tara jekk 7 huwa fil-siġra?

64
00:02:53,270 --> 00:02:55,020
Nibdew fil-għerq.

65
00:02:55,020 --> 00:02:58,690
Seba huwa akbar minn 6, hekk jekk huwa fil-siġra, għandu jkun fuq il-lemin.

66
00:02:59,680 --> 00:03:03,650
Imbagħad, huwa inqas minn 8, u għalhekk għandu jitħalla.

67
00:03:03,650 --> 00:03:06,210
Hawnhekk, sibna 7.

68
00:03:06,210 --> 00:03:08,160
Issa, aħna ser jiċċekkja għal 5.

69
00:03:08,160 --> 00:03:11,500
Ħames huwa inqas minn 6, u għalhekk għandu jkun lejn ix-xellug.

70
00:03:11,500 --> 00:03:13,460
Ħames huwa akbar minn 2,

71
00:03:13,460 --> 00:03:15,010
għalhekk għandu jkun id-dritt,

72
00:03:15,010 --> 00:03:18,100
u huwa wkoll akbar minn 4, u għalhekk għandu jkun tajjeb mill-ġdid.

73
00:03:18,100 --> 00:03:20,300
Madankollu, m'hemm l-ebda wild hawnhekk.

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

75
00:03:22,000 --> 00:03:24,270
Dan ifisser li 5 ma tkunx siġra tagħna.

76
00:03:24,270 --> 00:03:27,250
>> Nistgħu tfittxija-siġra binarju bil-kodiċi li ġej:

77
00:03:28,430 --> 00:03:31,140
F'kull node, aħna tikkontrolla biex tara jekk sibna

78
00:03:31,140 --> 00:03:33,020
il-valur li qed infittxu.

79
00:03:33,020 --> 00:03:35,740
Jekk aħna ma jsibuha, aħna jiddeterminaw jekk għandu jkun

80
00:03:35,740 --> 00:03:38,990
fuq il-lemin jew xellug u jiċċekkjaw li subtree.

81
00:03:38,990 --> 00:03:41,160
Dan loop se tkompli r-siġra

82
00:03:41,160 --> 00:03:44,190
sakemm ma jkunx hemm node wild jew fuq il-lemin jew xellug.

83
00:03:45,190 --> 00:03:48,600
>> Ftakar li 5 ma kienx fil-siġra.

84
00:03:48,600 --> 00:03:50,460
Kif nistgħu daħħal dan?

85
00:03:50,460 --> 00:03:52,370
Il-proċess jistenna simili għal tfittxija.

86
00:03:52,370 --> 00:03:54,830
Aħna ttenni l-siġra tibda minn 6,

87
00:03:54,830 --> 00:03:57,040
xellug għal 2,

88
00:03:57,040 --> 00:03:59,140
dritt għall-4,

89
00:03:59,140 --> 00:04:02,500
u d-dritt għal darb'oħra, iżda 4 m'għandha l-ebda tfal fuq din in-naħa.

90
00:04:02,500 --> 00:04:06,090
Dan se jkun l-pożizzjoni l-ġdida għal 5,

91
00:04:06,090 --> 00:04:08,500
u se tibda bl-ebda tfal.

92
00:04:09,020 --> 00:04:12,220
>> Kif fast huma operazzjonijiet fuq siġra tfittxija binarju?

93
00:04:12,220 --> 00:04:15,410
Ftakar li Bigohnotation tfittex li tipprovdi marbuta fuq.

94
00:04:15,410 --> 00:04:17,390
Fl-agħar każ,

95
00:04:17,390 --> 00:04:19,480
siġra tagħna tista 'sempliċement tkun lista marbuta

96
00:04:19,480 --> 00:04:22,220
li jfisser li inserzjoni, tħassir, u t-tiftix

97
00:04:22,220 --> 00:04:25,380
tista 'tieħu żmien proporzjonali għall-għadd ta' punti strateġiċi fil-siġra.

98
00:04:25,380 --> 00:04:27,380
Dan huwa O (n).

99
00:04:27,380 --> 00:04:30,690
>> Per eżempju, dan li ġej huwa siġra valida tfittxija binarja.

100
00:04:31,850 --> 00:04:34,020
Madankollu, jekk aħna tipprova ssib 9,

101
00:04:34,020 --> 00:04:36,760
irridu travers kull node.

102
00:04:36,760 --> 00:04:39,120
Huwa l-ebda aħjar minn lista marbuta.

103
00:04:39,120 --> 00:04:41,410
Idealment, aħna rridu kull node

104
00:04:41,410 --> 00:04:44,120
ta 'siġar tagħna tfittxija binarja li jkollha 2 tfal.

105
00:04:44,120 --> 00:04:46,370
Dan il-mod, inserzjoni, tħassir u tiftix

106
00:04:46,370 --> 00:04:50,190
se tieħu, fl-agħar, O (log n) iż-żmien.

107
00:04:50,190 --> 00:04:52,470
Is-siġra minn qabel tista 'tkun aktar ibbilanċjata,

108
00:04:52,470 --> 00:04:54,140
bħal dan.

109
00:04:54,140 --> 00:04:57,980
Issa, tfittex up xi valur tieħu, l-aktar, 3 passi.

110
00:04:57,980 --> 00:04:59,460
Dan siġra hija bilanċjata,

111
00:04:59,460 --> 00:05:01,190
fis-sens li huwa għandu fond minimu

112
00:05:01,190 --> 00:05:03,680
relattiva għan-numru ta 'nodes.

113
00:05:03,680 --> 00:05:06,300
>> Looking for valur fil-siġra bilanċjat tfittxija binarju

114
00:05:06,300 --> 00:05:09,540
huwa simili għal tfittxija binarju fuq firxa magħżula.

115
00:05:09,540 --> 00:05:12,290
Fil-fatt, jekk aħna ma bżonn li tiddaħħal jew tħassar oġġetti,

116
00:05:12,290 --> 00:05:15,150
għandhom iġibu ruħhom eżattament bl-istess mod.

117
00:05:15,150 --> 00:05:17,600
Madankollu, struttura ta 'siġra hija aħjar

118
00:05:17,600 --> 00:05:19,530
għall inserzjonijiet tqandil u tħassir

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

120
00:05:22,670 --> 00:05:24,030
Dan huwa CS50.