1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Comment voulez-vous représenter tous les membres de votre famille dans un ordinateur?

2
00:00:10,790 --> 00:00:12,390
Nous pourrions simplement utiliser une liste,

3
00:00:12,390 --> 00:00:14,400
mais il ya une hiérarchie claire ici.

4
00:00:14,400 --> 00:00:17,110
>> Disons que nous sommes en commençant par votre grand-mère, Alice.

5
00:00:17,110 --> 00:00:19,030
Elle a 2 fils, Bob

6
00:00:19,030 --> 00:00:21,310
et votre grand-père, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie a 3 enfants,

8
00:00:23,190 --> 00:00:26,730
votre oncle, Dave, votre tante, la veille, et votre père, Fred.

9
00:00:26,730 --> 00:00:28,750
Vous êtes seul enfant de Fred.

10
00:00:28,750 --> 00:00:30,950
>> Pourquoi organiser vos membres de la famille de cette manière

11
00:00:30,950 --> 00:00:34,010
être mieux que la représentation de liste simple?

12
00:00:34,010 --> 00:00:36,630
Une des raisons est que cette structure hiérarchique,

13
00:00:36,630 --> 00:00:39,660
appelé «arbre», contient plus d'informations qu'une simple liste.

14
00:00:40,540 --> 00:00:43,520
Nous savons que les relations familiales entre tous

15
00:00:43,520 --> 00:00:45,440
juste en examinant l'arbre.

16
00:00:45,440 --> 00:00:47,250
En outre, il peut accélérer

17
00:00:47,250 --> 00:00:50,010
look-up énormément de temps, si les données sont triées arbres.

18
00:00:50,010 --> 00:00:53,850
>> Nous ne pouvons pas profiter de cela ici, mais nous allons voir un exemple de cette sous peu.

19
00:00:53,850 --> 00:00:56,150
Chaque personne est représentée par un noeud de l'arbre.

20
00:00:56,680 --> 00:00:58,370
Les nœuds peuvent avoir des noeuds enfants

21
00:00:58,370 --> 00:01:00,350
ainsi que d'un noeud parent.

22
00:01:00,350 --> 00:01:02,390
Ce sont les termes techniques,

23
00:01:02,390 --> 00:01:05,220
même lors de l'utilisation des arbres pour les familles choses en plus.

24
00:01:05,220 --> 00:01:07,940
Nœud d'Alice a 2 enfants et pas de parents,

25
00:01:07,940 --> 00:01:11,500
alors que le noeud de Charlie a 3 enfants et 1 parent.

26
00:01:11,500 --> 00:01:14,330
>> Un nœud feuille est celui qui n'a pas eu d'enfants

27
00:01:14,330 --> 00:01:16,410
sur le bord extérieur de l'arbre.

28
00:01:16,410 --> 00:01:18,520
Le noeud le plus haut de l'arbre, le noeud racine,

29
00:01:18,520 --> 00:01:20,240
n'a pas de parent.

30
00:01:20,240 --> 00:01:23,170
>> Un arbre binaire est un type spécifique d'arbre,

31
00:01:23,170 --> 00:01:26,720
dans lequel chaque noeud comporte, en plus, 2 enfants.

32
00:01:26,720 --> 00:01:30,490
Voici la structure d'un nœud d'un arbre binaire en C.

33
00:01:31,560 --> 00:01:34,530
Chaque nœud dispose de certaines données qui lui sont associées

34
00:01:34,530 --> 00:01:36,520
et 2 pointeurs vers d'autres nœuds.

35
00:01:36,520 --> 00:01:38,110
>> Dans notre arbre généalogique,

36
00:01:38,110 --> 00:01:40,900
les données associées était le nom de chaque personne.

37
00:01:40,900 --> 00:01:43,850
Ici, il est un int, mais il pourrait être n'importe quoi.

38
00:01:44,510 --> 00:01:46,200
Comme il s'avère,

39
00:01:46,200 --> 00:01:48,990
un arbre binaire ne serait pas une bonne représentation de la famille,

40
00:01:48,990 --> 00:01:51,960
puisque les gens ont souvent plus de 2 enfants.

41
00:01:51,960 --> 00:01:53,510
>> Un arbre binaire de recherche

42
00:01:53,510 --> 00:01:56,380
est un spécial, de type arbre binaire ordonné de

43
00:01:56,380 --> 00:01:58,090
qui nous permet de regarder rapidement les valeurs.

44
00:01:58,740 --> 00:02:00,050
Vous avez sans doute remarqué

45
00:02:00,050 --> 00:02:02,010
que chaque noeud en dessous de la racine d'un arbre

46
00:02:02,010 --> 00:02:04,620
est la racine d'un autre arbre, appelé «sous-arbre.

47
00:02:04,960 --> 00:02:07,090
Ici, la racine de l'arbre est 6,

48
00:02:07,090 --> 00:02:09,860
et son enfant, 2, est la racine d'un sous-arbre.

49
00:02:09,860 --> 00:02:11,870
>> Dans un arbre binaire de recherche

50
00:02:11,870 --> 00:02:15,790
toutes les valeurs d'un sous-arbre droit du noeud

51
00:02:15,790 --> 00:02:18,690
sont supérieurs à la valeur du noeud. Ici: 6.

52
00:02:18,690 --> 00:02:22,640
Eh bien, les valeurs sous-arbre gauche d'un nœud

53
00:02:24,540 --> 00:02:26,890
est inférieure à la valeur du noeud.

54
00:02:26,890 --> 00:02:28,620
Si nous avons besoin pour gérer les valeurs en double,

55
00:02:28,620 --> 00:02:31,760
nous pouvons changer l'un de ceux à une inégalité lâche,

56
00:02:31,760 --> 00:02:34,410
ce qui signifie des valeurs identiques peuvent tomber soit sur la gauche ou la droite,

57
00:02:34,410 --> 00:02:37,400
aussi longtemps que nous sommes conformes à ce sujet tout au long.

58
00:02:37,400 --> 00:02:39,620
Cet arbre est un arbre binaire de recherche

59
00:02:39,620 --> 00:02:41,540
parce qu'il suit ces règles.

60
00:02:42,320 --> 00:02:46,020
>> C'est à quoi il ressemblerait si nous avons tourné tous les nœuds en structures C.

61
00:02:46,880 --> 00:02:48,410
Notez que si un enfant est porté disparu,

62
00:02:48,410 --> 00:02:50,340
le pointeur est nul.

63
00:02:50,340 --> 00:02:53,270
Comment peut-on vérifier pour voir si 7 est dans l'arbre?

64
00:02:53,270 --> 00:02:55,020
Nous commençons à la racine.

65
00:02:55,020 --> 00:02:58,690
Sept est supérieur à 6, donc si c'est dans l'arbre, il doit se trouver à droite.

66
00:02:59,680 --> 00:03:03,650
Ensuite, il est inférieur à 8, donc il doit être laissé.

67
00:03:03,650 --> 00:03:06,210
Ici, nous avons trouvé 7.

68
00:03:06,210 --> 00:03:08,160
Maintenant, nous allons vérifier pour 5.

69
00:03:08,160 --> 00:03:11,500
Cinq est inférieur à 6, il doit donc être à la gauche.

70
00:03:11,500 --> 00:03:13,460
Cinq est supérieur à 2,

71
00:03:13,460 --> 00:03:15,010
donc il doit être droit,

72
00:03:15,010 --> 00:03:18,100
et il est également supérieur à 4, il doit donc être de nouveau à droite.

73
00:03:18,100 --> 00:03:20,300
Cependant, il n'ya pas d'enfant ici.

74
00:03:20,300 --> 00:03:22,000
Le pointeur est nul.

75
00:03:22,000 --> 00:03:24,270
Cela signifie que 5 n'est pas dans notre arbre.

76
00:03:24,270 --> 00:03:27,250
>> Nous pouvons chercher l'arbre binaire avec le code suivant:

77
00:03:28,430 --> 00:03:31,140
A chaque nœud, nous vérifions pour voir si nous avons trouvé

78
00:03:31,140 --> 00:03:33,020
la valeur que nous recherchons.

79
00:03:33,020 --> 00:03:35,740
Si nous ne le trouvez pas, nous déterminer si elle doit être

80
00:03:35,740 --> 00:03:38,990
et sur la gauche ou la droite vérifiez que sous-arborescence.

81
00:03:38,990 --> 00:03:41,160
Cette boucle se poursuivra dans l'arbre

82
00:03:41,160 --> 00:03:44,190
jusqu'à ce qu'il n'y nœud enfant soit sur la gauche ou la droite.

83
00:03:45,190 --> 00:03:48,600
>> Rappelez-vous que 5 n'était pas dans l'arborescence.

84
00:03:48,600 --> 00:03:50,460
Comment peut-on l'insérer?

85
00:03:50,460 --> 00:03:52,370
Le processus est similaire à la recherche.

86
00:03:52,370 --> 00:03:54,830
Nous itérer bas de l'arbre à partir de 6,

87
00:03:54,830 --> 00:03:57,040
de gauche à 2,

88
00:03:57,040 --> 00:03:59,140
droit à 4,

89
00:03:59,140 --> 00:04:02,500
et encore à droite, mais 4 n'a pas d'enfant de ce côté.

90
00:04:02,500 --> 00:04:06,090
Ce sera la nouvelle position 5,

91
00:04:06,090 --> 00:04:08,500
et il va commencer sans enfants.

92
00:04:09,020 --> 00:04:12,220
>> À quelle vitesse les opérations sur un arbre binaire de recherche?

93
00:04:12,220 --> 00:04:15,410
Rappelez-vous que Bigohnotation vise à fournir une limite supérieure.

94
00:04:15,410 --> 00:04:17,390
Dans le pire des cas,

95
00:04:17,390 --> 00:04:19,480
notre arbre pourrait être simplement une liste chaînée

96
00:04:19,480 --> 00:04:22,220
ce qui signifie que l'insertion, la suppression et la recherche

97
00:04:22,220 --> 00:04:25,380
peut prendre un temps proportionnel au nombre de noeuds dans l'arborescence.

98
00:04:25,380 --> 00:04:27,380
Ceci est O (n).

99
00:04:27,380 --> 00:04:30,690
>> Par exemple, ce qui suit est un arbre binaire de recherche valide.

100
00:04:31,850 --> 00:04:34,020
Cependant, si nous essayons de trouver 9,

101
00:04:34,020 --> 00:04:36,760
nous devons parcourir chaque nœud.

102
00:04:36,760 --> 00:04:39,120
Il n'est pas meilleur que d'une liste chaînée.

103
00:04:39,120 --> 00:04:41,410
Idéalement, nous voudrions que chaque nœud

104
00:04:41,410 --> 00:04:44,120
de notre arbre binaire de recherche d'avoir 2 enfants.

105
00:04:44,120 --> 00:04:46,370
De cette façon, l'insertion, la suppression et la recherche

106
00:04:46,370 --> 00:04:50,190
faudrait, au pire, O (log n).

107
00:04:50,190 --> 00:04:52,470
L'arbre d'avant pourrait être plus équilibré,

108
00:04:52,470 --> 00:04:54,140
comme celui-ci.

109
00:04:54,140 --> 00:04:57,980
Maintenant, en regardant n'importe quelle valeur prend, au plus, 3 étapes.

110
00:04:57,980 --> 00:04:59,460
Cet arbre est équilibré,

111
00:04:59,460 --> 00:05:01,190
sens qui a une profondeur minimale

112
00:05:01,190 --> 00:05:03,680
par rapport au nombre de noeuds.

113
00:05:03,680 --> 00:05:06,300
>> Vous cherchez une valeur dans un arbre binaire de recherche équilibré

114
00:05:06,300 --> 00:05:09,540
est similaire à la recherche binaire sur un tableau trié.

115
00:05:09,540 --> 00:05:12,290
En fait, si nous n'avons pas besoin d'insérer ou de supprimer des éléments,

116
00:05:12,290 --> 00:05:15,150
ils se comportent exactement de la même manière.

117
00:05:15,150 --> 00:05:17,600
Cependant, une structure arborescente vaut mieux

118
00:05:17,600 --> 00:05:19,530
des insertions et des suppressions de manutention

119
00:05:20,360 --> 00:05:22,670
>> Mon nom est Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
C'est CS50.