1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Recherche binaire]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Université de Harvard]

3
00:00:04,000 --> 00:00:07,000
[C'est CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Si je vous ai donné une liste de noms de personnages Disney dans l'ordre alphabétique

5
00:00:09,000 --> 00:00:11,000
et vous a demandé de trouver Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
comment feriez-vous pour cela?

7
00:00:13,000 --> 00:00:15,000
Une façon évidente serait de parcourir la liste depuis le début

8
00:00:15,000 --> 00:00:18,000
et vérifier chaque nom pour voir si c'est Mickey.

9
00:00:18,000 --> 00:00:22,000
Mais pendant que vous lisez Aladdin, Alice, Ariel, et ainsi de suite,

10
00:00:22,000 --> 00:00:25,000
vous vous rendrez vite compte que le démarrage sur le devant de la liste n'était pas une bonne idée.

11
00:00:25,000 --> 00:00:29,000
Ok, peut-être vous devriez commencer à travailler à rebours à partir de la fin de la liste.

12
00:00:29,000 --> 00:00:33,000
Maintenant que vous lisez Tarzan, Stitch, Blanche-Neige, et ainsi de suite.

13
00:00:33,000 --> 00:00:36,000
Pourtant, cela ne semble pas être la meilleure façon de s'y prendre.

14
00:00:36,000 --> 00:00:38,000
>> Eh bien, une autre façon que vous pourriez prendre pour ce faire est d'essayer d'affiner

15
00:00:38,000 --> 00:00:41,000
la liste des noms que vous avez à regarder.

16
00:00:41,000 --> 00:00:43,000
Puisque vous savez qu'ils sont dans l'ordre alphabétique,

17
00:00:43,000 --> 00:00:45,000
vous pouvez simplement regarder les noms dans le milieu de la liste

18
00:00:45,000 --> 00:00:49,000
et vérifier si Mickey Mouse est avant ou après ce nom.

19
00:00:49,000 --> 00:00:51,000
En regardant le nom de famille dans la deuxième colonne

20
00:00:51,000 --> 00:00:54,000
vous rendre compte que M pour Mickey vient après J pour Jasmine,

21
00:00:54,000 --> 00:00:57,000
si vous souhaitez tout simplement ignorer la première moitié de la liste.

22
00:00:57,000 --> 00:00:59,000
Ensuite, vous auriez probablement regarder le haut de la dernière colonne

23
00:00:59,000 --> 00:01:02,000
et de voir qu'il commence par Raiponce.

24
00:01:02,000 --> 00:01:06,000
Mickey vient avant Rapunzel, dirait qu'on ne peut ignorer la dernière colonne ainsi.

25
00:01:06,000 --> 00:01:08,000
Poursuite de la stratégie de recherche, vous verrez rapidement que Mickey

26
00:01:08,000 --> 00:01:11,000
est dans la première moitié de la liste restante de noms

27
00:01:11,000 --> 00:01:14,000
et enfin trouver Mickey caché entre Merlin et Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Ce que vous venez de faire est essentiellement binaire de recherche.

29
00:01:17,000 --> 00:01:22,000
Comme ce nom l'indique, il effectue sa stratégie de recherche en quelques binaire.

30
00:01:22,000 --> 00:01:24,000
Qu'est-ce que cela signifie?

31
00:01:24,000 --> 00:01:27,000
Eh bien, étant donné une liste d'éléments triés, l'algorithme de recherche binaire prend une décision binaire -

32
00:01:27,000 --> 00:01:33,000
à gauche ou à droite, supérieure ou inférieure, avant ou après alphabétique - à chaque point.

33
00:01:33,000 --> 00:01:35,000
Maintenant que nous avons un nom qui va de pair avec cet algorithme de recherche,

34
00:01:35,000 --> 00:01:38,000
Voyons un autre exemple, mais cette fois avec une liste de numéros triés.

35
00:01:38,000 --> 00:01:43,000
Disons que nous sommes à la recherche pour le numéro 144 dans la liste des numéros triés.

36
00:01:43,000 --> 00:01:46,000
Tout comme avant, nous trouvons que le nombre est au milieu -

37
00:01:46,000 --> 00:01:50,000
qui dans ce cas est de 13 - 144 et voir si est supérieur ou inférieur à 13.

38
00:01:50,000 --> 00:01:54,000
Comme il est clairement supérieur à 13, on peut ignorer tout ce qui est 13 ou moins

39
00:01:54,000 --> 00:01:57,000
et se concentrer uniquement sur la moitié restante.

40
00:01:57,000 --> 00:01:59,000
Puisque nous avons maintenant un nombre pair d'éléments à gauche,

41
00:01:59,000 --> 00:02:01,000
nous avons simplement choisir un numéro qui est proche de la moyenne.

42
00:02:01,000 --> 00:02:03,000
Dans ce cas, nous choisissons 55.

43
00:02:03,000 --> 00:02:06,000
Nous aurions pu tout aussi bien choisi 89.

44
00:02:06,000 --> 00:02:11,000
D'accord. Encore une fois, 144 est supérieur à 55, alors nous allons vers la droite.

45
00:02:11,000 --> 00:02:14,000
Heureusement pour nous, le nombre du milieu prochaine est de 144,

46
00:02:14,000 --> 00:02:16,000
celui que nous recherchons.

47
00:02:16,000 --> 00:02:21,000
Ainsi, afin de trouver 144 en utilisant une recherche binaire, nous sommes en mesure de le trouver en seulement 3 étapes.

48
00:02:21,000 --> 00:02:24,000
Si nous avions utilisé la recherche linéaire ici, il nous aurait fallu 12 étapes.

49
00:02:24,000 --> 00:02:28,000
En effet, depuis cette méthode de recherche de moitié le nombre d'éléments

50
00:02:28,000 --> 00:02:31,000
il doit regarder à chaque étape, il va trouver l'élément qu'il est à la recherche

51
00:02:31,000 --> 00:02:35,000
dans environ le logarithme du nombre d'éléments dans la liste.

52
00:02:35,000 --> 00:02:37,000
Maintenant que nous avons vu 2 exemples, nous allons jeter un coup d'oeil à

53
00:02:37,000 --> 00:02:41,000
certains pseudo-code pour une fonction récursive qui implémente recherche binaire.

54
00:02:41,000 --> 00:02:44,000
En partant du haut, nous voyons que nous devons trouver une fonction qui prend 4 arguments:

55
00:02:44,000 --> 00:02:47,000
clé, tableau, min et max.

56
00:02:47,000 --> 00:02:51,000
La clé, c'est le nombre que nous sommes à la recherche d', donc 144 dans l'exemple précédent.

57
00:02:51,000 --> 00:02:54,000
Array est la liste des numéros que nous recherchons.

58
00:02:54,000 --> 00:02:57,000
Min et max sont les indices des positions minimum et maximum

59
00:02:57,000 --> 00:02:59,000
que nous étudions actuellement.

60
00:02:59,000 --> 00:03:03,000
Alors, quand nous commençons, min sera de zéro et max sera l'indice maximum de la matrice.

61
00:03:03,000 --> 00:03:07,000
Comme nous l'limiter la recherche, nous mettrons à jour min et max

62
00:03:07,000 --> 00:03:10,000
pour être juste la gamme que nous sommes toujours à la recherche po

63
00:03:10,000 --> 00:03:12,000
>> Passons à la partie intéressante premier.

64
00:03:12,000 --> 00:03:14,000
La première chose à faire est de trouver le point milieu,

65
00:03:14,000 --> 00:03:19,000
l'indice qui est à mi-chemin entre le mini et maxi du tableau que nous envisageons toujours.

66
00:03:19,000 --> 00:03:22,000
Ensuite, nous examinons la valeur du tableau à cet endroit mi-parcours

67
00:03:22,000 --> 00:03:25,000
et voir si le nombre que nous sommes à la recherche d'est inférieure à cette clé.

68
00:03:25,000 --> 00:03:27,000
Si le nombre est à cette position inférieure,

69
00:03:27,000 --> 00:03:31,000
alors cela signifie que la clé est plus grand que tous les nombres à gauche de cette position.

70
00:03:31,000 --> 00:03:33,000
Ainsi, nous pouvons appeler la fonction de recherche binaire à nouveau,

71
00:03:33,000 --> 00:03:36,000
mais cette fois la mise à jour des valeurs minimum et maximum des paramètres de lire que la moitié

72
00:03:36,000 --> 00:03:40,000
qui est supérieure ou égale à la valeur que nous venons d'examiner.

73
00:03:40,000 --> 00:03:44,000
D'autre part, si la clé est inférieur au nombre courant au milieu de la matrice,

74
00:03:44,000 --> 00:03:47,000
nous voulons aller vers la gauche et ignorer tous les nombres supérieurs.

75
00:03:47,000 --> 00:03:52,000
Encore une fois, nous appelons binaire de recherche, mais cette fois avec la gamme des valeurs min et max à jour

76
00:03:52,000 --> 00:03:54,000
pour inclure juste la moitié inférieure.

77
00:03:54,000 --> 00:03:57,000
Si la valeur à mi-chemin de courant dans le réseau n'est pas

78
00:03:57,000 --> 00:04:01,000
supérieur ni inférieur à la clé, il doit être égal à la clé.

79
00:04:01,000 --> 00:04:05,000
Ainsi, nous pouvons simplement retourner l'indice milieu actuel, et nous avons fini.

80
00:04:05,000 --> 00:04:09,000
Enfin, ce contrôle est ici dans le cas où le nombre

81
00:04:09,000 --> 00:04:11,000
n'est pas réellement dans le tableau de nombres, nous sommes à la recherche.

82
00:04:11,000 --> 00:04:14,000
Si l'indice maximum de la plage que nous sommes à la recherche d'

83
00:04:14,000 --> 00:04:17,000
est toujours inférieur au minimum, ce qui signifie que nous sommes allés trop loin.

84
00:04:17,000 --> 00:04:20,000
Comme le nombre n'était pas dans le tableau d'entrée, nous renvoient -1

85
00:04:20,000 --> 00:04:24,000
pour indiquer que rien n'a été trouvé.

86
00:04:24,000 --> 00:04:26,000
>> Vous avez peut être remarqué que pour cet algorithme au travail,

87
00:04:26,000 --> 00:04:28,000
la liste des numéros doit être trié.

88
00:04:28,000 --> 00:04:31,000
En d'autres termes, on ne peut que trouver 144 en utilisant la recherche binaire

89
00:04:31,000 --> 00:04:34,000
si tous les nombres sont triés du plus bas au plus élevé.

90
00:04:34,000 --> 00:04:38,000
Si ce n'était pas le cas, nous ne serions pas en mesure d'exclure la moitié des numéros à chaque étape.

91
00:04:38,000 --> 00:04:40,000
Nous avons donc 2 options.

92
00:04:40,000 --> 00:04:43,000
Soit on peut prendre une liste non triée et trier avant en utilisant la recherche binaire,

93
00:04:43,000 --> 00:04:48,000
ou nous pouvons faire en sorte que la liste des numéros est triée comme nous ajouter des numéros à elle.

94
00:04:48,000 --> 00:04:50,000
Ainsi, au lieu de trier juste au moment où nous devons rechercher,

95
00:04:50,000 --> 00:04:53,000
pourquoi ne pas garder la liste triée en tout temps?

96
00:04:53,000 --> 00:04:57,000
>> Une façon de garder une liste de numéros triés tout en permettant

97
00:04:57,000 --> 00:04:59,000
un pour ajouter ou déplacer des numéros de cette liste

98
00:04:59,000 --> 00:05:02,000
est d'utiliser ce qu'on appelle un arbre binaire de recherche.

99
00:05:02,000 --> 00:05:05,000
Un arbre binaire de recherche est une structure de données qui possède 3 propriétés.

100
00:05:05,000 --> 00:05:09,000
En premier lieu, le sous-arbre gauche du noeud contient aucune seules valeurs qui sont inférieures à

101
00:05:09,000 --> 00:05:11,000
ou égale à la valeur du nœud.

102
00:05:11,000 --> 00:05:15,000
Deuxièmement, le sous-arbre droit d'un noeud ne contient que des valeurs qui sont supérieures à

103
00:05:15,000 --> 00:05:17,000
ou égale à la valeur du nœud.

104
00:05:17,000 --> 00:05:20,000
Et, enfin, les deux sous-arbres gauche et droit de tous les nœuds

105
00:05:20,000 --> 00:05:23,000
sont aussi des arbres binaires de recherche.

106
00:05:23,000 --> 00:05:26,000
Regardons un exemple avec les mêmes numéros que nous avons utilisés précédemment.

107
00:05:26,000 --> 00:05:30,000
Pour ceux d'entre vous qui n'ont jamais vu un arbre en informatique avant,

108
00:05:30,000 --> 00:05:34,000
permettez-moi de commencer par vous dire qu'un arbre pousse vers le bas de l'informatique.

109
00:05:34,000 --> 00:05:36,000
Oui, contrairement aux arbres vous êtes habitués,

110
00:05:36,000 --> 00:05:38,000
la racine d'un arbre de l'informatique est au sommet,

111
00:05:38,000 --> 00:05:41,000
et les feuilles sont en bas.

112
00:05:41,000 --> 00:05:45,000
Chaque petite boîte est appelée un nœud et les noeuds sont reliés les uns aux autres par des arêtes.

113
00:05:45,000 --> 00:05:48,000
Ainsi, la racine de cet arbre est une valeur de nœud avec la valeur 13,

114
00:05:48,000 --> 00:05:52,000
qui a 2 nœuds enfants avec les valeurs 5 et 34.

115
00:05:52,000 --> 00:05:57,000
Un sous-arbre est l'arbre qui est formé juste en regardant une sous-section de l'arbre entier.

116
00:05:57,000 --> 00:06:03,000
>> Par exemple, le sous-arbre gauche du noeud 3 est l'arbre créé par les noeuds 0, 1, et 2.

117
00:06:03,000 --> 00:06:06,000
Donc, si nous revenons aux propriétés d'un arbre binaire de recherche,

118
00:06:06,000 --> 00:06:09,000
nous voyons que chaque nœud de l'arbre est conforme à toutes les 3 propriétés, à savoir,

119
00:06:09,000 --> 00:06:15,000
la sous-arborescence de gauche ne contient que des valeurs qui sont inférieures ou égales à la valeur du noeud;

120
00:06:15,000 --> 00:06:16,000
le sous-arbre droit de tous les nœuds

121
00:06:16,000 --> 00:06:19,000
ne contient que des valeurs qui sont supérieures ou égales à la valeur du noeud, et

122
00:06:19,000 --> 00:06:25,000
sous-arbres gauche et droit de tous les nœuds sont aussi des arbres binaires de recherche.

123
00:06:25,000 --> 00:06:28,000
Bien que cet arbre est différent, c'est un arbre binaire de recherche valide

124
00:06:28,000 --> 00:06:30,000
pour le même ensemble de nombres.

125
00:06:30,000 --> 00:06:32,000
En fait, il existe de nombreuses façons que vous pouvez créer

126
00:06:32,000 --> 00:06:35,000
un arbre binaire de recherche valable à partir de ces chiffres.

127
00:06:35,000 --> 00:06:38,000
Eh bien, revenons à la première que nous avons créé.

128
00:06:38,000 --> 00:06:40,000
Alors, que pouvons-nous faire avec ces arbres?

129
00:06:40,000 --> 00:06:44,000
Eh bien, nous pouvons très simplement trouver les valeurs minimales et maximales.

130
00:06:44,000 --> 00:06:46,000
Les valeurs minimales peuvent être trouvés en va toujours vers la gauche

131
00:06:46,000 --> 00:06:48,000
jusqu'à ce qu'il n'y pas d'autres nœuds à visiter.

132
00:06:48,000 --> 00:06:53,000
A l'inverse, pour trouver le maximum tout simplement descend vers la droite à chaque fois.

133
00:06:54,000 --> 00:06:56,000
>> Trouver tout autre numéro qui n'est pas le minimum ou le maximum

134
00:06:56,000 --> 00:06:58,000
est tout aussi facile.

135
00:06:58,000 --> 00:07:00,000
Dire que nous sommes à la recherche pour le nombre 89.

136
00:07:00,000 --> 00:07:03,000
Nous avons simplement vérifier la valeur de chaque nœud et allez vers la gauche ou vers la droite,

137
00:07:03,000 --> 00:07:06,000
selon que la valeur du noeud est inférieur ou supérieur à

138
00:07:06,000 --> 00:07:08,000
celui que nous recherchons.

139
00:07:08,000 --> 00:07:11,000
Donc, à partir de la racine de 13, nous voyons que 89 est plus grand,

140
00:07:11,000 --> 00:07:13,000
et si nous allons vers la droite.

141
00:07:13,000 --> 00:07:16,000
Ensuite, nous voyons le nœud 34, et encore une fois nous allons à droite.

142
00:07:16,000 --> 00:07:20,000
89 est toujours supérieur à 55, donc nous continuons à aller vers la droite.

143
00:07:20,000 --> 00:07:24,000
Nous avons ensuite mis au point un nœud avec la valeur de 144 et allez vers la gauche.

144
00:07:24,000 --> 00:07:26,000
Et voilà, 89 est juste là.

145
00:07:26,000 --> 00:07:31,000
>> Une autre chose que nous pouvons faire est d'imprimer tous les numéros en effectuant un parcours infixe.

146
00:07:31,000 --> 00:07:35,000
Un parcours infixe signifie tout imprimer dans le sous-arbre gauche

147
00:07:35,000 --> 00:07:37,000
suivie de l'impression elle-même le noeud

148
00:07:37,000 --> 00:07:40,000
puis suivie par une impression tout dans le sous-arbre droit.

149
00:07:40,000 --> 00:07:43,000
Par exemple, prenons notre arbre binaire de recherche favori

150
00:07:43,000 --> 00:07:46,000
et imprimer les numéros dans l'ordre.

151
00:07:46,000 --> 00:07:49,000
Nous commençons à la racine de 13, mais avant l'impression 13, nous devons imprimer

152
00:07:49,000 --> 00:07:51,000
tout dans le sous-arbre gauche.

153
00:07:51,000 --> 00:07:55,000
Donc, nous allons à 5. Nous devons encore aller plus loin dans l'arbre jusqu'à ce qu'on trouve le nœud le plus à gauche,

154
00:07:55,000 --> 00:07:57,000
qui est égale à zéro.

155
00:07:57,000 --> 00:08:00,000
Après l'impression de zéro, nous remontons à la 1 et imprimer cela.

156
00:08:00,000 --> 00:08:03,000
Puis nous allons à la sous-arbre droit, qui est 2, et imprimer cela.

157
00:08:03,000 --> 00:08:05,000
Maintenant que nous avons terminé avec ce sous-arbre,

158
00:08:05,000 --> 00:08:07,000
nous pouvons revenir à la 3 et l'imprimer.

159
00:08:07,000 --> 00:08:11,000
Poursuivant back up, nous imprimons le 5 puis le 8.

160
00:08:11,000 --> 00:08:13,000
Maintenant que nous avons terminé l'ensemble du sous-arbre gauche,

161
00:08:13,000 --> 00:08:17,000
nous pouvons imprimer le 13 et commencer à travailler sur le sous-arbre droit.

162
00:08:17,000 --> 00:08:21,000
Nous sautons jusqu'au 34, mais avant impression 34, nous devons imprimer son sous-arbre gauche.

163
00:08:21,000 --> 00:08:27,000
Donc, nous imprimons 21; puis nous arrivons à imprimer 34 et visiter son sous-arbre droit.

164
00:08:27,000 --> 00:08:31,000
Comme 55 n'a pas de sous-arbre gauche, nous l'imprimer et de continuer sur son sous-arbre droit.

165
00:08:31,000 --> 00:08:36,000
144 comporte un sous-arbre gauche, et ainsi nous imprimons le 89, suivi du 144,

166
00:08:36,000 --> 00:08:39,000
et enfin le nœud le plus à droite de la 233.

167
00:08:39,000 --> 00:08:44,000
Il vous en avez, tous les nombres sont imprimées dans l'ordre du plus bas au plus élevé.

168
00:08:44,000 --> 00:08:47,000
>> Ajouter quelque chose à l'arbre est relativement indolore ainsi.

169
00:08:47,000 --> 00:08:51,000
Tout ce que nous avons à faire est de s'assurer que nous suivons 3 propriétés binaires de recherche arborescente

170
00:08:51,000 --> 00:08:53,000
puis insérez la valeur là où il ya de l'espace.

171
00:08:53,000 --> 00:08:55,000
Disons que nous voulons insérer la valeur de 7.

172
00:08:55,000 --> 00:08:58,000
Depuis le 7 est inférieur à 13, on va vers la gauche.

173
00:08:58,000 --> 00:09:01,000
Mais elle est supérieure à 5, donc nous traversons vers la droite.

174
00:09:01,000 --> 00:09:04,000
Comme il est inférieur à 8 et 8 est un noeud feuille, on ajoute 7 à la gauche de l'enfant 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Nous avons ajouté un certain nombre à notre arbre binaire de recherche.

176
00:09:09,000 --> 00:09:12,000
>> Si nous pouvons ajouter des choses, nous ferions mieux en mesure de supprimer les choses ainsi.

177
00:09:12,000 --> 00:09:14,000
Malheureusement pour nous, la suppression est un peu plus compliqué -

178
00:09:14,000 --> 00:09:16,000
pas beaucoup, mais juste un peu.

179
00:09:16,000 --> 00:09:18,000
Il ya 3 différents scénarios que nous avons à examiner

180
00:09:18,000 --> 00:09:21,000
lors de la suppression d'éléments d'arbres binaires de recherche.

181
00:09:21,000 --> 00:09:24,000
Tout d'abord, le cas le plus simple est que l'élément est un nœud feuille.

182
00:09:24,000 --> 00:09:27,000
Dans ce cas, il suffit de le supprimer et continuer avec notre entreprise.

183
00:09:27,000 --> 00:09:30,000
Disons que nous voulons supprimer le 7 que nous venons d'ajouter.

184
00:09:30,000 --> 00:09:34,000
Eh bien, il suffit de le trouver, retirez-le et c'est tout.

185
00:09:35,000 --> 00:09:37,000
Le cas suivant est de savoir si le nœud a seulement 1 enfant.

186
00:09:37,000 --> 00:09:40,000
Ici, nous pouvons supprimer le noeud, mais nous devons d'abord assurez-vous

187
00:09:40,000 --> 00:09:42,000
pour relier le sous-arbre qui est maintenant laissé orphelin

188
00:09:42,000 --> 00:09:44,000
pour le parent du nœud que nous venons supprimé.

189
00:09:44,000 --> 00:09:47,000
Disons que nous voulons supprimer 3 de notre arbre.

190
00:09:47,000 --> 00:09:50,000
Nous prenons l'élément enfant de ce noeud et le fixer au parent du noeud.

191
00:09:50,000 --> 00:09:54,000
Dans ce cas, nous sommes en train de fixer la 1 à la 5.

192
00:09:54,000 --> 00:09:57,000
Cela fonctionne sans problème parce que nous savons, d'après la propriété d'arbre binaire de recherche,

193
00:09:57,000 --> 00:10:01,000
que tout, dans le sous-arbre gauche du 3 étant inférieur à 5.

194
00:10:01,000 --> 00:10:05,000
Maintenant que 3 sous-arbre est pris en charge, on peut le supprimer.

195
00:10:05,000 --> 00:10:08,000
Le troisième et dernier cas est le plus complexe.

196
00:10:08,000 --> 00:10:11,000
C'est le cas lorsque le nœud que nous voulons supprimer a 2 enfants.

197
00:10:11,000 --> 00:10:15,000
Pour ce faire, nous devons d'abord trouver le nœud qui possède la plus grande valeur suivante,

198
00:10:15,000 --> 00:10:18,000
permuter les deux, puis supprimez le nœud en question.

199
00:10:18,000 --> 00:10:22,000
Notez que le nœud qui possède la plus grande valeur suivante ne peut pas avoir 2 enfants se

200
00:10:22,000 --> 00:10:26,000
depuis son enfant de gauche serait un meilleur candidat pour le plus grand côté.

201
00:10:26,000 --> 00:10:30,000
Par conséquent, la suppression d'un nœud avec 2 enfants revient à la permutation de 2 nœuds,

202
00:10:30,000 --> 00:10:33,000
et en supprimant ensuite est traité par 1 des 2 règles précitées.

203
00:10:33,000 --> 00:10:37,000
Par exemple, disons que nous voulons supprimer le nœud racine, 13.

204
00:10:37,000 --> 00:10:39,000
La première chose à faire est de nous trouver la plus grande valeur suivant dans l'arborescence

205
00:10:39,000 --> 00:10:41,000
qui, dans ce cas, est de 21.

206
00:10:41,000 --> 00:10:46,000
Nous avons ensuite permuter les 2 noeuds, soit 13 et 21 une feuille le nœud du groupe central.

207
00:10:46,000 --> 00:10:49,000
Maintenant, nous pouvons simplement supprimer 13.

208
00:10:50,000 --> 00:10:53,000
>> Comme mentionné précédemment, il existe de nombreuses façons de faire un arbre binaire de recherche valide.

209
00:10:53,000 --> 00:10:56,000
Malheureusement pour nous, certains sont pires que d'autres.

210
00:10:56,000 --> 00:10:59,000
Par exemple, qu'est-ce qui se passe quand on construit un arbre binaire de recherche

211
00:10:59,000 --> 00:11:01,000
à partir d'une liste triée des chiffres?

212
00:11:01,000 --> 00:11:04,000
Tous les numéros sont simplement ajoutés à la droite à chaque étape.

213
00:11:04,000 --> 00:11:06,000
Quand nous voulons rechercher un numéro,

214
00:11:06,000 --> 00:11:08,000
nous n'avons pas le choix, mais seulement à regarder à droite à chaque étape.

215
00:11:08,000 --> 00:11:11,000
Ce n'est pas mieux que la recherche linéaire du tout.

216
00:11:11,000 --> 00:11:13,000
Bien que nous ne les couvrir ici, il existe d'autres, plus complexes,

217
00:11:13,000 --> 00:11:16,000
des structures de données qui font en sorte que cela n'arrive pas.

218
00:11:16,000 --> 00:11:18,000
Cependant, une chose simple qui peut être fait pour éviter cela est

219
00:11:18,000 --> 00:11:21,000
simplement modifier aléatoirement les valeurs d'entrée.

220
00:11:21,000 --> 00:11:26,000
Il est hautement improbable que par hasard une liste de numéros mélangées sont triées.

221
00:11:26,000 --> 00:11:29,000
Si tel était le cas, les casinos ne voulait pas rester en affaires longtemps.

222
00:11:29,000 --> 00:11:31,000
>> Il vous en avez.

223
00:11:31,000 --> 00:11:34,000
Vous savez maintenant sur la recherche binaire et les arbres binaires de recherche.

224
00:11:34,000 --> 00:11:36,000
Je suis Patrick Schmid, et c'est CS50.

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

226
00:11:38,000 --> 00:11:43,000
Une façon évidente serait d'examiner la liste de ... [bip]

227
00:11:43,000 --> 00:11:46,000
... Le nombre d'articles ... yep

228
00:11:46,000 --> 00:11:50,000
[Rires]

229
00:11:50,000 --> 00:11:55,000
... Poster nœud de 234 ... Augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! C'était -