Arbre binaire de recherche, impressions

Bonjour/Bonsoir individus de toute ethnie et sexe confondus.

Je suis en train d'apprendre de ma propre initiative quand et comment utiliser les structures de données ainsi que leur inconvénients et avantages.
Les liste chainées, les tableaux et les structures c'est fait (j'ignore si ce dernier est vraiment une structure de donnée cela dit ou si c'est inhérent à certains langages, comme le C).

Je pense un jour avoir l'utilité d'un arbre binaire de recherche.
J'ai quelques interrogations à propos de cette structure de donnée cependant.
J'ai lu ce tutoriel.

1) Est ce une convention (inter)nationale de construire un ABR de la sorte :
http://rperrot.developpez.com/articl..._recherche.jpg

Ou simplement arbitrairement choisie par l'auteur du tutoriel ?
Ou encore en vigueur uniquement dans les pays où lit de gauche à droite ?

2) Arrêtez moi si je me trompe mais idéalement la racine doit avoir la valeur intermédiaire, mais cela implique aussi que l'on connaisse plus ou moins les données qui entreront dans l'arbre.
A moins que l'on soit plus ou moins obligé de redéfinir la racine à chaque ajout/suppression de nœud ?
Mais dans ce cas se pose définitivement la question du temps de l'ajout/suppression d'un nœud, même si un arbre de recherche ne se soucie pas de cela comme son nom l'indique.

Citation:

---

Envoyé par AnozerOne

1) Est ce une convention (inter)nationale de construire un ABR de la sorte :

---

Il n'y a aucunement de convention pour la construction d'un arbre de recherche. Que tu mettes les plus grandes feuilles à gauche ou à droite, peu importe du moment que tu en tiens compte lors de la recherche. La seule convention qui prévaudra, est celle que tu as décidé d'implémenter. L'auteur à utiliser ce sens par soucis de compréhension.

Citation:

---

Envoyé par AnozerOne

2) Arrêtez moi si je me trompe mais idéalement la racine doit avoir la valeur intermédiaire

---

Idéalement oui, pour profiter pleinement du principe de dichotomie. Mais dans la pratique tu prends généralement pour racine, la première valeur à insérer dans l'arbre. Ton arbre sera surement déséquilibré, mais je ne pense pas que ce soit significatif en temps de parcours lors de la recherche d'un neud.

Citation:

---

Envoyé par AnozerOne

A moins que l'on soit plus ou moins obligé de redéfinir la racine à chaque ajout/suppression de nœud ?.

---

Redéfinir la racine à chaque insertion paraît très très compliqué à mettre en oeuvre pour le peu d'avantage que ça pourrait apporter.

En espérant avoir pu aider.

Une catégorie d'arbres binaires de recherche s'appelle les arbres de recherche équilibrés (ou AVL).

Le principe consiste à maintenir en permanence un arbre quasi-équilibré, c'est-à-dire que pour chaque sous-arbre, le nombre de nœuds à gauche est égale au nombre de nœuds à droite (à plus ou moins 1 près).

L'avantage est de cette approche est que la hauteur de l'arbre est petite (logarithmique en le nombre de sommets) ce qui est le critère important dans la recherche d'un élément puisque la complexité de celle-ci est linéaire en la hauteur.

Donc à chaque insertion et suppression d'un élément, on va rééquilibrer l'arbre (et changer sa racine éventuellement) mais sans que ce cout ne soit très important (encore logarithmique en le nombre de sommets).

Pour plus de détails, tu peux aller voir ce cours par exemple:
http://www.enseignement.polytechniqu...in4/node8.html

Merci à vous deux.

@nonifier : C'est limpide.

@Biribibi : Hélas les liens d'images du cours que tu as donné en lien ne semblent pas valides, ce qui ne rend pas la lecture très agréable.
Toutefois grâce a ce mot clef que tu m'as appris, j'ai pu trouver ceci :
http://fr.wikipedia.org/wiki/Arbre_%C3%A9quilibr%C3%A9

Citation:

---

Dans un arbre AVL, la hauteur du SAG et celle du SAD diffèrent au plus de un. Le nombre de réorganisations maximum est en O(log N), c'est-à-dire la hauteur de l'arbre. L'insertion, la recherche et la suppression sont en O(log N).

---

Erf, donc si on a pas de chance on doit réorganiser l'arbre en entier, j'avoue que ca me refroidit.

Existe t'il un autre type d'arbre binaire avec peut être moins de performance pour la recherche d'un élément, mais avec un ajout/suppression d'élément moins couteux ?
Bref un meilleur compromis entre temps de recherche et gestion de la structure de l'arbre.

Salut,

non, tu n'as jamais besoin de réorganiser l'arbre en entier.
Comme je disais, c'est de l'ordre de log(n) éléments (par exemple 10 éléments pour un arbre à 1000 sommets, 20 éléments pour un arbre à 1 million de sommets) et cela dans le pire des cas.
Les AVL font partie des structures avec le meilleur compromis recherche/modification.
Il existe aussi les arbres rouge/noir basés un peu sur le même principe (maintenir un arbre équilibré) et donc la complexité des opérations est la même (à un facteur près). Je crois qu'ils sont plus efficaces en pratique mais à vérifier.
http://fr.wikipedia.org/wiki/Arbre_bicolore

Citation de Wikipédia (même si ce n'est pas forcement une source très fiable.

Citation:

---

Les arbres bicolores, ainsi que les arbres AVL, offrent la meilleure garantie sur le temps d'insertion, de suppression et de recherche dans les cas défavorables.

---

Sinon, tu peux regarder du coté des tables de hash qui sont basés sur un tout autre concept.
http://fr.wikipedia.org/wiki/Table_de_hachage

Autant pour moi, j'avais mal lu la phrase que j'ai cité.
J'ai déjà en effet vu plusieurs fois cité ces "arbres rouges", il faudrait que je me renseigne plus à ce sujet.

Au sujet de wikipedia je sais qu'il ne faut pas prendre cela pour argent comptant, et privilégier les documents avec des sources référencées, mais j'ai un vague souvenir comme quoi il y aurait moins d'erreur ou équivalence entre une encyclopédie classique que l'on peut acheter.
Cela se tient car potentiellement c'est le monde entier qui peut lire n'importe quel sujet et corriger les erreurs éventuelles.

Donc à priori plus l'article est "vieux", plus il est fiable, à l'inverse d'une encyclopédie papier ou bien évidemment l'erreur perdurera, mais d'un autre côté il y a peu de chances qu'une erreur soit produite.
Et wikipedia reste à la traine par rapport à des encyclopédies minutieuses.

Je vais regarder de plus prés les tables de hachage, et je suis aussi totalement ouvert à toute autre structure de donnée.

Wikipédia anglais est relativement fiable je trouve (du moins, pour les articles scientifiques) mais la version française l'est beaucoup moins.

:faq:

C'est le bouton "FAQ ALGO" en haut dans la barre de menu.

Même si la FAQ est relativement complète elle ne répond pas néanmoins à mes questions précises.
Ce qui n'est de toute façon pas le but d'une FAQ.