1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Πώς θα εκπροσωπεί όλα τα μέλη της οικογένειάς σας σε έναν υπολογιστή;

2
00:00:10,790 --> 00:00:12,390
Θα μπορούσαμε να χρησιμοποιήσουμε απλά μια λίστα,

3
00:00:12,390 --> 00:00:14,400
αλλά υπάρχει μια σαφής ιεραρχία εδώ.

4
00:00:14,400 --> 00:00:17,110
>> Ας πούμε ότι αρχίζουμε με προγιαγιά σας, Alice.

5
00:00:17,110 --> 00:00:19,030
Έχει 2 γιους, ο Bob

6
00:00:19,030 --> 00:00:21,310
και ο παππούς σου, Τσάρλι.

7
00:00:21,310 --> 00:00:23,190
Τσάρλι έχει 3 παιδιά,

8
00:00:23,190 --> 00:00:26,730
Ο θείος σας, ο Dave, η θεία σου, η Εύα, και ο πατέρας σας, ο Φρεντ.

9
00:00:26,730 --> 00:00:28,750
Είστε μόνο παιδί του Fred.

10
00:00:28,750 --> 00:00:30,950
>> Γιατί θα οργάνωση τα μέλη της οικογένειας σας με αυτόν τον τρόπο

11
00:00:30,950 --> 00:00:34,010
να είναι καλύτερη από την απλή αναπαράσταση λίστα;

12
00:00:34,010 --> 00:00:36,630
Ένας λόγος είναι ότι αυτή η ιεραρχική δομή,

13
00:00:36,630 --> 00:00:39,660
που ονομάζεται «δέντρο», περιέχει περισσότερες πληροφορίες από ό, τι μια απλή λίστα.

14
00:00:40,540 --> 00:00:43,520
Γνωρίζουμε τις οικογενειακές σχέσεις μεταξύ όλων

15
00:00:43,520 --> 00:00:45,440
ακριβώς με την εξέταση το δέντρο.

16
00:00:45,440 --> 00:00:47,250
Επίσης, αυτό μπορεί να επιταχύνει

17
00:00:47,250 --> 00:00:50,010
look-up χρόνο παρά πολύ, αν τα δεδομένα είναι ταξινομημένο δέντρο.

18
00:00:50,010 --> 00:00:53,850
>> Δεν μπορούν να επωφεληθούν από αυτό εδώ, αλλά θα δούμε ένα παράδειγμα αυτό σύντομα.

19
00:00:53,850 --> 00:00:56,150
Κάθε άτομο αντιπροσωπεύεται από έναν κόμβο στο δέντρο.

20
00:00:56,680 --> 00:00:58,370
Οι κόμβοι μπορούν να έχουν το παιδί τους κόμβους

21
00:00:58,370 --> 00:01:00,350
καθώς και ένα μητρικό κόμβο.

22
00:01:00,350 --> 00:01:02,390
Αυτοί είναι οι τεχνικοί όροι,

23
00:01:02,390 --> 00:01:05,220
ακόμη και όταν χρησιμοποιούν τα δέντρα για πράγματα εκτός από τις οικογένειες.

24
00:01:05,220 --> 00:01:07,940
Κόμβο της Alice έχει 2 παιδιά και δεν τους γονείς,

25
00:01:07,940 --> 00:01:11,500
ενώ κόμβο του Τσάρλι έχει 3 παιδιά και 1 γονέα.

26
00:01:11,500 --> 00:01:14,330
>> Ένας κόμβος είναι ένα φύλλο που δεν έχει οποιαδήποτε παιδιά

27
00:01:14,330 --> 00:01:16,410
στην εξωτερική άκρη του δένδρου.

28
00:01:16,410 --> 00:01:18,520
Το κορυφαίο κόμβο του δέντρου, ο κόμβος ρίζα,

29
00:01:18,520 --> 00:01:20,240
δεν έχει γονέα.

30
00:01:20,240 --> 00:01:23,170
>> Ένα δέντρο δυαδικό είναι ένα συγκεκριμένο είδος δέντρου,

31
00:01:23,170 --> 00:01:26,720
στο οποίο κάθε κόμβος έχει, στην καλύτερη περίπτωση, 2 παιδιά.

32
00:01:26,720 --> 00:01:30,490
Εδώ είναι η struct ενός κόμβου ενός δυαδικού δέντρου στο C.

33
00:01:31,560 --> 00:01:34,530
Κάθε κόμβος έχει κάποια δεδομένα που σχετίζονται με το

34
00:01:34,530 --> 00:01:36,520
και 2 δείκτες σε άλλους κόμβους.

35
00:01:36,520 --> 00:01:38,110
>> Στο οικογενειακό μας δέντρο,

36
00:01:38,110 --> 00:01:40,900
τα δεδομένα που σχετίζονται ήταν το όνομα του κάθε ατόμου.

37
00:01:40,900 --> 00:01:43,850
Εδώ είναι ένα int, αν και θα μπορούσε να είναι οτιδήποτε.

38
00:01:44,510 --> 00:01:46,200
Όπως αποδεικνύεται,

39
00:01:46,200 --> 00:01:48,990
ένα δυαδικό δέντρο δεν θα ήταν μια καλή παράσταση για μια οικογένεια,

40
00:01:48,990 --> 00:01:51,960
δεδομένου ότι οι άνθρωποι έχουν συχνά περισσότερα από 2 παιδιά.

41
00:01:51,960 --> 00:01:53,510
>> Ένα δέντρο δυαδική αναζήτηση

42
00:01:53,510 --> 00:01:56,380
είναι μια ειδική, διέταξε τον τύπο του δυαδικού δένδρου

43
00:01:56,380 --> 00:01:58,090
που μας επιτρέπει να δούμε τις τιμές γρήγορα.

44
00:01:58,740 --> 00:02:00,050
Μπορεί να έχετε παρατηρήσει

45
00:02:00,050 --> 00:02:02,010
ότι κάθε κόμβος κάτω από τη ρίζα ενός δέντρου

46
00:02:02,010 --> 00:02:04,620
είναι η ρίζα του δέντρου άλλο, που ονομάζεται «υποδέντρο.

47
00:02:04,960 --> 00:02:07,090
Εδώ, η ρίζα του δέντρου είναι 6,

48
00:02:07,090 --> 00:02:09,860
και το παιδί της, 2, είναι η ρίζα του υποδέντρου.

49
00:02:09,860 --> 00:02:11,870
>> Σε ένα δυαδικό δέντρο αναζήτησης

50
00:02:11,870 --> 00:02:15,790
όλες οι τιμές ενός κόμβου είναι σωστό υποδέντρο

51
00:02:15,790 --> 00:02:18,690
είναι μεγαλύτερη από την αξία του κόμβου. Εδώ: 6.

52
00:02:18,690 --> 00:02:22,640
Λοιπόν, οι τιμές στο αριστερό υποδέντρο ενός κόμβου

53
00:02:24,540 --> 00:02:26,890
είναι λιγότερο από την αξία του κόμβου.

54
00:02:26,890 --> 00:02:28,620
Αν πρέπει να χειριστεί διπλές τιμές,

55
00:02:28,620 --> 00:02:31,760
μπορούμε να αλλάξουμε είτε από αυτούς σε ένα χαλαρό ανισότητα,

56
00:02:31,760 --> 00:02:34,410
σημαίνει ίδιες τιμές μπορεί να πέσει είτε στην αριστερή ή δεξιά,

57
00:02:34,410 --> 00:02:37,400
όσο είμαστε συνεπείς για την όλη διαδικασία.

58
00:02:37,400 --> 00:02:39,620
Αυτό το δέντρο είναι ένα δυαδικό δέντρο αναζήτησης

59
00:02:39,620 --> 00:02:41,540
επειδή ακολουθεί αυτούς τους κανόνες.

60
00:02:42,320 --> 00:02:46,020
>> Αυτό είναι το πώς θα φαινόταν αν γυρίσαμε όλους τους κόμβους σε C structs.

61
00:02:46,880 --> 00:02:48,410
Παρατηρήστε ότι αν ένα παιδί λείπει,

62
00:02:48,410 --> 00:02:50,340
ο δείκτης είναι μηδενική.

63
00:02:50,340 --> 00:02:53,270
Πώς να ελέγξετε αν 7 είναι στο δέντρο;

64
00:02:53,270 --> 00:02:55,020
Ξεκινάμε από τη ρίζα.

65
00:02:55,020 --> 00:02:58,690
Επτά είναι μεγαλύτερος από 6, οπότε αν είναι στο δέντρο, θα πρέπει να είναι προς τα δεξιά.

66
00:02:59,680 --> 00:03:03,650
Στη συνέχεια, είναι μικρότερο από 8, και έτσι πρέπει να μείνει.

67
00:03:03,650 --> 00:03:06,210
Εδώ, έχουμε βρει 7.

68
00:03:06,210 --> 00:03:08,160
Τώρα, θα ελέγξουμε για 5.

69
00:03:08,160 --> 00:03:11,500
Πέντε είναι μικρότερο από 6, έτσι ώστε να πρέπει να είναι προς τα αριστερά.

70
00:03:11,500 --> 00:03:13,460
Πέντε είναι μεγαλύτερο από 2,

71
00:03:13,460 --> 00:03:15,010
γι 'αυτό πρέπει να είναι σωστό,

72
00:03:15,010 --> 00:03:18,100
και είναι επίσης μεγαλύτερος από 4, οπότε πρέπει να είναι σωστό και πάλι.

73
00:03:18,100 --> 00:03:20,300
Ωστόσο, δεν υπάρχει κανένα παιδί εδώ.

74
00:03:20,300 --> 00:03:22,000
Ο δείκτης είναι μηδενική.

75
00:03:22,000 --> 00:03:24,270
Αυτό σημαίνει ότι δεν είναι 5 στο δέντρο μας.

76
00:03:24,270 --> 00:03:27,250
>> Μπορούμε να αναζητήσετε το δυαδικό δέντρο με τον ακόλουθο κώδικα:

77
00:03:28,430 --> 00:03:31,140
Σε κάθε κόμβο, ελέγχουμε να δούμε αν έχουμε βρει

78
00:03:31,140 --> 00:03:33,020
η τιμή που ψάχνουμε.

79
00:03:33,020 --> 00:03:35,740
Αν δεν το βρείτε, θα καθορίσει εάν θα πρέπει να είναι

80
00:03:35,740 --> 00:03:38,990
αριστερά ή προς τα δεξιά και ελέγξτε ότι υποδένδρο.

81
00:03:38,990 --> 00:03:41,160
Αυτός ο βρόχος θα συνεχίσει κάτω από το δέντρο

82
00:03:41,160 --> 00:03:44,190
έως ότου δεν υπάρχει κόμβος παιδί είτε στην αριστερή ή δεξιά.

83
00:03:45,190 --> 00:03:48,600
>> Να θυμάστε ότι το 5 δεν ήταν στο δέντρο.

84
00:03:48,600 --> 00:03:50,460
Πώς μπορούμε να το τοποθετήσετε;

85
00:03:50,460 --> 00:03:52,370
Η διαδικασία μοιάζει με την αναζήτηση.

86
00:03:52,370 --> 00:03:54,830
Έχουμε επαναλάβει κάτω από το δέντρο αρχίζει από 6,

87
00:03:54,830 --> 00:03:57,040
αριστερά προς 2,

88
00:03:57,040 --> 00:03:59,140
δικαίωμα 4,

89
00:03:59,140 --> 00:04:02,500
και πάλι δεξιά, αλλά το 4 δεν έχει παιδί σε αυτή την πλευρά.

90
00:04:02,500 --> 00:04:06,090
Αυτή θα είναι η νέα θέση για 5,

91
00:04:06,090 --> 00:04:08,500
και θα αρχίσει χωρίς παιδιά.

92
00:04:09,020 --> 00:04:12,220
>> Πόσο γρήγορα είναι οι λειτουργίες σε ένα δυαδικό δέντρο αναζήτησης;

93
00:04:12,220 --> 00:04:15,410
Να θυμάστε ότι Bigohnotation επιδιώκει να παρέχει ένα άνω όριο.

94
00:04:15,410 --> 00:04:17,390
Στη χειρότερη περίπτωση,

95
00:04:17,390 --> 00:04:19,480
δέντρο μας θα μπορούσε απλά να είναι μια συνδεδεμένη λίστα

96
00:04:19,480 --> 00:04:22,220
πράγμα που σημαίνει ότι η εισαγωγή, διαγραφή, και αναζήτηση

97
00:04:22,220 --> 00:04:25,380
θα μπορούσε να πάρει το χρόνο ανάλογα με τον αριθμό των κόμβων στο δέντρο.

98
00:04:25,380 --> 00:04:27,380
Αυτό είναι O (n).

99
00:04:27,380 --> 00:04:30,690
>> Για παράδειγμα, η ακόλουθη είναι μια έγκυρη δένδρο δυαδική αναζήτηση.

100
00:04:31,850 --> 00:04:34,020
Ωστόσο, αν προσπαθήσουμε να βρούμε 9,

101
00:04:34,020 --> 00:04:36,760
έχουμε να διασχίσουν κάθε κόμβο.

102
00:04:36,760 --> 00:04:39,120
Δεν είναι καλύτερη από μια συνδεδεμένη λίστα.

103
00:04:39,120 --> 00:04:41,410
Ιδανικά, θα θέλαμε σε κάθε κόμβο

104
00:04:41,410 --> 00:04:44,120
του δέντρου δυαδική αναζήτηση μας να έχουν 2 παιδιά.

105
00:04:44,120 --> 00:04:46,370
Με αυτό τον τρόπο, εισαγωγή, διαγραφή και αναζήτηση

106
00:04:46,370 --> 00:04:50,190
θα λάβει, στη χειρότερη περίπτωση, O (log n) χρόνο.

107
00:04:50,190 --> 00:04:52,470
Το δέντρο από πριν θα μπορούσε να είναι πιο ισορροπημένη,

108
00:04:52,470 --> 00:04:54,140
όπως αυτό.

109
00:04:54,140 --> 00:04:57,980
Τώρα, κοιτώντας ψηλά οποιαδήποτε αξία έχει, το πολύ, 3 βήματα.

110
00:04:57,980 --> 00:04:59,460
Αυτό το δέντρο είναι ισορροπημένη,

111
00:04:59,460 --> 00:05:01,190
έννοια που έχει ένα ελάχιστο βάθος

112
00:05:01,190 --> 00:05:03,680
σε σχέση με τον αριθμό των κόμβων.

113
00:05:03,680 --> 00:05:06,300
>> Ψάχνετε για μια τιμή σε ένα ισορροπημένο δέντρο δυαδική αναζήτηση

114
00:05:06,300 --> 00:05:09,540
είναι παρόμοια με δυαδική αναζήτηση σε ταξινομημένο πίνακα.

115
00:05:09,540 --> 00:05:12,290
Στην πραγματικότητα, αν δεν χρειάζεται να εισάγετε ή να διαγράψετε τα στοιχεία,

116
00:05:12,290 --> 00:05:15,150
συμπεριφέρονται ακριβώς με τον ίδιο τρόπο.

117
00:05:15,150 --> 00:05:17,600
Ωστόσο, μια δομή δέντρου είναι καλύτερη

118
00:05:17,600 --> 00:05:19,530
για ενθέσεις χειρισμού και διαγραφές

119
00:05:20,360 --> 00:05:22,670
>> Το όνομά μου είναι Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Αυτό είναι CS50.