1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Δυαδική Αναζήτηση]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Πανεπιστήμιο του Χάρβαρντ]

3
00:00:04,000 --> 00:00:07,000
[Αυτό είναι CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Αν σας έδωσα μια λίστα με τα ονόματα των χαρακτήρων της Disney σε αλφαβητική σειρά

5
00:00:09,000 --> 00:00:11,000
και σας ζήτησε να βρείτε Μίκυ Μάους,

6
00:00:11,000 --> 00:00:13,000
πώς θα μπορείτε να κάνετε για αυτό;

7
00:00:13,000 --> 00:00:15,000
Ένας προφανής τρόπος θα ήταν να σαρώσει τη λίστα από την αρχή

8
00:00:15,000 --> 00:00:18,000
και ελέγξτε κάθε όνομα για να δείτε αν είναι Μίκυ.

9
00:00:18,000 --> 00:00:22,000
Αλλά, όπως μπορείτε να διαβάσετε Aladdin, Alice, Ariel, και ούτω καθεξής,

10
00:00:22,000 --> 00:00:25,000
γρήγορα θα συνειδητοποιήσετε ότι ξεκινώντας από το μπροστινό μέρος του καταλόγου δεν ήταν μια καλή ιδέα.

11
00:00:25,000 --> 00:00:29,000
Εντάξει, ίσως θα πρέπει να αρχίσουμε να εργαζόμαστε προς τα πίσω από το τέλος της λίστας.

12
00:00:29,000 --> 00:00:33,000
Τώρα μπορείτε να διαβάσετε Ταρζάν, Stitch, Χιονάτη, και ούτω καθεξής.

13
00:00:33,000 --> 00:00:36,000
Παρόλα αυτά, αυτό δεν φαίνεται σαν ο καλύτερος τρόπος να πάει για αυτό.

14
00:00:36,000 --> 00:00:38,000
>> Λοιπόν, ένας άλλος τρόπος που θα μπορούσε να πάει για να κάνει αυτό είναι να προσπαθήσουμε να περιορίσετε

15
00:00:38,000 --> 00:00:41,000
ο κατάλογος των ονομάτων που θα πρέπει να εξετάσουμε.

16
00:00:41,000 --> 00:00:43,000
Από τη στιγμή που γνωρίζουμε ότι είναι σε αλφαβητική σειρά,

17
00:00:43,000 --> 00:00:45,000
θα μπορούσατε ακριβώς να δούμε τα ονόματα στη μέση της λίστας

18
00:00:45,000 --> 00:00:49,000
και ελέγξτε αν Μίκυ Μάους είναι πριν ή μετά από αυτό το όνομα.

19
00:00:49,000 --> 00:00:51,000
Κοιτάζοντας το τελευταίο όνομα στη δεύτερη στήλη

20
00:00:51,000 --> 00:00:54,000
τότε θα συνειδητοποιήσετε ότι για Μ Mickey έρχεται μετά από J για Jasmine,

21
00:00:54,000 --> 00:00:57,000
έτσι θα αγνοήσουν απλά το πρώτο ήμισυ του καταλόγου.

22
00:00:57,000 --> 00:00:59,000
Στη συνέχεια, θα ήθελα ίσως δούμε στην κορυφή της την τελευταία στήλη

23
00:00:59,000 --> 00:01:02,000
και να δούμε ότι αυτή η διαδικασία αρχίζει με Ραπουνζέλ.

24
00:01:02,000 --> 00:01:06,000
Mickey έρχεται πριν Ραπουνζέλ? Μοιάζει μπορούμε να αγνοήσουμε την τελευταία στήλη, καθώς και.

25
00:01:06,000 --> 00:01:08,000
Συνεχίζοντας τη στρατηγική αναζήτησης, θα δείτε ότι γρήγορα Mickey

26
00:01:08,000 --> 00:01:11,000
είναι στο πρώτο μισό του εναπομένοντος λίστα των ονομάτων

27
00:01:11,000 --> 00:01:14,000
και, τέλος, βρείτε Mickey κρύβονται μεταξύ Merlin και Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Αυτό που μόλις έκανε ήταν ουσιαστικά δυαδική αναζήτηση.

29
00:01:17,000 --> 00:01:22,000
Όπως το όνομα υπονοεί, εκτελεί αναζήτηση στρατηγική του σε ένα δυαδικό θέμα.

30
00:01:22,000 --> 00:01:24,000
Τι σημαίνει αυτό;

31
00:01:24,000 --> 00:01:27,000
Λοιπόν, δίνεται μια λίστα με ταξινομημένα στοιχεία, ο αλγόριθμος δυαδικής αναζήτησης κάνει μια δυαδική απόφαση -

32
00:01:27,000 --> 00:01:33,000
αριστερά ή δεξιά, μεγαλύτερη ή μικρότερη από, αλφαβητικά πριν ή μετά - σε κάθε σημείο.

33
00:01:33,000 --> 00:01:35,000
Τώρα που έχουμε ένα όνομα που πηγαίνει μαζί με αυτό τον αλγόριθμο αναζήτησης,

34
00:01:35,000 --> 00:01:38,000
Ας δούμε ένα άλλο παράδειγμα, αλλά αυτή τη φορά με μια λίστα ταξινομημένο αριθμούς.

35
00:01:38,000 --> 00:01:43,000
Πείτε ψάχνουμε για τον αριθμό 144 σε αυτή τη λίστα των αριθμών ταξινομημένο.

36
00:01:43,000 --> 00:01:46,000
Όπως και πριν, θα βρούμε τον αριθμό που είναι στη μέση -

37
00:01:46,000 --> 00:01:50,000
το οποίο στην περίπτωση αυτή είναι 13 - και να δούμε αν 144 είναι μεγαλύτερη ή μικρότερη από 13.

38
00:01:50,000 --> 00:01:54,000
Δεδομένου ότι είναι σαφώς μεγαλύτερο από 13, δεν μπορούμε να αγνοήσουμε τα πάντα που είναι 13 ή λιγότερο

39
00:01:54,000 --> 00:01:57,000
και να επικεντρώνονται απλώς στο υπόλοιπο μισό.

40
00:01:57,000 --> 00:01:59,000
Δεδομένου ότι έχουμε τώρα ένα ακόμη αριθμό των ειδών που έφυγε,

41
00:01:59,000 --> 00:02:01,000
επιλέγουμε απλώς έναν αριθμό που είναι κοντά στο κέντρο.

42
00:02:01,000 --> 00:02:03,000
Σε αυτή την περίπτωση έχουμε επιλέξει 55.

43
00:02:03,000 --> 00:02:06,000
Θα μπορούσαμε να είχαμε εξίσου εύκολα επιλέξει 89.

44
00:02:06,000 --> 00:02:11,000
Εντάξει. Και πάλι, 144 είναι μεγαλύτερο από 55, έτσι ώστε να πάμε προς τα δεξιά.

45
00:02:11,000 --> 00:02:14,000
Ευτυχώς για μας, ο επόμενος αριθμός μέση είναι 144,

46
00:02:14,000 --> 00:02:16,000
αυτός που ψάχνουμε.

47
00:02:16,000 --> 00:02:21,000
Έτσι, προκειμένου να βρει 144 χρησιμοποιώντας μια δυαδική αναζήτηση, είμαστε σε θέση να το βρείτε μόνο σε 3 βήματα.

48
00:02:21,000 --> 00:02:24,000
Αν θα χρησιμοποιηθεί γραμμική αναζήτηση εδώ, θα έχουν 12 βήματα μας.

49
00:02:24,000 --> 00:02:28,000
Ως Μάλιστα, εφόσον αυτή η μέθοδος αναζήτησης μειώνει στο μισό τον αριθμό των στοιχείων

50
00:02:28,000 --> 00:02:31,000
πρέπει να δούμε σε κάθε βήμα, θα βρείτε το στοιχείο είναι που ψάχνουν για

51
00:02:31,000 --> 00:02:35,000
περίπου στο αρχείο καταγραφής του αριθμού των στοιχείων στη λίστα.

52
00:02:35,000 --> 00:02:37,000
Τώρα που έχουμε δει 2 παραδείγματα, ας ρίξουμε μια ματιά στο

53
00:02:37,000 --> 00:02:41,000
κάποια ψευδοκώδικα για μια αναδρομική συνάρτηση που υλοποιεί δυαδική αναζήτηση.

54
00:02:41,000 --> 00:02:44,000
Ξεκινώντας από την κορυφή, βλέπουμε ότι πρέπει να βρούμε μια λειτουργία που διαρκεί 4 επιχειρήματα:

55
00:02:44,000 --> 00:02:47,000
κλειδί, σειρά, λεπτά, και max.

56
00:02:47,000 --> 00:02:51,000
Το κλειδί είναι ο αριθμός που ψάχνουμε, έτσι 144 στο προηγούμενο παράδειγμα.

57
00:02:51,000 --> 00:02:54,000
Array είναι η λίστα των αριθμών που ψάχνετε.

58
00:02:54,000 --> 00:02:57,000
Ελάχιστο και μέγιστο είναι οι δείκτες των ελάχιστων και μέγιστων θέσεις

59
00:02:57,000 --> 00:02:59,000
ότι αυτή τη στιγμή εξετάζουμε.

60
00:02:59,000 --> 00:03:03,000
Έτσι, όταν αρχίσουμε, min θα είναι μηδέν και μέγιστη θα είναι το μέγιστο δείκτη του πίνακα.

61
00:03:03,000 --> 00:03:07,000
Όπως περιορίσετε την αναζήτηση προς τα κάτω, θα ενημερώσουμε min και max

62
00:03:07,000 --> 00:03:10,000
να είναι ακριβώς το εύρος που εξακολουθούν να ψάχνουν μέσα

63
00:03:10,000 --> 00:03:12,000
>> Ας μεταβείτε στο ενδιαφέρον μέρος πρώτο.

64
00:03:12,000 --> 00:03:14,000
Το πρώτο πράγμα που κάνουμε είναι να βρούμε το μέσο,

65
00:03:14,000 --> 00:03:19,000
ο δείκτης που είναι στα μισά του δρόμου μεταξύ της ελάχιστης και της μέγιστης του πίνακα ότι είμαστε ακόμα εξεταστεί.

66
00:03:19,000 --> 00:03:22,000
Στη συνέχεια θα εξετάσουμε την αξία του πίνακα στη συγκεκριμένη θέση μέσο

67
00:03:22,000 --> 00:03:25,000
και να δούμε αν ο αριθμός που ψάχνουμε είναι μικρότερο από αυτό το κλειδί.

68
00:03:25,000 --> 00:03:27,000
Εάν ο αριθμός σε αυτή τη θέση είναι μικρότερη,

69
00:03:27,000 --> 00:03:31,000
τότε αυτό σημαίνει ότι το κλειδί είναι μεγαλύτερο από ό, τι όλων των αριθμών στα αριστερά της θέσεως αυτής.

70
00:03:31,000 --> 00:03:33,000
Έτσι, μπορούμε να ονομάσουμε δυαδική λειτουργία αναζήτησης και πάλι,

71
00:03:33,000 --> 00:03:36,000
αλλά αυτή τη φορά την ενημέρωση του min και max παραμέτρους για να διαβάσει μόνο το μισό

72
00:03:36,000 --> 00:03:40,000
που είναι μεγαλύτερη ή ίση με την τιμή που μόλις κοίταξε.

73
00:03:40,000 --> 00:03:44,000
Από την άλλη πλευρά, εάν το κλειδί είναι μικρότερο από τον αριθμό στο τρέχον μέσο της συστοιχίας,

74
00:03:44,000 --> 00:03:47,000
θέλουμε να πάμε προς τα αριστερά και αγνοεί όλους τους αριθμούς που είναι μεγαλύτερες.

75
00:03:47,000 --> 00:03:52,000
Και πάλι, καλούμε δυαδική αναζήτηση, αλλά αυτή τη φορά με τη σειρά του min και max ενημερωμένο

76
00:03:52,000 --> 00:03:54,000
να περιλαμβάνει μόνο το κάτω μισό.

77
00:03:54,000 --> 00:03:57,000
Αν η τιμή στο τρέχον μέσον της συστοιχίας είναι ούτε

78
00:03:57,000 --> 00:04:01,000
ούτε μεγαλύτερο από μικρότερο από το κλειδί, τότε πρέπει να είναι ίσο με το κλειδί.

79
00:04:01,000 --> 00:04:05,000
Έτσι, μπορούμε να επιστρέψουμε απλά τον ισχύοντα μέσο δείκτη, και τελειώσαμε.

80
00:04:05,000 --> 00:04:09,000
Τέλος, αυτός ο έλεγχος είναι εδώ για την περίπτωση που ο αριθμός

81
00:04:09,000 --> 00:04:11,000
δεν είναι στην πραγματικότητα στην διάταξη των αριθμών αναζητούμε.

82
00:04:11,000 --> 00:04:14,000
Εάν η μέγιστη δείκτης της περιοχής που ψάχνουμε για

83
00:04:14,000 --> 00:04:17,000
Είναι όλο και λιγότερο από το ελάχιστο, αυτό σημαίνει ότι έχουμε προχωρήσει πάρα πολύ.

84
00:04:17,000 --> 00:04:20,000
Δεδομένου ότι ο αριθμός δεν ήταν στην διάταξη εισαγωγής, επιστρέφουμε -1

85
00:04:20,000 --> 00:04:24,000
για να δείξει ότι τίποτα δεν βρέθηκε.

86
00:04:24,000 --> 00:04:26,000
>> Μπορεί να έχετε παρατηρήσει ότι ο αλγόριθμος για να εργαστούν,

87
00:04:26,000 --> 00:04:28,000
η λίστα των αριθμών πρέπει να ταξινομηθούν.

88
00:04:28,000 --> 00:04:31,000
Με άλλα λόγια, μπορούμε να βρούμε μόνο 144 χρησιμοποιώντας δυαδική αναζήτηση

89
00:04:31,000 --> 00:04:34,000
αν όλοι οι αριθμοί που διέταξε από το χαμηλότερο στο υψηλότερο.

90
00:04:34,000 --> 00:04:38,000
Αν αυτό δεν συνέβαινε αυτό, δεν θα ήμασταν σε θέση να αποκλείσει το ήμισυ των αριθμών σε κάθε βήμα.

91
00:04:38,000 --> 00:04:40,000
Έτσι έχουμε 2 επιλογές.

92
00:04:40,000 --> 00:04:43,000
Είτε μπορούμε να πάρουμε μια λίστα και αδιαχώριστα ταξινομήσετε πριν από τη χρήση δυαδική αναζήτηση,

93
00:04:43,000 --> 00:04:48,000
ή μπορούμε να βεβαιωθείτε ότι ο κατάλογος των αριθμών ταξινομημένο ως προσθέτουμε αριθμούς σε αυτό.

94
00:04:48,000 --> 00:04:50,000
Έτσι, αντί της ταξινόμησης μόνο όταν έχουμε να αναζητήσετε,

95
00:04:50,000 --> 00:04:53,000
γιατί να μην κρατήσει τη λίστα ταξινομημένη ανά πάσα στιγμή;

96
00:04:53,000 --> 00:04:57,000
>> Ένας τρόπος για να διατηρήσετε μια λίστα με τους αριθμούς ταξινομημένο, ενώ ταυτόχρονα επιτρέπει

97
00:04:57,000 --> 00:04:59,000
κάποιον να προσθέσετε ή να μετακινήσετε τους αριθμούς από αυτήν τη λίστα

98
00:04:59,000 --> 00:05:02,000
είναι με τη χρήση κάτι που ονομάζεται ένα δυαδικό δέντρο αναζήτησης.

99
00:05:02,000 --> 00:05:05,000
Ένα δέντρο δυαδική αναζήτηση είναι μια δομή δεδομένων που έχει 3 ιδιότητες.

100
00:05:05,000 --> 00:05:09,000
Πρώτον, η αριστερή υποδένδρο κάθε κόμβος περιέχει μόνο τιμές που είναι λιγότερο από

101
00:05:09,000 --> 00:05:11,000
ή ίση με την αξία του κόμβου.

102
00:05:11,000 --> 00:05:15,000
Δεύτερον, η σωστή υποδένδρο ενός κόμβου περιέχει μόνο τιμές που είναι μεγαλύτερες από ό, τι

103
00:05:15,000 --> 00:05:17,000
ή ίση με την αξία του κόμβου.

104
00:05:17,000 --> 00:05:20,000
Και, τέλος, τόσο τα αριστερά και δεξιά υποδένδρων όλων των κόμβων

105
00:05:20,000 --> 00:05:23,000
Είναι, επίσης, δυαδικά δέντρα αναζήτησης.

106
00:05:23,000 --> 00:05:26,000
Ας δούμε ένα παράδειγμα με τους ίδιους αριθμούς που χρησιμοποιήσαμε νωρίτερα.

107
00:05:26,000 --> 00:05:30,000
Για όσους από εσάς δεν έχουν δει ποτέ ένα δέντρο της επιστήμης των υπολογιστών πριν,

108
00:05:30,000 --> 00:05:34,000
επιτρέψτε μου να ξεκινήσω λέγοντάς σας ότι ένα δέντρο επιστήμης των υπολογιστών μεγαλώνει προς τα κάτω.

109
00:05:34,000 --> 00:05:36,000
Ναι, σε αντίθεση με τα δέντρα που έχετε συνηθίσει,

110
00:05:36,000 --> 00:05:38,000
η ρίζα ενός δένδρου επιστήμης των υπολογιστών είναι στην κορυφή,

111
00:05:38,000 --> 00:05:41,000
και τα φύλλα βρίσκονται στο κάτω μέρος.

112
00:05:41,000 --> 00:05:45,000
Κάθε μικρό κουτί ονομάζεται ένας κόμβος, και οι κόμβοι συνδέονται μεταξύ τους με ακμές.

113
00:05:45,000 --> 00:05:48,000
Έτσι, η ρίζα αυτού του δέντρου είναι ένας κόμβος αξία με την τιμή 13,

114
00:05:48,000 --> 00:05:52,000
η οποία έχει 2 κόμβους παιδιά με τις τιμές 5 και 34.

115
00:05:52,000 --> 00:05:57,000
Μια υποδέντρο είναι το δέντρο που σχηματίζεται ακριβώς με την εξέταση μια υποενότητα του ολόκληρο το δέντρο.

116
00:05:57,000 --> 00:06:03,000
>> Για παράδειγμα, η αριστερή υποδένδρο του κόμβου 3 είναι το δέντρο που δημιουργήθηκε από τους κόμβους 0, 1 και 2.

117
00:06:03,000 --> 00:06:06,000
Έτσι, αν πάμε πίσω στις ιδιότητες ενός δέντρου δυαδική αναζήτηση,

118
00:06:06,000 --> 00:06:09,000
βλέπουμε ότι κάθε κόμβος στο δέντρο συμμορφώνεται με όλες τις 3 ιδιότητες, δηλαδή,

119
00:06:09,000 --> 00:06:15,000
το αριστερό υποδέντρο περιέχει μόνο τιμές που είναι μικρότερες ή ίσες με την αξία του κόμβου?

120
00:06:15,000 --> 00:06:16,000
υποδέντρο το δικαίωμα όλων των κόμβων

121
00:06:16,000 --> 00:06:19,000
περιέχει μόνο τιμές που είναι μεγαλύτερες ή ίσες με την τιμή του κόμβου? και

122
00:06:19,000 --> 00:06:25,000
τόσο αριστερά και δεξιά υποδένδρων όλων των κόμβων είναι επίσης δέντρα δυαδικής αναζήτησης.

123
00:06:25,000 --> 00:06:28,000
Αν και αυτό το δέντρο φαίνεται διαφορετικό, αυτό είναι ένα έγκυρο δένδρο δυαδική αναζήτηση

124
00:06:28,000 --> 00:06:30,000
για το ίδιο σύνολο αριθμών.

125
00:06:30,000 --> 00:06:32,000
Ως Στην πραγματικότητα, υπάρχουν πολλοί τρόποι που μπορείτε να δημιουργήσετε

126
00:06:32,000 --> 00:06:35,000
έγκυρο δέντρο δυαδικής αναζήτησης από αυτούς τους αριθμούς.

127
00:06:35,000 --> 00:06:38,000
Λοιπόν, ας πάμε πίσω στο πρώτο δημιουργήσαμε.

128
00:06:38,000 --> 00:06:40,000
Έτσι, αυτό που μπορούμε να κάνουμε με αυτά τα δέντρα;

129
00:06:40,000 --> 00:06:44,000
Λοιπόν, μπορούμε πολύ απλά να βρείτε τις ελάχιστες και μέγιστες τιμές.

130
00:06:44,000 --> 00:06:46,000
Οι ελάχιστες τιμές μπορούν να βρεθούν από πάντα θα τα αριστερά

131
00:06:46,000 --> 00:06:48,000
μέχρι να μην υπάρχουν περισσότερους κόμβους για να επισκεφθείτε.

132
00:06:48,000 --> 00:06:53,000
Αντίθετα, για να βρείτε το μέγιστο μία μόνο απλά κατεβαίνει προς τα δεξιά σε κάθε στιγμή.

133
00:06:54,000 --> 00:06:56,000
>> Η εύρεση οποιοδήποτε άλλο αριθμό που δεν είναι το ελάχιστο ή το μέγιστο

134
00:06:56,000 --> 00:06:58,000
είναι εξίσου εύκολη.

135
00:06:58,000 --> 00:07:00,000
Πείτε ψάχνουμε για τον αριθμό 89.

136
00:07:00,000 --> 00:07:03,000
Εμείς απλά ελέγξτε την αξία του κάθε κόμβου και να πάει προς τα αριστερά ή προς τα δεξιά,

137
00:07:03,000 --> 00:07:06,000
ανάλογα με το αν η αξία του κόμβου είναι μικρότερη ή μεγαλύτερη από ό, τι

138
00:07:06,000 --> 00:07:08,000
αυτός που ψάχνουμε.

139
00:07:08,000 --> 00:07:11,000
Έτσι, ξεκινώντας από τη ρίζα του 13, βλέπουμε ότι το 89 είναι μεγαλύτερο,

140
00:07:11,000 --> 00:07:13,000
και έτσι πάμε προς τα δεξιά.

141
00:07:13,000 --> 00:07:16,000
Στη συνέχεια, βλέπουμε τον κόμβο για 34, και πάλι πάμε προς τα δεξιά.

142
00:07:16,000 --> 00:07:20,000
89 είναι ακόμα μεγαλύτερη από το 55, έτσι ώστε να συνεχίζουν να πηγαίνουν προς τα δεξιά.

143
00:07:20,000 --> 00:07:24,000
Στη συνέχεια έρχονται με ένα κόμβο με την αξία του 144 και πηγαίνετε προς τα αριστερά.

144
00:07:24,000 --> 00:07:26,000
Lo και behold, 89 είναι ακριβώς εκεί.

145
00:07:26,000 --> 00:07:31,000
>> Ένα άλλο πράγμα που μπορούμε να κάνουμε είναι να εκτυπώσετε όλα τα τηλέφωνα με την εκτέλεση μιας inorder διάσχισης.

146
00:07:31,000 --> 00:07:35,000
Μια inorder διάσχιση σημαίνει να εκτυπώσετε τα πάντα στο αριστερό υποδέντρο

147
00:07:35,000 --> 00:07:37,000
ακολουθείται από τύπωση το ίδιο το κόμβο

148
00:07:37,000 --> 00:07:40,000
και στη συνέχεια ακολουθείται από τύπωση πάντα έξω στο δεξί υποδένδρο.

149
00:07:40,000 --> 00:07:43,000
Για παράδειγμα, ας πάρουμε το αγαπημένο δέντρο μας δυαδική αναζήτηση

150
00:07:43,000 --> 00:07:46,000
και να εκτυπώσετε τους αριθμούς σε ταξινομημένη σειρά.

151
00:07:46,000 --> 00:07:49,000
Ξεκινάμε από τη ρίζα του 13, αλλά πριν από την εκτύπωση 13 έχουμε να εκτυπώσετε

152
00:07:49,000 --> 00:07:51,000
πάντα στο αριστερό υποδέντρο.

153
00:07:51,000 --> 00:07:55,000
Γι 'αυτό και πάμε στο 5. Έχουμε ακόμη να πάει βαθύτερα στο δέντρο μέχρι να βρούμε την πιο αριστερή κόμβο,

154
00:07:55,000 --> 00:07:57,000
η οποία είναι μηδέν.

155
00:07:57,000 --> 00:08:00,000
Μετά την εκτύπωση μηδέν, πάμε πίσω στο 1 και να εκτυπώσετε ότι έξω.

156
00:08:00,000 --> 00:08:03,000
Στη συνέχεια, πάμε προς τα δεξιά υποδέντρο, η οποία είναι 2, και να εκτυπώσετε ότι έξω.

157
00:08:03,000 --> 00:08:05,000
Τώρα που τελειώσαμε με αυτό το υποδένδρο,

158
00:08:05,000 --> 00:08:07,000
μπορούμε να πάμε πίσω μέχρι το 3 και να το τυπώσετε έξω.

159
00:08:07,000 --> 00:08:11,000
Συνεχίζοντας να δημιουργήσετε αντίγραφα ασφαλείας, να εκτυπώσετε το 5 και στη συνέχεια το 8.

160
00:08:11,000 --> 00:08:13,000
Τώρα που έχουμε ολοκληρώσει το σύνολο αριστερά υποδένδρο,

161
00:08:13,000 --> 00:08:17,000
μπορούμε να τυπώσουμε το 13 και να αρχίσει να εργάζεται για το δικαίωμα υποδέντρο.

162
00:08:17,000 --> 00:08:21,000
Εμείς hop σε 34, αλλά πριν από την εκτύπωση 34 θα πρέπει να εκτυπώσετε το αριστερό υποδέντρο του.

163
00:08:21,000 --> 00:08:27,000
Γι 'αυτό και εκτυπώσετε 21? Τότε έχουμε την ευκαιρία να εκτυπώσετε 34 και επισκεφθείτε το δικαίωμα υποδένδρο του.

164
00:08:27,000 --> 00:08:31,000
Από 55 έχει κανένα αριστερό υποδέντρο, θα το εκτυπώσετε και να συνεχίσει προς τα δεξιά υποδέντρο του.

165
00:08:31,000 --> 00:08:36,000
144 έχει ένα αριστερό υποδέντρο, και έτσι μπορούμε να εκτυπώσετε το 89, που ακολουθείται από τα 144,

166
00:08:36,000 --> 00:08:39,000
και τέλος η πιο δεξιά κόμβο 233.

167
00:08:39,000 --> 00:08:44,000
Εκεί το έχετε? Όλοι οι αριθμοί εκτυπώνονται με τη σειρά από τη χαμηλότερη στην υψηλότερη.

168
00:08:44,000 --> 00:08:47,000
>> Η προσθήκη κάτι για το δέντρο είναι σχετικά ανώδυνη, καθώς και.

169
00:08:47,000 --> 00:08:51,000
Το μόνο που έχετε να κάνετε είναι να βεβαιωθείτε ότι ακολουθούμε 3 ακίνητα δυαδικού δένδρου αναζήτησης

170
00:08:51,000 --> 00:08:53,000
και στη συνέχεια τοποθετήστε την αξία όπου υπάρχει χώρος.

171
00:08:53,000 --> 00:08:55,000
Ας πούμε ότι θέλετε να εισάγετε την αξία του 7.

172
00:08:55,000 --> 00:08:58,000
Από το 7 είναι λιγότερο από 13, πάμε προς τα αριστερά.

173
00:08:58,000 --> 00:09:01,000
Αλλά είναι μεγαλύτερος από 5, οπότε διασχίζουν προς τα δεξιά.

174
00:09:01,000 --> 00:09:04,000
Δεδομένου ότι είναι λιγότερο από 8 και 8 είναι ένας κόμβος φύλλο, προσθέτουμε 7 στο αριστερό παιδί του 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Έχουμε προσθέσει έναν αριθμό σε δυαδικό δένδρο αναζήτησης.

176
00:09:09,000 --> 00:09:12,000
>> Αν μπορούμε να προσθέσουμε τα πράγματα, καλύτερα να είναι σε θέση να διαγράψετε τα πράγματα, όπως καλά.

177
00:09:12,000 --> 00:09:14,000
Δυστυχώς για εμάς, η διαγραφή είναι λίγο πιο περίπλοκη -

178
00:09:14,000 --> 00:09:16,000
δεν είναι πολλά, αλλά ακριβώς λίγο.

179
00:09:16,000 --> 00:09:18,000
Υπάρχουν 3 διαφορετικά σενάρια ότι πρέπει να εξετάσουμε

180
00:09:18,000 --> 00:09:21,000
κατά τη διαγραφή στοιχείων από δυαδικά δέντρα αναζήτησης.

181
00:09:21,000 --> 00:09:24,000
Πρώτον, η ευκολότερη περίπτωση είναι ότι το στοιχείο είναι ένα δικτυακό κόμβο.

182
00:09:24,000 --> 00:09:27,000
Σε αυτή την περίπτωση, θα διαγράψετε και να πάει απλά με την επιχείρησή μας.

183
00:09:27,000 --> 00:09:30,000
Πείτε μας θέλετε να διαγράψετε το 7 που μόλις προσθέσατε.

184
00:09:30,000 --> 00:09:34,000
Λοιπόν, βρίσκουμε απλά, να το αφαιρέσετε, και αυτό είναι αυτό.

185
00:09:35,000 --> 00:09:37,000
Η επόμενη περίπτωση είναι αν ο κόμβος έχει μόνο 1 παιδί.

186
00:09:37,000 --> 00:09:40,000
Εδώ μπορούμε να διαγράψετε τον κόμβο, αλλά πρέπει πρώτα να βεβαιωθείτε

187
00:09:40,000 --> 00:09:42,000
για να συνδέσετε το υποδένδρο που επαφίεται τώρα ορφανά

188
00:09:42,000 --> 00:09:44,000
στη μητρική του κόμβου που μόλις διαγράφονται.

189
00:09:44,000 --> 00:09:47,000
Πείτε μας θέλετε να διαγράψετε 3 από δέντρο μας.

190
00:09:47,000 --> 00:09:50,000
Παίρνουμε το στοιχείο παιδί του κόμβου και να το επισυνάψετε στο γονέα του κόμβου.

191
00:09:50,000 --> 00:09:54,000
Σε αυτή την περίπτωση, είμαστε προσάρτηση τώρα το 1 στο 5.

192
00:09:54,000 --> 00:09:57,000
Αυτό λειτουργεί χωρίς πρόβλημα, διότι γνωρίζουμε, σύμφωνα με τη δυαδική αναζήτηση ακινήτων δέντρο,

193
00:09:57,000 --> 00:10:01,000
ότι τα πάντα στο αριστερό υποδένδρο της 3 ήταν μικρότερο από 5.

194
00:10:01,000 --> 00:10:05,000
Τώρα που 3 του υποδέντρο έχει ληφθεί μέριμνα, μπορούμε να το διαγράψετε.

195
00:10:05,000 --> 00:10:08,000
Η τρίτη και τελευταία περίπτωση είναι η πιο πολύπλοκη.

196
00:10:08,000 --> 00:10:11,000
Αυτή είναι η περίπτωση όταν ο κόμβος που θέλουμε να έχει διαγραφεί 2 παιδιά.

197
00:10:11,000 --> 00:10:15,000
Για να γίνει αυτό, πρέπει πρώτα να βρει τον κόμβο που έχει την επόμενη μεγαλύτερη αξία,

198
00:10:15,000 --> 00:10:18,000
ανταλλάξουν τα δύο, και στη συνέχεια να διαγράψετε τον κόμβο στην ερώτηση.

199
00:10:18,000 --> 00:10:22,000
Παρατηρήστε τον κόμβο που έχει η αμέσως μεγαλύτερη τιμή δεν μπορεί να έχει το ίδιο 2 παιδιά

200
00:10:22,000 --> 00:10:26,000
από το αριστερό παιδί του θα ήταν η καλύτερη υποψήφια για το επόμενο μεγαλύτερο.

201
00:10:26,000 --> 00:10:30,000
Ως εκ τούτου, η διαγραφή ενός κόμβου με 2 παιδιά ανέρχεται σε εναλλαγή των 2 κόμβων,

202
00:10:30,000 --> 00:10:33,000
και στη συνέχεια διαγραφή γίνεται από 1 από τα 2 παραπάνω κανόνες.

203
00:10:33,000 --> 00:10:37,000
Για παράδειγμα, ας πούμε ότι θέλετε να διαγράψετε τον κόμβο ρίζα, 13.

204
00:10:37,000 --> 00:10:39,000
Το πρώτο πράγμα που κάνουμε είναι να βρούμε την επόμενη μεγαλύτερη αξία στο δέντρο

205
00:10:39,000 --> 00:10:41,000
το οποίο, σε αυτή την περίπτωση, είναι 21.

206
00:10:41,000 --> 00:10:46,000
Θα ανταλλάξουν τα 2 κόμβους, κάνοντας φύλλο 13 α και 21 ο κεντρικός κόμβος της ομάδας.

207
00:10:46,000 --> 00:10:49,000
Τώρα μπορούμε απλά να διαγράψετε 13.

208
00:10:50,000 --> 00:10:53,000
>> Όπως αναφέρθηκε προηγουμένως, υπάρχουν πολλοί πιθανοί τρόποι για να κάνετε μια έγκυρη δέντρο δυαδική αναζήτηση.

209
00:10:53,000 --> 00:10:56,000
Δυστυχώς για μας, μερικά είναι χειρότερα από ό, τι άλλες.

210
00:10:56,000 --> 00:10:59,000
Για παράδειγμα, τι συμβαίνει όταν χτίζουμε ένα δυαδικό δέντρο αναζήτησης

211
00:10:59,000 --> 00:11:01,000
από μια ταξινομημένη λίστα των αριθμών;

212
00:11:01,000 --> 00:11:04,000
Όλοι οι αριθμοί απλώς προστίθεται στο δικαίωμα σε κάθε βήμα.

213
00:11:04,000 --> 00:11:06,000
Όταν θέλουμε να αναζητήσετε έναν αριθμό,

214
00:11:06,000 --> 00:11:08,000
δεν έχουμε άλλη επιλογή παρά μόνο να κοιτάξουμε το δικαίωμα σε κάθε βήμα.

215
00:11:08,000 --> 00:11:11,000
Αυτό δεν είναι καλύτερη από γραμμική αναζήτηση σε όλα.

216
00:11:11,000 --> 00:11:13,000
Παρά το γεγονός ότι εμείς δεν θα τους καλύψει εδώ, υπάρχουν και άλλες, πιο σύνθετες,

217
00:11:13,000 --> 00:11:16,000
δομές δεδομένων που να βεβαιωθείτε ότι αυτό δεν θα συμβεί.

218
00:11:16,000 --> 00:11:18,000
Ωστόσο, ένα απλό πράγμα που μπορεί να γίνει για να αποφευχθεί αυτό είναι

219
00:11:18,000 --> 00:11:21,000
απλά να ανακατέψετε τυχαία τις τιμές εισόδου.

220
00:11:21,000 --> 00:11:26,000
Είναι εξαιρετικά απίθανο ότι με τυχαία μια ευκαιρία ανακατεύονται λίστα των αριθμών είναι ταξινομημένο.

221
00:11:26,000 --> 00:11:29,000
Αν συνέβαινε αυτό, οι χαρτοπαικτικές λέσχες δεν θα μείνουν στην επιχείρηση για μεγάλο χρονικό διάστημα.

222
00:11:29,000 --> 00:11:31,000
>> Εκεί το έχετε.

223
00:11:31,000 --> 00:11:34,000
Ξέρετε τώρα για δυαδική αναζήτηση και δέντρα δυαδικής αναζήτησης.

224
00:11:34,000 --> 00:11:36,000
Είμαι Patrick Schmid, και αυτό είναι CS50.

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
Ένας προφανής τρόπος θα ήταν να σαρώσει τη λίστα από ... [μπιπ]

227
00:11:43,000 --> 00:11:46,000
... Ο αριθμός των αντικειμένων ... yep

228
00:11:46,000 --> 00:11:50,000
[Γέλια]

229
00:11:50,000 --> 00:11:55,000
Κόμβο ... μετά από 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Αυτό ήταν -