1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Paano mo ire-kumatawan sa lahat ng iyong mga miyembro ng pamilya sa isang computer?

2
00:00:10,790 --> 00:00:12,390
Kami maaaring gamitin lamang ng isang listahan,

3
00:00:12,390 --> 00:00:14,400
ngunit may isang malinaw na hierarchy dito.

4
00:00:14,400 --> 00:00:17,110
>> Ipagpalagay natin na kami ay nagsisimula sa iyong lola sa tuhod, Alice.

5
00:00:17,110 --> 00:00:19,030
Siya ay may 2 anak, Bob

6
00:00:19,030 --> 00:00:21,310
at ang iyong lolo, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie ay may 3 bata,

8
00:00:23,190 --> 00:00:26,730
iyong tiyuhin, Dave, iyong tiyahin, Eba, at ang iyong ama, Fred.

9
00:00:26,730 --> 00:00:28,750
Ikaw lamang Fred bata.

10
00:00:28,750 --> 00:00:30,950
>> Bakit-aayos ng iyong mga miyembro ng pamilya sa ganitong paraan

11
00:00:30,950 --> 00:00:34,010
maging mas mahusay kaysa sa simpleng representasyon ng listahan?

12
00:00:34,010 --> 00:00:36,630
Isang kadahilanan ay na ito hierarchical istraktura,

13
00:00:36,630 --> 00:00:39,660
tinatawag na 'puno,' ay naglalaman ng karagdagang impormasyon kaysa sa isang simpleng listahan.

14
00:00:40,540 --> 00:00:43,520
Alam namin ang familial relasyon sa pagitan ng lahat

15
00:00:43,520 --> 00:00:45,440
lamang sa pamamagitan ng pagsusuri sa puno.

16
00:00:45,440 --> 00:00:47,250
Gayundin, maaari itong mapabilis ang

17
00:00:47,250 --> 00:00:50,010
hitsura-up na oras tremendously, kung puno data ay pinagsunod-sunod.

18
00:00:50,010 --> 00:00:53,850
>> Hindi namin maaaring samantalahin na dito, ngunit gagamitin namin makita ang isang halimbawa ng mga ito sa lalong madaling panahon.

19
00:00:53,850 --> 00:00:56,150
Ang bawat tao ay kinakatawan ng isang node sa tree.

20
00:00:56,680 --> 00:00:58,370
Node node anak

21
00:00:58,370 --> 00:01:00,350
pati na rin bilang isang magulang na node.

22
00:01:00,350 --> 00:01:02,390
Ito ang mga teknikal na mga tuntunin,

23
00:01:02,390 --> 00:01:05,220
kahit na kapag gumagamit ng puno para sa mga bagay bukod sa mga pamilya.

24
00:01:05,220 --> 00:01:07,940
Alice ng node ay may 2 bata at walang mga magulang,

25
00:01:07,940 --> 00:01:11,500
habang ang Charlie ng node ay may 3 bata at 1 magulang.

26
00:01:11,500 --> 00:01:14,330
>> Isang dahon node ay isa na ay hindi magkakaroon ng anumang mga bata

27
00:01:14,330 --> 00:01:16,410
sa labas gilid ng puno.

28
00:01:16,410 --> 00:01:18,520
Ang pinakamataas na node ng puno, ang root node,

29
00:01:18,520 --> 00:01:20,240
ay walang magulang.

30
00:01:20,240 --> 00:01:23,170
>> Isang puno ng binary ay isang partikular na uri ng puno,

31
00:01:23,170 --> 00:01:26,720
na node ang bawat isa ay, sa pinakamarami, 2 bata.

32
00:01:26,720 --> 00:01:30,490
Narito ang struct ng isang node ng isang binary puno sa C.

33
00:01:31,560 --> 00:01:34,530
Node bawat ay may ilang mga data na nauugnay dito

34
00:01:34,530 --> 00:01:36,520
at 2 pointer sa iba pang mga node.

35
00:01:36,520 --> 00:01:38,110
>> Sa aming pamilya puno,

36
00:01:38,110 --> 00:01:40,900
ang mga kaugnay na data ay ang pangalan ng bawat tao.

37
00:01:40,900 --> 00:01:43,850
Narito ito ay isang int, bagaman maaari itong maging anumang.

38
00:01:44,510 --> 00:01:46,200
Bilang ito ay lumiliko out,

39
00:01:46,200 --> 00:01:48,990
isang binary tree ay hindi magiging isang mahusay na representasyon para sa isang pamilya,

40
00:01:48,990 --> 00:01:51,960
dahil ang mga tao ay madalas na may higit sa 2 bata.

41
00:01:51,960 --> 00:01:53,510
>> Ang isang binary puno ng paghahanap

42
00:01:53,510 --> 00:01:56,380
ay isang espesyal na, na nakaayos uri ng binary puno

43
00:01:56,380 --> 00:01:58,090
na nagbibigay-daan sa amin upang tingnan ang halaga nang mabilis.

44
00:01:58,740 --> 00:02:00,050
Maaaring napansin mo

45
00:02:00,050 --> 00:02:02,010
ang bawat node sa ibaba ang ugat ng isang puno

46
00:02:02,010 --> 00:02:04,620
ay ang root ng ibang puno, na tinatawag na 'subtree.'

47
00:02:04,960 --> 00:02:07,090
Narito, ang mga ugat ng puno ay 6,

48
00:02:07,090 --> 00:02:09,860
at sa bata, 2, ay ang root ng isang subtree.

49
00:02:09,860 --> 00:02:11,870
>> Sa isang binary puno ng paghahanap

50
00:02:11,870 --> 00:02:15,790
ang lahat ng mga halaga ng isang node karapatan subtree

51
00:02:15,790 --> 00:02:18,690
ay mas mataas kaysa sa halaga ang node. Dito: 6.

52
00:02:18,690 --> 00:02:22,640
Well, ang mga halaga sa kaliwa subtree isang node

53
00:02:24,540 --> 00:02:26,890
ay mas mababa kaysa sa halaga ang node.

54
00:02:26,890 --> 00:02:28,620
Kung kailangan namin ang mga duplicate na halaga,

55
00:02:28,620 --> 00:02:31,760
Maaari naming baguhin ang alinman sa mga ng maluwag na hindi pagkakapareho,

56
00:02:31,760 --> 00:02:34,410
ibig sabihin magkakahawig na mga halaga ay maaaring mahulog sa alinman sa kaliwa o kanan,

57
00:02:34,410 --> 00:02:37,400
hangga't namin pare-pareho ang tungkol dito sa buong.

58
00:02:37,400 --> 00:02:39,620
Punong kahoy na ito ay isang binary puno ng paghahanap

59
00:02:39,620 --> 00:02:41,540
dahil ito ay sumusunod sa mga panuntunang ito.

60
00:02:42,320 --> 00:02:46,020
>> Ito ay kung paano hitsura nito ay magiging kung naka-namin ang lahat ng mga node sa C structs.

61
00:02:46,880 --> 00:02:48,410
Pansinin na kung ang isang bata ay nawawala,

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

63
00:02:50,340 --> 00:02:53,270
Paano namin suriin upang makita kung 7 sa tree?

64
00:02:53,270 --> 00:02:55,020
Simulan namin sa root.

65
00:02:55,020 --> 00:02:58,690
Pitong mas malaki kaysa sa 6, kaya kung ito ay sa tree, dapat itong maging sa kanan.

66
00:02:59,680 --> 00:03:03,650
Pagkatapos, mas mababa sa 8, kaya dapat itong iwanang.

67
00:03:03,650 --> 00:03:06,210
Dito, aming natagpuan 7.

68
00:03:06,210 --> 00:03:08,160
Ngayon, susuriin namin para sa 5.

69
00:03:08,160 --> 00:03:11,500
Limang ay mas mababa sa 6, kaya dapat itong maging sa kaliwa.

70
00:03:11,500 --> 00:03:13,460
Limang mas malaki kaysa sa 2,

71
00:03:13,460 --> 00:03:15,010
kaya dapat itong karapatan,

72
00:03:15,010 --> 00:03:18,100
at ito ay din mas malaki sa 4, kaya dapat itong kanan muli.

73
00:03:18,100 --> 00:03:20,300
Subalit, may bata hindi dito.

74
00:03:20,300 --> 00:03:22,000
Pointer ay null.

75
00:03:22,000 --> 00:03:24,270
Nangangahulugan ito na 5 ay wala sa aming puno.

76
00:03:24,270 --> 00:03:27,250
>> Maaari naming maghanap sa binary puno na may mga sumusunod na code:

77
00:03:28,430 --> 00:03:31,140
Sa bawat node, suriin namin upang makita kung namin nahanap

78
00:03:31,140 --> 00:03:33,020
ang halaga na aming hinahanap.

79
00:03:33,020 --> 00:03:35,740
Kung hindi namin mahanap ito, namin matukoy kung ito ay kailangang maging

80
00:03:35,740 --> 00:03:38,990
sa kaliwa o kanan at suriin na subtree.

81
00:03:38,990 --> 00:03:41,160
Loop na ito ay patuloy ang tree

82
00:03:41,160 --> 00:03:44,190
hanggang doon ay walang anak node sa alinman sa kaliwa o kanan.

83
00:03:45,190 --> 00:03:48,600
>> Tandaan na ang 5 ay hindi sa tree.

84
00:03:48,600 --> 00:03:50,460
Paano namin ipasok ito?

85
00:03:50,460 --> 00:03:52,370
Ang proseso ay mukhang katulad upang maghanap.

86
00:03:52,370 --> 00:03:54,830
Namin umulit tree na nagsisimula mula 6,

87
00:03:54,830 --> 00:03:57,040
kaliwa sa 2,

88
00:03:57,040 --> 00:03:59,140
karapatan sa 4,

89
00:03:59,140 --> 00:04:02,500
at sa muli, ngunit 4 ay hindi anak sa bandang ito.

90
00:04:02,500 --> 00:04:06,090
Ito ang magiging bagong posisyon para sa 5,

91
00:04:06,090 --> 00:04:08,500
at ito ay magsimula sa walang mga bata.

92
00:04:09,020 --> 00:04:12,220
>> Kung gaano kabilis ang pagpapatakbo sa isang binary puno ng paghahanap?

93
00:04:12,220 --> 00:04:15,410
Tandaan na Bigohnotation naglalayong magbigay ng isang pang-itaas bound.

94
00:04:15,410 --> 00:04:17,390
Sa pinakamasama kaso,

95
00:04:17,390 --> 00:04:19,480
aming puno ay maaaring lamang ay isang naka-link na listahan

96
00:04:19,480 --> 00:04:22,220
na nangangahulugan na ang pagpapasok ng, pagtanggal, at paghahanap

97
00:04:22,220 --> 00:04:25,380
Maaaring tumagal ng oras na proporsyonal sa ang bilang ng mga node sa tree.

98
00:04:25,380 --> 00:04:27,380
Ito ay O (n).

99
00:04:27,380 --> 00:04:30,690
>> Halimbawa, ang mga sumusunod ay isang may-bisang puno ng binary paghahanap.

100
00:04:31,850 --> 00:04:34,020
Gayunpaman, kung sinusubukan naming upang mahanap 9,

101
00:04:34,020 --> 00:04:36,760
mayroon kami sa pagbagtas bawat node.

102
00:04:36,760 --> 00:04:39,120
Ito ay walang mas mahusay kaysa sa isang naka-link na listahan.

103
00:04:39,120 --> 00:04:41,410
May perpektong, namin gusto ang bawat node

104
00:04:41,410 --> 00:04:44,120
ng aming puno ng paghahanap ng binary sa 2 bata.

105
00:04:44,120 --> 00:04:46,370
Ganitong paraan, ang pagpapasok ng, pagtanggal at paghahanap

106
00:04:46,370 --> 00:04:50,190
ay tumagal, sa pinakamalala, O (log n) oras.

107
00:04:50,190 --> 00:04:52,470
Ang puno mula sa bago maaaring maging mas balanced,

108
00:04:52,470 --> 00:04:54,140
tulad nito.

109
00:04:54,140 --> 00:04:57,980
Ngayon, hinahanap anumang halaga tumatagal, hindi hihigit sa, 3 hakbang.

110
00:04:57,980 --> 00:04:59,460
Puno na ito ay balanced,

111
00:04:59,460 --> 00:05:01,190
kahulugan na may minimal na lalim

112
00:05:01,190 --> 00:05:03,680
kaugnay sa bilang ng mga node.

113
00:05:03,680 --> 00:05:06,300
>> Naghahanap para sa isang halaga sa isang balanseng puno ng binary paghahanap

114
00:05:06,300 --> 00:05:09,540
ay katulad sa binary paghahanap sa isang pinagsunod-sunod array.

115
00:05:09,540 --> 00:05:12,290
Sa katunayan, kung hindi namin kailangan upang ipasok o tanggalin ang mga item,

116
00:05:12,290 --> 00:05:15,150
kumikilos sila eksaktong parehong paraan.

117
00:05:15,150 --> 00:05:17,600
Gayunman, ang isang mala-punong balangkas ay mas mahusay

118
00:05:17,600 --> 00:05:19,530
para sa handling pagpapasok at pagtanggal

119
00:05:20,360 --> 00:05:22,670
>> Ang pangalan ko ay ng Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Ito ay CS50.