[Powered by Google Translate] Comment voulez-vous représenter tous les membres de votre famille dans un ordinateur?
Nous pourrions simplement utiliser une liste,
mais il ya une hiérarchie claire ici.
>> Disons que nous sommes en commençant par votre grand-mère, Alice.
Elle a 2 fils, Bob
et votre grand-père, Charlie.
Charlie a 3 enfants,
votre oncle, Dave, votre tante, la veille, et votre père, Fred.
Vous êtes seul enfant de Fred.
>> Pourquoi organiser vos membres de la famille de cette manière
être mieux que la représentation de liste simple?
Une des raisons est que cette structure hiérarchique,
appelé «arbre», contient plus d'informations qu'une simple liste.
Nous savons que les relations familiales entre tous
juste en examinant l'arbre.
En outre, il peut accélérer
look-up énormément de temps, si les données sont triées arbres.
>> Nous ne pouvons pas profiter de cela ici, mais nous allons voir un exemple de cette sous peu.
Chaque personne est représentée par un noeud de l'arbre.
Les nœuds peuvent avoir des noeuds enfants
ainsi que d'un noeud parent.
Ce sont les termes techniques,
même lors de l'utilisation des arbres pour les familles choses en plus.
Nœud d'Alice a 2 enfants et pas de parents,
alors que le noeud de Charlie a 3 enfants et 1 parent.
>> Un nœud feuille est celui qui n'a pas eu d'enfants
sur le bord extérieur de l'arbre.
Le noeud le plus haut de l'arbre, le noeud racine,
n'a pas de parent.
>> Un arbre binaire est un type spécifique d'arbre,
dans lequel chaque noeud comporte, en plus, 2 enfants.
Voici la structure d'un nœud d'un arbre binaire en C.
Chaque nœud dispose de certaines données qui lui sont associées
et 2 pointeurs vers d'autres nœuds.
>> Dans notre arbre généalogique,
les données associées était le nom de chaque personne.
Ici, il est un int, mais il pourrait être n'importe quoi.
Comme il s'avère,
un arbre binaire ne serait pas une bonne représentation de la famille,
puisque les gens ont souvent plus de 2 enfants.
>> Un arbre binaire de recherche
est un spécial, de type arbre binaire ordonné de
qui nous permet de regarder rapidement les valeurs.
Vous avez sans doute remarqué
que chaque noeud en dessous de la racine d'un arbre
est la racine d'un autre arbre, appelé «sous-arbre.
Ici, la racine de l'arbre est 6,
et son enfant, 2, est la racine d'un sous-arbre.
>> Dans un arbre binaire de recherche
toutes les valeurs d'un sous-arbre droit du noeud
sont supérieurs à la valeur du noeud. Ici: 6.
Eh bien, les valeurs sous-arbre gauche d'un nœud
est inférieure à la valeur du noeud.
Si nous avons besoin pour gérer les valeurs en double,
nous pouvons changer l'un de ceux à une inégalité lâche,
ce qui signifie des valeurs identiques peuvent tomber soit sur la gauche ou la droite,
aussi longtemps que nous sommes conformes à ce sujet tout au long.
Cet arbre est un arbre binaire de recherche
parce qu'il suit ces règles.
>> C'est à quoi il ressemblerait si nous avons tourné tous les nœuds en structures C.
Notez que si un enfant est porté disparu,
le pointeur est nul.
Comment peut-on vérifier pour voir si 7 est dans l'arbre?
Nous commençons à la racine.
Sept est supérieur à 6, donc si c'est dans l'arbre, il doit se trouver à droite.
Ensuite, il est inférieur à 8, donc il doit être laissé.
Ici, nous avons trouvé 7.
Maintenant, nous allons vérifier pour 5.
Cinq est inférieur à 6, il doit donc être à la gauche.
Cinq est supérieur à 2,
donc il doit être droit,
et il est également supérieur à 4, il doit donc être de nouveau à droite.
Cependant, il n'ya pas d'enfant ici.
Le pointeur est nul.
Cela signifie que 5 n'est pas dans notre arbre.
>> Nous pouvons chercher l'arbre binaire avec le code suivant:
A chaque nœud, nous vérifions pour voir si nous avons trouvé
la valeur que nous recherchons.
Si nous ne le trouvez pas, nous déterminer si elle doit être
et sur la gauche ou la droite vérifiez que sous-arborescence.
Cette boucle se poursuivra dans l'arbre
jusqu'à ce qu'il n'y nœud enfant soit sur la gauche ou la droite.
>> Rappelez-vous que 5 n'était pas dans l'arborescence.
Comment peut-on l'insérer?
Le processus est similaire à la recherche.
Nous itérer bas de l'arbre à partir de 6,
de gauche à 2,
droit à 4,
et encore à droite, mais 4 n'a pas d'enfant de ce côté.
Ce sera la nouvelle position 5,
et il va commencer sans enfants.
>> À quelle vitesse les opérations sur un arbre binaire de recherche?
Rappelez-vous que Bigohnotation vise à fournir une limite supérieure.
Dans le pire des cas,
notre arbre pourrait être simplement une liste chaînée
ce qui signifie que l'insertion, la suppression et la recherche
peut prendre un temps proportionnel au nombre de noeuds dans l'arborescence.
Ceci est O (n).
>> Par exemple, ce qui suit est un arbre binaire de recherche valide.
Cependant, si nous essayons de trouver 9,
nous devons parcourir chaque nœud.
Il n'est pas meilleur que d'une liste chaînée.
Idéalement, nous voudrions que chaque nœud
de notre arbre binaire de recherche d'avoir 2 enfants.
De cette façon, l'insertion, la suppression et la recherche
faudrait, au pire, O (log n).
L'arbre d'avant pourrait être plus équilibré,
comme celui-ci.
Maintenant, en regardant n'importe quelle valeur prend, au plus, 3 étapes.
Cet arbre est équilibré,
sens qui a une profondeur minimale
par rapport au nombre de noeuds.
>> Vous cherchez une valeur dans un arbre binaire de recherche équilibré
est similaire à la recherche binaire sur un tableau trié.
En fait, si nous n'avons pas besoin d'insérer ou de supprimer des éléments,
ils se comportent exactement de la même manière.
Cependant, une structure arborescente vaut mieux
des insertions et des suppressions de manutention
>> Mon nom est Bannus Van der Kloot.
C'est CS50.