1
00:00:00,000 --> 00:00:02,994
>> [Παίζει μουσική]

2
00:00:02,994 --> 00:00:05,426

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Έτσι έχουμε εγγύτερα
και στενότερη ότι Άγιο Δισκοπότηρο των δεδομένων

4
00:00:08,550 --> 00:00:13,050
δομές, αυτό που μπορούμε να εισάγουμε
σε, να διαγράψετε από, και κοιτάζω προς τα πάνω

5
00:00:13,050 --> 00:00:15,440
σε σταθερό χρόνο.

6
00:00:15,440 --> 00:00:16,270
Δεξιά.

7
00:00:16,270 --> 00:00:17,280
Αυτό είναι το είδος του στόχου.

8
00:00:17,280 --> 00:00:19,720
Θέλουμε να είμαστε σε θέση να κάνουμε
τα πράγματα είναι πολύ, πολύ γρήγορα.

9
00:00:19,720 --> 00:00:22,580
>> Έχετε το βρήκαμε εδώ όταν
μιλάμε για προσπάθειες;

10
00:00:22,580 --> 00:00:23,670
Λοιπόν, ας ρίξουμε μια ματιά.

11
00:00:23,670 --> 00:00:25,628
Έτσι έχουμε δει αρκετές
διαφορετικές δομές δεδομένων

12
00:00:25,628 --> 00:00:28,680
που χειρίζονται την χαρτογράφηση των
λεγόμενη ζεύγη κλειδιού-τιμής,

13
00:00:28,680 --> 00:00:32,080
χαρτογράφηση κάποιο κομμάτι των δεδομένων
σε κάποιο άλλο κομμάτι δεδομένων

14
00:00:32,080 --> 00:00:36,020
έτσι ώστε να γνωρίζουν πού να βρείτε
πληροφορίες στη δομή.

15
00:00:36,020 --> 00:00:40,060
>> Έτσι, για συστοιχία, για παράδειγμα, το
κλειδί είναι ο δείκτης στοιχείο ή συστοιχία

16
00:00:40,060 --> 00:00:42,600
τοποθεσία 0 ή συστοιχία 1 και ούτω καθεξής.

17
00:00:42,600 --> 00:00:46,140
Και η τιμή είναι τα δεδομένα
ότι υπάρχει σε αυτή τη θέση.

18
00:00:46,140 --> 00:00:48,550
Έτσι, αυτό που είναι αποθηκευμένα στη σειρά 0;

19
00:00:48,550 --> 00:00:54,290
Τι είναι αποθηκευμένα σε σειρά έναντι μόλις 1
0 και 1, τα οποία θα είναι τα κλειδιά.

20
00:00:54,290 --> 00:00:56,360
>> Με ένα πίνακα κατακερματισμού είναι
το είδος της ίδιας ιδέας.

21
00:00:56,360 --> 00:01:00,690
Με ένα πίνακα κατακερματισμού, έχουμε αυτό το κλειδί
λειτουργία που δημιουργεί κωδικούς hash.

22
00:01:00,690 --> 00:01:03,670
Έτσι, το κλειδί είναι ο κώδικας hash των δεδομένων.

23
00:01:03,670 --> 00:01:06,530
Και η τιμή, ιδίως
μιλήσαμε για την αλυσιδωτή σύνδεση

24
00:01:06,530 --> 00:01:10,590
στο βίντεο για πίνακες κατακερματισμού,
είναι εκείνος που συνδέεται κατάλογο των δεδομένων

25
00:01:10,590 --> 00:01:12,550
ότι απεικονίζεται σε αυτή την hashCode.

26
00:01:12,550 --> 00:01:14,050
Δεξιά.

27
00:01:14,050 --> 00:01:16,050
Τι γίνεται με μια άλλη προσέγγιση
Αυτή η μέθοδος, όμως;

28
00:01:16,050 --> 00:01:21,000
Τι γίνεται με μια μέθοδο, η οποία
το κλειδί είναι εγγυημένη για να είναι μοναδική,

29
00:01:21,000 --> 00:01:25,410
σε αντίθεση με ένα πίνακα κατακερματισμού, όπου θα μπορούσαμε να
καταλήγουν με δύο κομμάτια των στοιχείων

30
00:01:25,410 --> 00:01:27,200
που έχουν την ίδια hashCode.

31
00:01:27,200 --> 00:01:30,020
Και τότε έχουμε να κάνουμε με
ότι είτε διερεύνηση ή περισσότερα

32
00:01:30,020 --> 00:01:33,340
κατά προτίμηση αλυσιδωτή σύνδεση για να διορθώσετε αυτό το πρόβλημα.

33
00:01:33,340 --> 00:01:37,520
>> Έτσι τώρα μπορούμε να εγγυηθούμε
ότι οι βασικές μας θα είναι μοναδική.

34
00:01:37,520 --> 00:01:39,690
Και τι θα γινόταν αν ήταν τιμή μας
ακριβώς κάτι τόσο εύκολο

35
00:01:39,690 --> 00:01:44,080
ως αληθινό και το ψεύτικο που μας λέει αν
ή όχι αυτό το κομμάτι των πληροφοριών

36
00:01:44,080 --> 00:01:45,610
υπάρχει στην δομή;

37
00:01:45,610 --> 00:01:48,180
Μια Boolean θα μπορούσε να είναι τόσο απλό όσο ένα κομμάτι.

38
00:01:48,180 --> 00:01:52,660
Ρεαλιστικά είναι πιθανώς μια
byte πιο πιθανό από ό, τι ένα κομμάτι.

39
00:01:52,660 --> 00:01:55,410
Αλλά αυτό είναι πολύ μικρότερο από ό, τι
αποθήκευση ίσως μια σειρά 50 χαρακτήρων,

40
00:01:55,410 --> 00:01:57,360
για παράδειγμα.

41
00:01:57,360 --> 00:02:02,210
>> Έτσι προσπαθεί, παρόμοια με hash πίνακες,
που συνδυάζουν συστοιχίες και συνδεδεμένη λίστα,

42
00:02:02,210 --> 00:02:05,790
προσπαθεί συνδυάζουν συστοιχίες,
δομές, και δείκτες

43
00:02:05,790 --> 00:02:08,509
μαζί με την αποθήκευση δεδομένων σε
ένας ενδιαφέρων τρόπος που είναι

44
00:02:08,509 --> 00:02:11,550
αρκετά διαφορετική από
οτιδήποτε έχουμε δει μέχρι τώρα.

45
00:02:11,550 --> 00:02:16,750
Τώρα χρησιμοποιούμε τα δεδομένα ως οδικός χάρτης
για να πλοηγηθείτε σε αυτήν τη δομή των δεδομένων.

46
00:02:16,750 --> 00:02:18,710
Και αν μπορούμε να ακολουθήσουμε
Ο οδικός χάρτης, αν μπορούμε

47
00:02:18,710 --> 00:02:22,390
ακολουθήστε τα δεδομένα από
αρχή μέχρι το τέλος, θα

48
00:02:22,390 --> 00:02:24,945
ξέρω αν αυτά τα δεδομένα
υπάρχουν στο Trie.

49
00:02:24,945 --> 00:02:28,310
>> Και αν δεν μπορεί να ακολουθήσει το χάρτη
από νόημα να καταλήξει σε όλα,

50
00:02:28,310 --> 00:02:30,600
δεν μπορεί να υπάρξει τα στοιχεία.

51
00:02:30,600 --> 00:02:32,890
Πάλι, τα πλήκτρα είναι εδώ
εγγυημένη για να είναι μοναδική.

52
00:02:32,890 --> 00:02:36,020
Και έτσι σε αντίθεση με ένα πίνακα κατακερματισμού, εμείς δεν πρόκειται ποτέ
πρέπει να ασχοληθεί με συγκρούσεις εδώ.

53
00:02:36,020 --> 00:02:39,090
Και δεν υπάρχουν δύο κομμάτια των δεδομένων
έχουν ακριβώς το ίδιο οδικό χάρτη

54
00:02:39,090 --> 00:02:40,530
εκτός ότι τα δεδομένα είναι πανομοιότυπα.

55
00:02:40,530 --> 00:02:44,580
>> Αν εισάγετε τον Ιωάννη, στη συνέχεια,
ψάχνουμε για τον John.

56
00:02:44,580 --> 00:02:47,430
Αυτό είναι δύο πανομοιότυπα κομμάτια
δεδομένων, δεξιά, ψάχνουμε μέσα.

57
00:02:47,430 --> 00:02:49,880
Αλλά κατά τα άλλα, οποιαδήποτε
δύο κομμάτια των δεδομένων είναι

58
00:02:49,880 --> 00:02:52,750
εγγυημένη για να έχουν μοναδικές χάρτες πορείας
μέσω αυτής της δομής δεδομένων.

59
00:02:52,750 --> 00:02:56,210
Και θα πάμε να ρίξουμε μια ματιά στο
μια οπτική του αυτό ακριβώς σε μια στιγμή.

60
00:02:56,210 --> 00:02:58,810
>> Θα το κάνουμε αυτό με την προσπάθεια να
δημιουργηθεί μια νέα δομή δεδομένων,

61
00:02:58,810 --> 00:03:00,564
χαρτογράφηση τα ακόλουθα βασικά ζεύγη τιμών.

62
00:03:00,564 --> 00:03:03,480
Σε αυτή την περίπτωση, εμείς δεν πρόκειται να χρησιμοποιήσετε
κάτι τόσο απλό όσο ένα Boolean.

63
00:03:03,480 --> 00:03:06,200
Είμαστε πραγματικά θα αποθηκεύσει το string.

64
00:03:06,200 --> 00:03:08,690
Και αυτή η συμβολοσειρά θα
να είναι το όνομα του πανεπιστημίου.

65
00:03:08,690 --> 00:03:12,140
>> Και το κλειδί θα είναι η χρονιά
όταν το εν λόγω πανεπιστήμιο ιδρύθηκε.

66
00:03:12,140 --> 00:03:15,380
Όλα τα έτη για τα πανεπιστήμια
πρόκειται να είναι τετραψήφιος.

67
00:03:15,380 --> 00:03:19,840
Και έτσι θα χρησιμοποιήσουμε αυτά τα τέσσερα ψηφία
πλοηγηθείτε σε αυτήν την δομή των δεδομένων.

68
00:03:19,840 --> 00:03:22,270
Και θα δούμε, και πάλι, πώς
το κάνουμε αυτό σε μόλις ένα δευτερόλεπτο.

69
00:03:22,270 --> 00:03:25,110
>> Στο τέλος της διαδρομής,
θα δούμε το όνομα

70
00:03:25,110 --> 00:03:30,250
του πανεπιστημίου που αντιστοιχεί
σε αυτό το κλειδί, αυτά τα τέσσερα ψηφία.

71
00:03:30,250 --> 00:03:34,390
Η βασική ιδέα πίσω από ένα trie
είναι ότι έχουμε μια κεντρική διαδρομή.

72
00:03:34,390 --> 00:03:35,640
Έτσι σκεφτείτε το σαν ένα δέντρο.

73
00:03:35,640 --> 00:03:39,211
Και αυτό είναι παρόμοιο στην ορθογραφία
και στην ιδέα για ένα δέντρο.

74
00:03:39,211 --> 00:03:41,460
Σε γενικές γραμμές όταν σκεφτόμαστε
δέντρα στον πραγματικό κόσμο,

75
00:03:41,460 --> 00:03:44,090
έχουν μια ρίζα που είναι στην
έδαφος και αναπτύσσονται προς τα πάνω

76
00:03:44,090 --> 00:03:46,830
και έχουν υποκαταστήματα
και έχουν τα φύλλα.

77
00:03:46,830 --> 00:03:49,450
Και βασικά η ιδέα της
α trie είναι ακριβώς το ίδιο,

78
00:03:49,450 --> 00:03:51,755
εκτός από το ότι η ρίζα αγκυροβολημένο
κάπου στον ουρανό.

79
00:03:51,755 --> 00:03:53,130
Και τα φύλλα βρίσκονται στο κάτω μέρος.

80
00:03:53,130 --> 00:03:55,750
>> Έτσι είναι το είδος του όπως τη λήψη ενός δέντρου
και απλά να ρίχνεις ανάποδα.

81
00:03:55,750 --> 00:03:56,880
Αλλά εξακολουθούν να υπάρχουν υποκαταστήματα.

82
00:03:56,880 --> 00:03:59,463
Και αυτοί θα είναι οδών μας,
Αυτές θα είναι οι συνδέσεις μας

83
00:03:59,463 --> 00:04:02,220
από τη ρίζα προς τα φύλλα.

84
00:04:02,220 --> 00:04:04,200
Σε αυτήν την περίπτωση, εκείνοι
μονοπάτια, τα υποκαταστήματα

85
00:04:04,200 --> 00:04:08,490
επισημαίνονται με ψηφία που μας λένε
ποιο τρόπο να πάει από εκεί που είμαστε.

86
00:04:08,490 --> 00:04:11,800
>> Αν δούμε ένα 0, κατεβαίνουμε αυτόν τον κλάδο,
Αν δούμε ένα 1, κατεβαίνουμε αυτόν τον κλάδο,

87
00:04:11,800 --> 00:04:12,900
και ούτω και ούτω καθεξής.

88
00:04:12,900 --> 00:04:14,060
Λοιπόν, τι σημαίνει αυτό;

89
00:04:14,060 --> 00:04:16,519
Λοιπόν, αυτό σημαίνει ότι
σε κάθε σημείο διασταύρωση

90
00:04:16,519 --> 00:04:19,260
και κάθε κόμβος στο
μεσαία και κάθε υποκατάστημα,

91
00:04:19,260 --> 00:04:23,020
υπάρχουν 10 πιθανές
μέρη που μπορούμε να πάμε.

92
00:04:23,020 --> 00:04:27,690
Έτσι, υπάρχουν 10 δείκτες
από κάθε τοποθεσία.

93
00:04:27,690 --> 00:04:30,610
>> Και αυτό είναι που προσπαθεί να πάρει μια
λίγο εκφοβιστικό για κάποιον

94
00:04:30,610 --> 00:04:34,460
ποιος δεν έχει πολλή
εμπειρία στην επιστήμη των υπολογιστών πριν.

95
00:04:34,460 --> 00:04:35,960
Αλλά προσπαθεί είναι πραγματικά πολύ ωραία.

96
00:04:35,960 --> 00:04:37,793
Και αν έχετε το
την ευκαιρία να συνεργαστούμε μαζί τους

97
00:04:37,793 --> 00:04:40,420
και είστε πρόθυμοι να σκάψουν στο
και να πειραματιστούν μαζί τους,

98
00:04:40,420 --> 00:04:44,234
είναι πραγματικά πολύ ενδιαφέρον
δομές δεδομένων για να εργαστείτε με.

99
00:04:44,234 --> 00:04:46,900
Αν θέλετε να εισάγετε ένα στοιχείο
στο trie, το μόνο που χρειάζεται να κάνουμε

100
00:04:46,900 --> 00:04:51,360
έχει χτίσει τη σωστή διαδρομή
από τη ρίζα στο φύλλο.

101
00:04:51,360 --> 00:04:55,390
Εδώ είναι αυτό που σε κάθε βήμα κατά μήκος
ο τρόπος που μπορεί να μοιάζει.

102
00:04:55,390 --> 00:04:59,660
Εμείς πάμε για να ορίσετε μια νέα δεδομένα
δομή για ένα νέο κόμβο που ονομάζεται trie.

103
00:04:59,660 --> 00:05:02,560
>> Και μέσα σε αυτά τα δεδομένα
δομή υπάρχουν δύο κομμάτια.

104
00:05:02,560 --> 00:05:05,460
Εμείς πάμε για να αποθηκεύσετε το
το όνομα του πανεπιστημίου.

105
00:05:05,460 --> 00:05:09,410
Και θα πάμε να αποθηκεύσετε
μια σειρά από δείκτες

106
00:05:09,410 --> 00:05:12,190
σε άλλους κόμβους του ίδιου τύπου.

107
00:05:12,190 --> 00:05:14,780
Έτσι, και πάλι, αυτό είναι ότι το είδος
της έννοιας της παντού

108
00:05:14,780 --> 00:05:18,567
είμαστε, σε 10 πιθανές
μέρη που μπορούμε να πάμε.

109
00:05:18,567 --> 00:05:20,150
Αν δούμε ένα 0, μπορούμε να ακολουθήσουμε αυτόν τον κλάδο.

110
00:05:20,150 --> 00:05:22,690
Αν δούμε ένα 1, ο κλάδος αυτός,
και ούτω καθεξής και ούτω καθεξής και ούτω καθεξής.

111
00:05:22,690 --> 00:05:25,160
Αν λέμε 9, κατηφορίζουμε αυτόν τον κλάδο.

112
00:05:25,160 --> 00:05:28,220
Έτσι, σε κάθε σημείο σύνδεσης,
μπορούμε να πάμε 10 πιθανές θέσεις.

113
00:05:28,220 --> 00:05:35,740
Έτσι, κάθε κόμβος πρέπει να περιέχει 10 δείκτες
σε άλλους κόμβους, για 10 άλλους κόμβους.

114
00:05:35,740 --> 00:05:39,810
>> Και τα δεδομένα είμαστε αποθήκευσης είναι
μόνο το όνομα του πανεπιστημίου.

115
00:05:39,810 --> 00:05:41,060
Ας οικοδομήσουμε μια trie.

116
00:05:41,060 --> 00:05:44,860
Ας εισάγετε ένα ζευγάρι
των στοιχείων σε Trie μας.

117
00:05:44,860 --> 00:05:46,740
Έτσι, στην κορυφή,
Αυτή είναι η ρίζα του κόμβου μας.

118
00:05:46,740 --> 00:05:49,740
Αυτό κατά πάσα πιθανότητα πρόκειται να είναι κάτι
θα πάμε να δηλώνουν παγκόσμιο επίπεδο.

119
00:05:49,740 --> 00:05:53,450
Και θα πάμε να διατηρήσει παγκόσμιο επίπεδο
ένας δείκτης σε αυτόν τον κόμβο πάντα.

120
00:05:53,450 --> 00:05:55,360
>> Θα πάμε να πούμε,
ρίζα ισούται με, και είστε

121
00:05:55,360 --> 00:05:57,580
πρόκειται να malloc εαυτό trie κόμβο.

122
00:05:57,580 --> 00:05:59,850
Και αν δεν πρόκειται ποτέ
να αγγίξει και πάλι ρίζα.

123
00:05:59,850 --> 00:06:02,300
Κάθε φορά που θέλετε να
ξεκινήσετε την πλοήγηση μέσα,

124
00:06:02,300 --> 00:06:05,802
ορίσετε έναν άλλο δείκτη
ίσο με ρίζα, όπως trav,

125
00:06:05,802 --> 00:06:07,760
η οποία είναι το παράδειγμα Ι
χρήση σε πολλά από τα βίντεό μου

126
00:06:07,760 --> 00:06:11,090
εδώ για στοίβες και ουρές
και τους καταλόγους σύνδεσμο και ούτω καθεξής.

127
00:06:11,090 --> 00:06:13,320
>> Μπορείτε να ορίσετε έναν άλλο δείκτη
που ονομάζεται Trav για διάσχιση.

128
00:06:13,320 --> 00:06:15,890
Και μπορείτε να χρησιμοποιήσετε για να περιηγηθείτε Trav
μέσω της δομής των δεδομένων.

129
00:06:15,890 --> 00:06:17,500
Ας δούμε πώς αυτό μπορεί να μοιάζει.

130
00:06:17,500 --> 00:06:19,880
Έτσι τώρα, τι
ένας κόμβος δεν μοιάζει;

131
00:06:19,880 --> 00:06:22,920
Λοιπόν, όπως ακριβώς τα δεδομένα μας
δήλωση δομή υποδεικνύεται,

132
00:06:22,920 --> 00:06:26,906
έχουμε μια σειρά, η οποία
στην περίπτωση αυτή είναι κενή.

133
00:06:26,906 --> 00:06:27,780
Δεν υπάρχει τίποτα εδώ.

134
00:06:27,780 --> 00:06:29,550
>> Και μια σειρά από 10 δείκτες.

135
00:06:29,550 --> 00:06:31,790
Και τώρα, έχουμε μόνο
έχουν 1 κόμβος σε αυτή την trie.

136
00:06:31,790 --> 00:06:33,110
Δεν υπάρχει τίποτα άλλο σε αυτό.

137
00:06:33,110 --> 00:06:36,020
Έτσι, οι 10 από αυτούς
δείκτες σημείο σε null.

138
00:06:36,020 --> 00:06:38,090
Αυτό είναι ό, τι δείχνει το κόκκινο.

139
00:06:38,090 --> 00:06:39,500
>> Ας εισάγετε τα στοιχεία του Χάρβαρντ.

140
00:06:39,500 --> 00:06:41,999
Ας προστεθεί το Πανεπιστήμιο του
Χάρβαρντ σε αυτό το Trie, η οποία

141
00:06:41,999 --> 00:06:43,940
ιδρύθηκε το έτος 1636.

142
00:06:43,940 --> 00:06:48,220
Θέλουμε να χρησιμοποιήσετε το πλήκτρο,
1636, για να μας πει πού είμαστε

143
00:06:48,220 --> 00:06:50,140
πρόκειται να αποθηκεύσετε το Χάρβαρντ στο Trie.

144
00:06:50,140 --> 00:06:51,470
Τώρα, πώς θα μπορούσαμε να το κάνουμε αυτό;

145
00:06:51,470 --> 00:06:52,886
>> Θα μπορούσε να είναι κάπως έτσι.

146
00:06:52,886 --> 00:06:54,160
Ξεκινάμε από τη ρίζα.

147
00:06:54,160 --> 00:06:56,920
Και έχουμε αυτές τις 10 θέσεις που μπορούμε να πάμε.

148
00:06:56,920 --> 00:06:59,900
Η ρίζα είναι ακριβώς όπως οποιοδήποτε
άλλο κόμβο του Trie.

149
00:06:59,900 --> 00:07:02,850
Υπάρχουν 10 θέσεις μπορούμε να πάμε από εδώ.

150
00:07:02,850 --> 00:07:07,215
>> Πού θα θελήσετε πιθανώς
για να πάει, αν το κλειδί είναι 1636;

151
00:07:07,215 --> 00:07:08,340
Υπάρχει πραγματικά δύο επιλογές.

152
00:07:08,340 --> 00:07:08,450
Δεξιά.

153
00:07:08,450 --> 00:07:10,825
Μπορούμε να οικοδομήσουμε το κλειδί από
δεξιά προς τα αριστερά και να αρχίσει με 6.

154
00:07:10,825 --> 00:07:14,000
Ή θα μπορούσαμε να οικοδομήσουμε το κλειδί από
αριστερά προς τα δεξιά και να αρχίσει με 1.

155
00:07:14,000 --> 00:07:16,140
>> Είναι ίσως περισσότερο
διαισθητική ως ανθρώπινο ον

156
00:07:16,140 --> 00:07:18,110
να καταλαβαίνουμε θα
Απλά πηγαίνετε αριστερά προς τα δεξιά.

157
00:07:18,110 --> 00:07:21,140
Και έτσι αν θέλετε να εισάγετε
Χάρβαρντ σε αυτό το Trie,

158
00:07:21,140 --> 00:07:23,560
Μάλλον θέλετε να ξεκινήσετε
ξεκινώντας από τη ρίζα,

159
00:07:23,560 --> 00:07:25,720
κοιτάζοντας τις επιλογές μου 10
μπροστά μου, και λέγοντας

160
00:07:25,720 --> 00:07:28,700
Θέλω να πάω κάτω από το 1 διαδρομή.

161
00:07:28,700 --> 00:07:29,700
ΕΝΤΆΞΕΙ.

162
00:07:29,700 --> 00:07:31,810
>> Τώρα, 1 μονοπάτι είναι σήμερα μηδενική.

163
00:07:31,810 --> 00:07:35,920
Έτσι, αν θέλω να προχωρήσουμε σε αυτή την κατεύθυνση
για να εισαγάγετε αυτό το στοιχείο στο Trie,

164
00:07:35,920 --> 00:07:42,040
Έχω να malloc ενός νέου κόμβου, έχουν 1
σημείο εκεί, και τότε είμαι καλό να πάει.

165
00:07:42,040 --> 00:07:46,460
>> Γι 'αυτό και ουσιαστικά είμαι σε μια
σημείο όπου στέκομαι

166
00:07:46,460 --> 00:07:50,270
στη ρίζα του δέντρου ή του
trie και υπάρχουν 10 υποκαταστήματα.

167
00:07:50,270 --> 00:07:52,260
Αλλά κάθε υποκατάστημα έχει
πύλη μπροστά του.

168
00:07:52,260 --> 00:07:53,060
Δεξιά.

169
00:07:53,060 --> 00:07:54,850
Επειδή δεν υπάρχει τίποτα άλλο εκεί.

170
00:07:54,850 --> 00:07:56,522
Δεν ασφαλή διέλευση.

171
00:07:56,522 --> 00:07:58,980
Αυτό σημαίνει ότι δεν υπάρχει τίποτα
κάτω από οποιοδήποτε από τα υποκαταστήματα αυτά.

172
00:07:58,980 --> 00:08:02,532
Αν θέλω να αρχίσει η δημιουργία
κάτι, θέλω να αφαιρέσω την πύλη.

173
00:08:02,532 --> 00:08:04,490
Θέλω να καταργήσω την πύλη
μπροστά από τον αριθμό 1.

174
00:08:04,490 --> 00:08:05,698
Και θέλω να περπατήσουν κάτω από αυτό.

175
00:08:05,698 --> 00:08:08,060
Και θέλω να οικοδομήσουμε
ένα άλλο μέρος για μένα να πάω.

176
00:08:08,060 --> 00:08:09,470
>> Και αυτό είναι ό, τι έχω κάνει εδώ.

177
00:08:09,470 --> 00:08:11,430
Έτσι, δεν είναι πλέον 1 σημεία σε μηδέν.

178
00:08:11,430 --> 00:08:13,830
Έχω πει ότι είναι ασφαλές να πάει κάτω εδώ τώρα.

179
00:08:13,830 --> 00:08:15,789
Έφτιαξα ένα άλλο κόμβο.

180
00:08:15,789 --> 00:08:18,330
Και όταν φτάσουμε σε αυτό τον κόμβο, Ι
έχουν άλλη απόφαση να κάνει.

181
00:08:18,330 --> 00:08:20,890
Πού θα πάω να πάω από εδώ;

182
00:08:20,890 --> 00:08:22,700
>> Λοιπόν, έχω ήδη πάει κάτω από το 1.

183
00:08:22,700 --> 00:08:24,470
Έτσι τώρα μπορώ πιθανόν να θέλετε να πάει κάτω από το 6.

184
00:08:24,470 --> 00:08:24,970
Δεξιά.

185
00:08:24,970 --> 00:08:27,100
Και πάλι, έχω 10 θέσεις μπορώ να επιλέξω.

186
00:08:27,100 --> 00:08:30,060
Ας πάμε τώρα κάτω από τον αριθμό 6.

187
00:08:30,060 --> 00:08:32,280
Γι 'αυτό και καταργήστε την πύλη
μπροστά από τον αριθμό 6.

188
00:08:32,280 --> 00:08:33,250
Και περπατώ εκεί κάτω.

189
00:08:33,250 --> 00:08:34,580
Και μπορώ να δημιουργήσω έναν άλλο κόμβο.

190
00:08:34,580 --> 00:08:37,630
Και έχω φθάσει σε ένα άλλο κομβικό σημείο.

191
00:08:37,630 --> 00:08:40,289
>> Και πάλι, έχω 10 επιλογές
για το πού μπορώ να πάω.

192
00:08:40,289 --> 00:08:42,799
Έχω μετακινηθεί 1-6.

193
00:08:42,799 --> 00:08:44,215
Έτσι τώρα μπορώ ίσως θέλουν να πάνε στο 3.

194
00:08:44,215 --> 00:08:45,381
3, δεν υπάρχει πουθενά μπορώ να πάω.

195
00:08:45,381 --> 00:08:48,980
Γι 'αυτό πρέπει να ανοίξει το δρόμο
και να οικοδομήσουμε τον εαυτό μου ένα νέο χώρο.

196
00:08:48,980 --> 00:08:50,870
Και μετά από 3, πού θέλω να πάω;

197
00:08:50,870 --> 00:08:52,450
Θέλω να πάω κάτω 6.

198
00:08:52,450 --> 00:08:54,770
>> Και, πάλι, έπρεπε να
ανοίξει το δρόμο για να το κάνουμε.

199
00:08:54,770 --> 00:08:59,179
Μέχρι τώρα έχω χρησιμοποιήσει το κλειδί μου για να εισάγετε τη δημιουργία
κόμβους και να αρχίσει να χτίσει αυτό το Trie.

200
00:08:59,179 --> 00:09:00,220
Έχω αρχίσει στη ρίζα.

201
00:09:00,220 --> 00:09:03,666
Έχω πάει κάτω 1636.

202
00:09:03,666 --> 00:09:05,540
Και τώρα είμαι στο κάτω μέρος
εκεί σε αυτόν τον κόμβο.

203
00:09:05,540 --> 00:09:06,610
Και ίσως να είναι σε θέση να
δείτε στην οθόνη σας.

204
00:09:06,610 --> 00:09:07,735
>> Είναι επισημαίνονται με κίτρινο χρώμα.

205
00:09:07,735 --> 00:09:10,020
Αυτό είναι όπου είμαι σήμερα.

206
00:09:10,020 --> 00:09:11,300
Κλειδί μου γίνεται.

207
00:09:11,300 --> 00:09:13,030
Έχω εξαντλήσει κάθε θέση κλειδί μου.

208
00:09:13,030 --> 00:09:15,040
Έτσι, δεν μπορώ να προχωρήσουμε περαιτέρω.

209
00:09:15,040 --> 00:09:17,720
Έτσι, σε αυτό το σημείο, το μόνο που μπορώ
πρέπει πραγματικά να κάνουμε είναι να πούμε, εντάξει.

210
00:09:17,720 --> 00:09:18,990
Είναι το είδος του αρέσει που αναζητούν
κάτω στο έδαφος,

211
00:09:18,990 --> 00:09:21,115
αν είστε οραματίζονται
τον εαυτό σας όπως αυτό το είδος της διαδρομής

212
00:09:21,115 --> 00:09:22,350
με διαφορετικές συνδέσεις.

213
00:09:22,350 --> 00:09:25,800
Ταξινόμηση της κοιτάζοντας προς τα κάτω και το είδος
σπρέι βαφής Χάρβαρντ στο έδαφος.

214
00:09:25,800 --> 00:09:26,800
Αυτό είναι το όνομα του αυτό.

215
00:09:26,800 --> 00:09:28,300
Να ξέρετε ότι είναι ό, τι είναι σε αυτή τη θέση.

216
00:09:28,300 --> 00:09:31,870
Αν αρχίσουμε από τη ρίζα και κατηφορίζουμε
1 και στη συνέχεια 6 και, στη συνέχεια, 3 και στη συνέχεια 6,

217
00:09:31,870 --> 00:09:32,780
που είμαστε?

218
00:09:32,780 --> 00:09:35,640
Λοιπόν, αν κοιτάξουμε προς τα κάτω
και βλέπουμε Χάρβαρντ, στη συνέχεια,

219
00:09:35,640 --> 00:09:38,960
γνωρίζουμε ότι το Χάρβαρντ ήταν
ιδρύθηκε το 1636 με βάση τον τρόπο

220
00:09:38,960 --> 00:09:41,400
είμαστε εφαρμογή αυτής της δομής δεδομένων.

221
00:09:41,400 --> 00:09:43,177
Έτσι, αυτό ήταν ελπίζουμε απλή.

222
00:09:43,177 --> 00:09:44,760
Εμείς πάμε να κάνουμε δύο ακόμα προσθήκες.

223
00:09:44,760 --> 00:09:50,060
Και ελπίζουμε ότι αυτό θα βοηθήσει να
δείτε αυτό το κάνει δύο φορές περισσότερο.

224
00:09:50,060 --> 00:09:52,210
>> Τώρα, ας τοποθετήστε ένα άλλο πανεπιστήμιο.

225
00:09:52,210 --> 00:09:54,630
Ας προστεθεί Yale σε αυτό το Trie.

226
00:09:54,630 --> 00:09:57,037
Yale ιδρύθηκε το 1701.

227
00:09:57,037 --> 00:09:58,870
Έτσι θα ξεκινήσει κατά τη
ρίζα, όπως κάνουμε πάντα.

228
00:09:58,870 --> 00:09:59,890
Και έχουμε δημιουργήσει ένα δείκτη διάσχισης.

229
00:09:59,890 --> 00:10:01,624
Εμείς πάμε για να χρησιμοποιήσετε αυτό για να μετακινηθείτε.

230
00:10:01,624 --> 00:10:03,790
Το πρώτο πράγμα που θέλουμε να
κάνετε είναι να πάτε κάτω από το 1 διαδρομή.

231
00:10:03,790 --> 00:10:05,830
Αυτό είναι το πρώτο ψηφίο του κλειδιού μας.

232
00:10:05,830 --> 00:10:08,420
Ευτυχώς, όμως, δεν το κάνουμε
Πρέπει να κάνει οποιαδήποτε εργασία αυτή τη φορά.

233
00:10:08,420 --> 00:10:09,919
Η διαδρομή 1 έχει ήδη εκκαθαριστεί.

234
00:10:09,919 --> 00:10:13,520
Μου εκκαθαριστεί προηγουμένως, όταν
η εισαγωγή του Χάρβαρντ στο 1636.

235
00:10:13,520 --> 00:10:18,090
Γι 'αυτό και μπορεί να κινηθεί με ασφάλεια
κάτω από 1 και πήγαινε εκεί.

236
00:10:18,090 --> 00:10:20,150
Αν μπορεί να κινηθεί κάτω από το 1.

237
00:10:20,150 --> 00:10:22,930
>> Τώρα, όμως, θέλω να πάω στο 7.

238
00:10:22,930 --> 00:10:24,280
Θα ανοίξει το δρόμο σε 6.

239
00:10:24,280 --> 00:10:27,050
Ξέρω ότι μπορώ με ασφάλεια
να προχωρήσει προς τα κάτω το μονοπάτι 6.

240
00:10:27,050 --> 00:10:29,220
Αλλά πρέπει να προχωρήσουμε στο δρόμο 7.

241
00:10:29,220 --> 00:10:30,580
Οπότε τι πρέπει να κάνω;

242
00:10:30,580 --> 00:10:35,070
Λοιπόν, ακριβώς όπως και πριν, το μόνο που χρειάζεται
για να καταργήσετε την πύλη, να βγει από το δρόμο,

243
00:10:35,070 --> 00:10:38,740
και να οικοδομήσουμε ένα νέο κόμβο από τη διαδρομή 7.

244
00:10:38,740 --> 00:10:40,250
Όπως αυτό.

245
00:10:40,250 --> 00:10:42,930
>> Έτσι τώρα έχω μετακινηθεί 1 και στη συνέχεια 7.

246
00:10:42,930 --> 00:10:45,550
Και τώρα παρατηρήσετε, είμαι το είδος
του σε αυτό το νέο subbranch.

247
00:10:45,550 --> 00:10:46,050
Δεξιά.

248
00:10:46,050 --> 00:10:49,260
Όλα τα υπόλοιπα από 16
σε, εγώ δεν νοιάζονται για.

249
00:10:49,260 --> 00:10:50,720
Εγώ δεν κάνω τίποτα 16.

250
00:10:50,720 --> 00:10:51,750
Κάνω 17 πράγματα.

251
00:10:51,750 --> 00:10:58,380
>> Έτσι τώρα, από τις 17 και στο εξής, θα πρέπει να
είδος χαράξει νέα μονοπάτια εδώ.

252
00:10:58,380 --> 00:11:00,462
Το επόμενο ψηφίο είναι το κλειδί μου 0.

253
00:11:00,462 --> 00:11:01,670
Προφανώς δεν μπορώ να πάρετε οπουδήποτε.

254
00:11:01,670 --> 00:11:02,628
Απλά έχτισε αυτό το κόμβο.

255
00:11:02,628 --> 00:11:04,550
Έτσι ξέρω ότι δεν υπάρχει κανένας
μονοπάτια προς τα εμπρός από εδώ.

256
00:11:04,550 --> 00:11:06,370
Έτσι έχω να κάνω τον εαυτό μου.

257
00:11:06,370 --> 00:11:09,360
>> Γι 'αυτό και malloc ενός νέου κόμβου
και έχουν σημείο 0 εκεί.

258
00:11:09,360 --> 00:11:12,770
Και στη συνέχεια, για μια ακόμη φορά, έχω ένα malloc
νέο κόμβο και να έχουν ένα σημείο εκεί.

259
00:11:12,770 --> 00:11:15,870
Και πάλι, έχω εξαντλήσει το κλειδί μου, 1701.

260
00:11:15,870 --> 00:11:18,472
Έτσι κοιτάζω κάτω και σπρέι βαφής Yale.

261
00:11:18,472 --> 00:11:19,680
Αυτό είναι το όνομα αυτού του κόμβου.

262
00:11:19,680 --> 00:11:24,660
>> Και έτσι τώρα αν ποτέ χρειαστεί να δούμε αν Yale
Είναι σε αυτό το trie, μπορώ να ξεκινήσω από τη ρίζα,

263
00:11:24,660 --> 00:11:27,060
Κατέβω 1701, και να κοιτάξει κάτω.

264
00:11:27,060 --> 00:11:30,030
Και αν δω σπρέι Yale
ζωγραφισμένα στο έδαφος, στη συνέχεια,

265
00:11:30,030 --> 00:11:32,200
Ξέρω Yale υπάρχει σε αυτή την trie.

266
00:11:32,200 --> 00:11:32,950
Ας κάνουμε ένα ακόμη.

267
00:11:32,950 --> 00:11:36,430
Ας προστεθεί σε αυτό Ντάρτμουθ
trie, η οποία ιδρύθηκε το 1769.

268
00:11:36,430 --> 00:11:37,750
>> Ξεκινήστε από τη ρίζα και πάλι.

269
00:11:37,750 --> 00:11:39,445
Η πρώτη μου ψηφίο του κλειδιού μου είναι 1.

270
00:11:39,445 --> 00:11:40,820
Μπορώ να κινηθεί με ασφάλεια σε αυτή την κατεύθυνση.

271
00:11:40,820 --> 00:11:42,400
Που ήδη υπάρχει.

272
00:11:42,400 --> 00:11:44,040
Το επόμενο ψηφίο του κλειδιού μου είναι 7.

273
00:11:44,040 --> 00:11:45,890
Μπορώ να κινηθεί με ασφάλεια σε αυτή την κατεύθυνση.

274
00:11:45,890 --> 00:11:47,540
Υπάρχει επίσης.

275
00:11:47,540 --> 00:11:49,000
>> Δίπλα μου είναι 6.

276
00:11:49,000 --> 00:11:52,860
Από εδώ, απ 'όπου βρίσκομαι σήμερα
σε κίτρινο υπάρχει σε αυτή τη μεσαία κόμβο,

277
00:11:52,860 --> 00:11:56,060
6 είναι κλειδωμένος μακριά.

278
00:11:56,060 --> 00:11:58,830
Αν θέλω να πάω σε αυτή την κατεύθυνση,
Έχω να το κατασκευάσω μόνος μου.

279
00:11:58,830 --> 00:12:02,250
Γι 'αυτό θα malloc ενός νέου κόμβου
και έχει 6 σημείο εκεί.

280
00:12:02,250 --> 00:12:04,250
Και τότε, και πάλι, είμαι
απίστευτα νέα μονοπάτια εδώ.

281
00:12:04,250 --> 00:12:10,750
>> Γι 'αυτό και malloc ένα νέο κόμβο έτσι ώστε από
ότι node-- αριθμός διαδρομής 9-- και, στη συνέχεια, τώρα

282
00:12:10,750 --> 00:12:13,584
αν ταξιδεύω 1769, και κοιτάζω προς τα κάτω.

283
00:12:13,584 --> 00:12:15,500
Δεν υπάρχει τίποτα επί του παρόντος
σπρέι ζωγραφισμένα εκεί.

284
00:12:15,500 --> 00:12:16,930
Μπορώ να γράψω Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Και έχω εισαχθεί
Dartmouth στο Trie.

286
00:12:20,710 --> 00:12:23,450
>> Έτσι, αυτό είναι εισαγωγή
τα πράγματα στο Trie.

287
00:12:23,450 --> 00:12:25,384
Τώρα θέλουμε να αναζητήσετε τα πράγματα.

288
00:12:25,384 --> 00:12:27,050
Πώς μπορώ να ψάχνουμε για πράγματα στο Trie;

289
00:12:27,050 --> 00:12:29,170
Λοιπόν, αυτό είναι λίγο πολύ η ίδια ιδέα.

290
00:12:29,170 --> 00:12:33,620
Τώρα χρησιμοποιούμε μόνο τα ψηφία του κλειδιού
για να δούμε αν μπορούμε να περιηγηθείτε από τη ρίζα

291
00:12:33,620 --> 00:12:37,170
στο σημείο όπου θέλουμε να πάμε στο Trie.

292
00:12:37,170 --> 00:12:41,620
>> Αν χτυπήσει ένα αδιέξοδο σε οποιοδήποτε σημείο, στη συνέχεια,
γνωρίζουμε ότι δεν μπορεί να υπάρχει το στοιχείο αυτό

293
00:12:41,620 --> 00:12:44,500
ή αλλιώς η διαδρομή θα
έχουν ήδη εκκαθαριστεί.

294
00:12:44,500 --> 00:12:45,930
Αν το κάνει όλη τη διαδρομή προς
το τέλος, το μόνο που χρειάζεται να κάνουμε

295
00:12:45,930 --> 00:12:48,471
είναι να κοιτάξει κάτω και να δούμε αν αυτό είναι
το στοιχείο που ψάχνουμε.

296
00:12:48,471 --> 00:12:49,335
Αν είναι, η επιτυχία.

297
00:12:49,335 --> 00:12:52,610
Αν δεν είναι, αποτυγχάνουν.

298
00:12:52,610 --> 00:12:54,940
>> Ας ψάξετε
Χάρβαρντ σε αυτό το Trie.

299
00:12:54,940 --> 00:12:56,020
Ξεκινάμε από τη ρίζα.

300
00:12:56,020 --> 00:12:58,228
Και, πάλι, θα πάμε να
δημιουργία ενός δείκτη διάσχιση

301
00:12:58,228 --> 00:12:59,390
να κάνει τις κινήσεις μας για μας.

302
00:12:59,390 --> 00:13:02,080
Από τη ρίζα γνωρίζουμε ότι η
πρώτο μέρος που πρέπει να πάτε είναι 1,

303
00:13:02,080 --> 00:13:03,390
μπορούμε να το κάνουμε αυτό;

304
00:13:03,390 --> 00:13:03,982
Ναι μπορούμε.

305
00:13:03,982 --> 00:13:04,690
Αν υπάρχει ασφάλεια.

306
00:13:04,690 --> 00:13:06,660
Μπορούμε να πάμε εκεί.

307
00:13:06,660 --> 00:13:08,440
>> Τώρα, το επόμενο μέρος που πρέπει να πάτε είναι 6.

308
00:13:08,440 --> 00:13:10,557
Μήπως η διαδρομή 6 υπάρχουν από εδώ;

309
00:13:10,557 --> 00:13:11,140
Ναι, αυτό κάνει.

310
00:13:11,140 --> 00:13:12,690
Μπορούμε να ακολουθήσουμε τον δρόμο 6.

311
00:13:12,690 --> 00:13:13,905
Και καταλήγουμε εδώ.

312
00:13:13,905 --> 00:13:16,130
>> Μπορούμε να πάμε κάτω από το 3 μονοπάτι από εδώ;

313
00:13:16,130 --> 00:13:18,450
Λοιπόν, όπως αποδεικνύεται,
ναι, ότι υπάρχει πάρα πολύ.

314
00:13:18,450 --> 00:13:20,790
Και μπορούμε να έχουμε στις 6 μονοπάτι από εδώ;

315
00:13:20,790 --> 00:13:21,982
Ναι μπορούμε.

316
00:13:21,982 --> 00:13:24,002
>> Δεν έχουμε αρκετά απαντηθεί
η ερώτηση ακόμα.

317
00:13:24,002 --> 00:13:25,710
Υπάρχει μία ακόμη
βήμα, το οποίο είναι τώρα

318
00:13:25,710 --> 00:13:28,520
θα πρέπει να κοιτάξουμε προς τα κάτω και
να δούμε αν αυτό είναι actually--

319
00:13:28,520 --> 00:13:32,660
αν ψάχνουμε για το Χάρβαρντ, είναι ότι
τι θα βρούμε αφού εξαντλεί το κλειδί;

320
00:13:32,660 --> 00:13:35,430
Στο παράδειγμα που χρησιμοποιούμε εδώ,
τα χρόνια είναι πάντα τέσσερα ψηφία.

321
00:13:35,430 --> 00:13:40,280
Αλλά ίσως να χρησιμοποιώντας το παράδειγμα όπου
αποθηκεύετε ένα λεξικό των λέξεων.

322
00:13:40,280 --> 00:13:44,060
>> Και έτσι αντί να έχουμε 10 δείκτες
για τη θέση μου, μπορείτε να έχετε 26.

323
00:13:44,060 --> 00:13:46,040
Μία για κάθε γράμμα της αλφαβήτου.

324
00:13:46,040 --> 00:13:50,350
Και υπάρχουν κάποιες λέξεις όπως νυχτερίδα,
η οποία είναι ένα υποσύνολο της παρτίδας, για παράδειγμα.

325
00:13:50,350 --> 00:13:53,511
Και έτσι, ακόμη και αν έχετε να το
τέλος του κλειδιού και κοιτάς κάτω,

326
00:13:53,511 --> 00:13:55,260
μπορεί να μην δούμε τι
ψάχνετε.

327
00:13:55,260 --> 00:13:58,500
>> Έτσι, μπορείτε πάντα να διασχίσουμε
ολόκληρη η διαδρομή και στη συνέχεια

328
00:13:58,500 --> 00:14:01,540
αν ήταν σε θέση επιτυχώς
να διασχίσει ολόκληρη τη διαδρομή,

329
00:14:01,540 --> 00:14:03,440
κοιτάξει κάτω και να κάνουμε μια τελική επιβεβαίωση.

330
00:14:03,440 --> 00:14:05,120
Είναι ότι αυτό που ψάχνω;

331
00:14:05,120 --> 00:14:07,740
Λοιπόν, εγώ κοιτάζω προς τα κάτω μετά την έναρξη της
στην κορυφή και πηγαίνοντας 1636.

332
00:14:07,740 --> 00:14:08,240
Κοιτάζω προς τα κάτω.

333
00:14:08,240 --> 00:14:09,400
Βλέπω Χάρβαρντ.

334
00:14:09,400 --> 00:14:11,689
Έτσι, ναι, έχω καταφέρει.

335
00:14:11,689 --> 00:14:13,980
Τι γίνεται αν αυτό που ψάχνω για
δεν είναι στο trie, όμως.

336
00:14:13,980 --> 00:14:17,200
Τι θα συμβεί αν ψάχνω για Princeton,
η οποία ιδρύθηκε το 1746.

337
00:14:17,200 --> 00:14:20,875
Και έτσι γίνεται 1746 κλειδί μου
για να πλοηγηθείτε στο Trie.

338
00:14:20,875 --> 00:14:22,040
Λοιπόν, μπορώ να ξεκινήσω από τη ρίζα.

339
00:14:22,040 --> 00:14:24,760
Και η πρώτη θέση που θέλω
να πηγαίνει κάτω από το 1 διαδρομή.

340
00:14:24,760 --> 00:14:25,590
Μπορώ να το κάνω;

341
00:14:25,590 --> 00:14:26,490
Ναι μπορω.

342
00:14:26,490 --> 00:14:28,730
>> Μπορώ να πάω κάτω από το 7 μονοπάτι από εκεί;

343
00:14:28,730 --> 00:14:29,230
Ναι, μπορώ.

344
00:14:29,230 --> 00:14:30,750
Ότι υπάρχει πάρα πολύ.

345
00:14:30,750 --> 00:14:32,460
Αλλά μπορώ να πάω κάτω από το 4 μονοπάτι από εδώ;

346
00:14:32,460 --> 00:14:35,550
Αυτό είναι σαν να ζητάμε από την ερώτηση, μπορεί να
Θα προχωρήσουμε προς τα κάτω αυτό το μικρό τετράγωνο

347
00:14:35,550 --> 00:14:37,114
ότι έχω επισημαίνονται με κίτρινο χρώμα;

348
00:14:37,114 --> 00:14:38,030
Δεν υπάρχει τίποτα εκεί.

349
00:14:38,030 --> 00:14:38,610
Δεξιά.

350
00:14:38,610 --> 00:14:41,310
>> Δεν υπάρχει δρόμος προς τα εμπρός κάτω από την πορεία 4.

351
00:14:41,310 --> 00:14:46,480
Εάν Princeton ήταν σε αυτό το trie, ότι 4
θα έχουν εκκαθαριστεί για εμάς ήδη.

352
00:14:46,480 --> 00:14:49,130
Και έτσι σε αυτό το σημείο
έχουμε φτάσει σε ένα αδιέξοδο.

353
00:14:49,130 --> 00:14:50,250
Δεν μπορούμε να προχωρήσουμε περαιτέρω.

354
00:14:50,250 --> 00:14:53,440
Και έτσι μπορούμε να πούμε, οριστικά, όχι.

355
00:14:53,440 --> 00:14:56,760
Princeton δεν υπάρχει σε αυτό το Trie.

356
00:14:56,760 --> 00:14:58,860
>> Έτσι τι σημαίνουν όλα αυτά;

357
00:14:58,860 --> 00:14:59,360
Δεξιά.

358
00:14:59,360 --> 00:15:01,000
Υπάρχει μια παρτίδα σε εξέλιξη εδώ.

359
00:15:01,000 --> 00:15:02,500
Υπάρχει δείκτες σε όλη τη χώρα.

360
00:15:02,500 --> 00:15:04,249
Και, όπως μπορείτε να δείτε
μόλις από το διάγραμμα,

361
00:15:04,249 --> 00:15:07,010
υπάρχει μια μεγάλη κόμβους που
είναι το είδος της πετούν γύρω.

362
00:15:07,010 --> 00:15:13,480
Αλλά παρατηρήσετε κάθε φορά που θέλαμε να
ελέγξτε αν κάτι ήταν στην Trie,

363
00:15:13,480 --> 00:15:15,000
είχαμε μόνο να κάνει 4 κινήσεις.

364
00:15:15,000 --> 00:15:17,208
>> Κάθε φορά που θέλαμε να
εισάγετε κάτι στο Trie,

365
00:15:17,208 --> 00:15:20,440
πρέπει να κάνουμε 4 κινήσεις, πιθανώς
mallocing κάποια πράγματα στην πορεία.

366
00:15:20,440 --> 00:15:23,482
Αλλά, όπως είδαμε όταν εισάγεται
Dartmouth στο Trie,

367
00:15:23,482 --> 00:15:25,940
μερικές φορές κάποια της διαδρομής
μπορεί να είναι ήδη εκκαθαριστεί για εμάς.

368
00:15:25,940 --> 00:15:30,520
Και έτσι όπως trie μας παίρνει μεγαλύτερη και
μεγαλύτερο, έχουμε κάνει λιγότερη δουλειά κάθε φορά

369
00:15:30,520 --> 00:15:32,270
για να εισάγετε νέα πράγματα
επειδή έχουμε ήδη

370
00:15:32,270 --> 00:15:35,746
έχτισε ένα μεγάλο μέρος της ενδιαμέσου
καταστήματα κατά μήκος του τρόπου.

371
00:15:35,746 --> 00:15:38,370
Αν έχουμε μόνο ποτέ να εξετάσουμε
4 πράγματα, 4 είναι απλά μια σταθερά.

372
00:15:38,370 --> 00:15:41,750
Πραγματικά είναι το είδος της προσέγγισης
σταθερή χρονική στιγμή της εισαγωγής

373
00:15:41,750 --> 00:15:44,501
και η συνεχής αναζήτηση του χρόνου.

374
00:15:44,501 --> 00:15:47,500
Ο συμβιβασμός, φυσικά, είναι ότι
trie αυτό, όπως μπορείτε να πείτε ίσως,

375
00:15:47,500 --> 00:15:49,030
είναι τεράστια.

376
00:15:49,030 --> 00:15:51,040
Κάθε ένα από αυτούς τους κόμβους
καταλαμβάνει πολύ χώρο.

377
00:15:51,040 --> 00:15:52,090
>> Αλλά αυτό είναι το δίλημμα.

378
00:15:52,090 --> 00:15:55,260
Αν θέλουμε πραγματικά γρήγορα
εισαγωγής, πραγματικά γρήγορη διαγραφή,

379
00:15:55,260 --> 00:15:59,630
και πραγματικά γρήγορη αναζήτηση, θα πρέπει να
έχουν πολλά δεδομένα που πετούν γύρω.

380
00:15:59,630 --> 00:16:03,590
Πρέπει να αναιρέσει ένα πολύ χώρο
και η μνήμη για την εν λόγω δομή δεδομένων

381
00:16:03,590 --> 00:16:04,290
να υπάρχει.

382
00:16:04,290 --> 00:16:05,415
>> Και έτσι αυτό είναι το δίλημμα.

383
00:16:05,415 --> 00:16:07,310
Αλλά φαίνεται σαν να
θα μπορούσε να βρει.

384
00:16:07,310 --> 00:16:09,560
Θα μπορούσαμε να διαπιστώσει ότι
άγιο δισκοπότηρο των δομών δεδομένων

385
00:16:09,560 --> 00:16:12,264
με γρήγορη εισαγωγή,
διαγραφή και αναζήτηση.

386
00:16:12,264 --> 00:16:14,430
Και ίσως αυτό θα είναι ένα
κατάλληλη δομή δεδομένων

387
00:16:14,430 --> 00:16:18,890
που θα χρησιμοποιηθεί για οποιαδήποτε πληροφορία
προσπαθούμε να κατάστημα.

388
00:16:18,890 --> 00:16:21,860
Είμαι ο Νταγκ Lloyd, αυτό είναι CS50.

389
00:16:21,860 --> 00:16:23,433