1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Hoe zou u vertegenwoordigt al uw gezinsleden in een computer?

2
00:00:10,790 --> 00:00:12,390
We kunnen gewoon gebruik maken van een lijst,

3
00:00:12,390 --> 00:00:14,400
maar er is een duidelijke hiërarchie hier.

4
00:00:14,400 --> 00:00:17,110
>> Laten we zeggen dat we beginnen met je overgrootmoeder, Alice.

5
00:00:17,110 --> 00:00:19,030
Ze heeft 2 zonen, Bob

6
00:00:19,030 --> 00:00:21,310
en je grootvader, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie heeft 3 kinderen,

8
00:00:23,190 --> 00:00:26,730
je oom, Dave, je tante, Eva, en je vader, Fred.

9
00:00:26,730 --> 00:00:28,750
U bent enig kind Fred's.

10
00:00:28,750 --> 00:00:30,950
>> Waarom zou het organiseren van uw familieleden op deze manier

11
00:00:30,950 --> 00:00:34,010
beter zijn dan de eenvoudige lijst voorstelling?

12
00:00:34,010 --> 00:00:36,630
Een reden is dat deze hiërarchische structuur,

13
00:00:36,630 --> 00:00:39,660
heet een 'boom', bevat meer informatie dan een eenvoudige lijst.

14
00:00:40,540 --> 00:00:43,520
We kennen de familiale relaties tussen iedereen

15
00:00:43,520 --> 00:00:45,440
alleen door onderzoek van de boom.

16
00:00:45,440 --> 00:00:47,250
Ook kan het versnellen

17
00:00:47,250 --> 00:00:50,010
look-up tijd enorm, als boom gegevens worden gesorteerd.

18
00:00:50,010 --> 00:00:53,850
>> We kunnen niet profiteren van dat hier, maar we zullen hier een voorbeeld van snel te zien.

19
00:00:53,850 --> 00:00:56,150
Elke persoon wordt vertegenwoordigd door een knooppunt op de boom.

20
00:00:56,680 --> 00:00:58,370
Knooppunten kunnen child nodes

21
00:00:58,370 --> 00:01:00,350
en een bovenliggende knooppunt.

22
00:01:00,350 --> 00:01:02,390
Dit zijn de technische termen,

23
00:01:02,390 --> 00:01:05,220
zelfs bij gebruik van bomen voor dingen naast gezinnen.

24
00:01:05,220 --> 00:01:07,940
Alice's knooppunt heeft 2 kinderen en geen ouders,

25
00:01:07,940 --> 00:01:11,500
terwijl Charlie's knooppunt heeft 3 kinderen en 1 ouder.

26
00:01:11,500 --> 00:01:14,330
>> Een blad knooppunt is er een die niet hoeft geen kinderen

27
00:01:14,330 --> 00:01:16,410
aan de buitenkant van de boom.

28
00:01:16,410 --> 00:01:18,520
De bovenste knoop van de boom, de root node,

29
00:01:18,520 --> 00:01:20,240
heeft geen ouder.

30
00:01:20,240 --> 00:01:23,170
>> Een binaire boom is een specifiek type boom

31
00:01:23,170 --> 00:01:26,720
waarbij elke knoop hooguit 2 kinderen.

32
00:01:26,720 --> 00:01:30,490
Hier is de struct een knooppunt van een binaire boom in C.

33
00:01:31,560 --> 00:01:34,530
Elk knooppunt heeft een aantal gegevens in verband met het

34
00:01:34,530 --> 00:01:36,520
en 2 pointers naar andere knooppunten.

35
00:01:36,520 --> 00:01:38,110
>> In onze stamboom,

36
00:01:38,110 --> 00:01:40,900
de bijbehorende gegevens was ieders naam.

37
00:01:40,900 --> 00:01:43,850
Hier is het een int, maar het kan van alles zijn.

38
00:01:44,510 --> 00:01:46,200
Het blijkt dat,

39
00:01:46,200 --> 00:01:48,990
een binaire boom zou niet een goede weergave voor een gezin,

40
00:01:48,990 --> 00:01:51,960
omdat mensen hebben vaak meer dan 2 kinderen.

41
00:01:51,960 --> 00:01:53,510
>> Een binaire zoekboom

42
00:01:53,510 --> 00:01:56,380
is een speciaal, geordende type binaire boom

43
00:01:56,380 --> 00:01:58,090
die ons in staat stelt om snel te kijken naar waarden.

44
00:01:58,740 --> 00:02:00,050
Je hebt misschien gemerkt

45
00:02:00,050 --> 00:02:02,010
dat elke knoop onder de wortel van een boom

46
00:02:02,010 --> 00:02:04,620
is de wortel van een andere boom, een zogenaamde 'substructuur.'

47
00:02:04,960 --> 00:02:07,090
Hier, de wortel van de boom is 6,

48
00:02:07,090 --> 00:02:09,860
en haar kind, 2, is de wortel van een tak.

49
00:02:09,860 --> 00:02:11,870
>> In een binaire zoekboom

50
00:02:11,870 --> 00:02:15,790
alle waarden van een knooppunt is rechter deelboom

51
00:02:15,790 --> 00:02:18,690
groter zijn dan de waarde van het knooppunt. Hier: 6.

52
00:02:18,690 --> 00:02:22,640
Nou, de waarden in de linker een knooppunt substructuur

53
00:02:24,540 --> 00:02:26,890
zijn minder dan de waarde van het knooppunt.

54
00:02:26,890 --> 00:02:28,620
Als we moeten dubbele waarden te behandelen,

55
00:02:28,620 --> 00:02:31,760
we een van deze veranderen in een losse ongelijkheid

56
00:02:31,760 --> 00:02:34,410
wat betekent dat identieke waarden kan vallen op de links of rechts,

57
00:02:34,410 --> 00:02:37,400
zolang we consequent in het hele gebouw.

58
00:02:37,400 --> 00:02:39,620
Deze boom is een binaire zoekboom

59
00:02:39,620 --> 00:02:41,540
omdat het volgt deze regels.

60
00:02:42,320 --> 00:02:46,020
>> Dit is hoe het eruit zou zien als we allemaal de knooppunten veranderd in C structs.

61
00:02:46,880 --> 00:02:48,410
Merk op dat als een kind wordt vermist,

62
00:02:48,410 --> 00:02:50,340
de aanwijzer is null.

63
00:02:50,340 --> 00:02:53,270
Hoe kunnen we controleren of 7 is in de boom?

64
00:02:53,270 --> 00:02:55,020
We beginnen bij de wortel.

65
00:02:55,020 --> 00:02:58,690
Zeven is groter dan 6, dus als het in de boom, moet het naar rechts.

66
00:02:59,680 --> 00:03:03,650
Dan is minder dan 8, dus het moet worden gelaten.

67
00:03:03,650 --> 00:03:06,210
Hier hebben wij gevonden 7.

68
00:03:06,210 --> 00:03:08,160
Nu gaan we controleren 5.

69
00:03:08,160 --> 00:03:11,500
Vijf is minder dan 6, dus het moet aan de linkerkant.

70
00:03:11,500 --> 00:03:13,460
Vijf groter is dan 2,

71
00:03:13,460 --> 00:03:15,010
dus het moet goed zijn,

72
00:03:15,010 --> 00:03:18,100
en is ook groter dan 4, dus moet rechts.

73
00:03:18,100 --> 00:03:20,300
Er is echter geen kind hier.

74
00:03:20,300 --> 00:03:22,000
De aanwijzer is null.

75
00:03:22,000 --> 00:03:24,270
Dit betekent dat 5 niet in de boom.

76
00:03:24,270 --> 00:03:27,250
>> We kunnen zoeken in de binaire boom met de volgende code:

77
00:03:28,430 --> 00:03:31,140
Bij elke knoop, kijken we of we hebben gevonden

78
00:03:31,140 --> 00:03:33,020
de waarde die we zoeken.

79
00:03:33,020 --> 00:03:35,740
Als we het niet vinden, wij bepalen of het zou moeten zijn

80
00:03:35,740 --> 00:03:38,990
aan de linker-of rechts en controleer of substructuur.

81
00:03:38,990 --> 00:03:41,160
Deze lus blijft de boom

82
00:03:41,160 --> 00:03:44,190
totdat er geen kindknoop zowel links of rechts.

83
00:03:45,190 --> 00:03:48,600
>> Vergeet niet dat 5 niet in de boom.

84
00:03:48,600 --> 00:03:50,460
Hoe kunnen we voegen het?

85
00:03:50,460 --> 00:03:52,370
Het proces lijkt op te zoeken.

86
00:03:52,370 --> 00:03:54,830
We herhalen de boom vanaf 6,

87
00:03:54,830 --> 00:03:57,040
overgelaten aan 2,

88
00:03:57,040 --> 00:03:59,140
recht op 4,

89
00:03:59,140 --> 00:04:02,500
en weer rechts, maar 4 heeft geen kind aan deze kant.

90
00:04:02,500 --> 00:04:06,090
Dit wordt de nieuwe positie 5 is,

91
00:04:06,090 --> 00:04:08,500
en het zal beginnen zonder kinderen.

92
00:04:09,020 --> 00:04:12,220
>> Hoe snel zijn activiteiten op een binaire zoekboom?

93
00:04:12,220 --> 00:04:15,410
Anders Bigohnotation beoogt een bovengrens.

94
00:04:15,410 --> 00:04:17,390
In het ergste geval,

95
00:04:17,390 --> 00:04:19,480
onze boom kan gewoon een gelinkte lijst

96
00:04:19,480 --> 00:04:22,220
waardoor insertie, deletie en zoeken

97
00:04:22,220 --> 00:04:25,380
zou kunnen tijd evenredig met het aantal knopen in de boom.

98
00:04:25,380 --> 00:04:27,380
Dit is O (n).

99
00:04:27,380 --> 00:04:30,690
>> Bijvoorbeeld, de volgende is geldig binaire zoekboom.

100
00:04:31,850 --> 00:04:34,020
Echter, als we proberen tot 9 te vinden,

101
00:04:34,020 --> 00:04:36,760
we iedere knooppunt doorkruisen.

102
00:04:36,760 --> 00:04:39,120
Het is niet beter dan een gelinkte lijst.

103
00:04:39,120 --> 00:04:41,410
Idealiter zouden we willen dat elke knoop

104
00:04:41,410 --> 00:04:44,120
van onze binaire zoekboom tot en met 2 kinderen te krijgen.

105
00:04:44,120 --> 00:04:46,370
Zo insertie, deletie en search

106
00:04:46,370 --> 00:04:50,190
zou, in het slechtste geval, O (log n) tijd.

107
00:04:50,190 --> 00:04:52,470
De boom van voor zou kunnen zijn evenwichtiger,

108
00:04:52,470 --> 00:04:54,140
als dit.

109
00:04:54,140 --> 00:04:57,980
Nu kijken elke waarde neemt hooguit 3 stappen.

110
00:04:57,980 --> 00:04:59,460
Deze boom is evenwichtig,

111
00:04:59,460 --> 00:05:01,190
betekenis die een minimale diepte

112
00:05:01,190 --> 00:05:03,680
opzichte van het aantal knooppunten.

113
00:05:03,680 --> 00:05:06,300
>> Op zoek naar een waarde in een gebalanceerde binaire zoekboom

114
00:05:06,300 --> 00:05:09,540
is vergelijkbaar met binair zoeken op een gesorteerde array.

115
00:05:09,540 --> 00:05:12,290
In feite, als we niet nodig om in te voegen of te verwijderen items,

116
00:05:12,290 --> 00:05:15,150
gedragen ze zich precies hetzelfde.

117
00:05:15,150 --> 00:05:17,600
Echter een boomstructuur beter

118
00:05:17,600 --> 00:05:19,530
voor de behandeling inserties en deleties

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

120
00:05:22,670 --> 00:05:24,030
Dit is CS50.