Discussion :

[hbx360]

Bonsoir, je souhaiterai savoir si pour construire un arbre binaire de recherche il faut obligatoirement passé par des liste doublement chainé ou des structures.

Ou est-ce que l'on peut tous simplement passer par un tableau d'entier par exemple ou l'on permuterait les valeur du tableau.

Merci par avance

[Obsidian]

En effet, un arbre de recherche binaire est un concept abstrait et tu peux donc choisir l'implémentation qui te sied le mieux, pourvu que tu puisses certifier qu'elle en respecte bien les règles.

À titre indicatif, il y a un peu plus de quinze ans, j'en avais implémenté un sur la calculatrice d'un étudiant en chimie, à qui on avait donné (comme à ses camarades) un arbre de décision sur papier, avec des branches « oui » ou « non ». La calculatrice en question était une Casio 7700 doté d'un Basic rudimentaire qui ne pouvait exécuter qu'une seule instruction à la suite d'une condition (ce qui, d'un point de vue algorithmique et automatismes, était un défi intéressant). Il m'a suffi d'initialiser une variable à 1, puis de faire une boucle sans fin dans laquelle je multipliais cette variable par 2, puis ajoutait la réponse de l'utilisateur, soit 0 pour non et 1 pour oui. Chaque nœud disposait alors d'un numéro unique propre.

Il suffisait ensuite d'associer chaque valeur avec un « echo » qui affichait soit la question suivante, soit la décision finale à prendre si on avait atteint une feuille.

[hbx360]

Ah oui assez impressionnant merci pour ta réponse ; donc si je veut créer un arbre binaire en passant par un tableau d'entier uniquement en permutant les différentes valeurs c'est possible si j'ai bien compris. Je précise pour plus de clarté construire un arbre binaire de recherche pour moi ces cette figure là :

.............7
.........../....\
.........4.......8
......../...........\
......3.............10
...../..\.........../
...2....4........9
../
1
..\
...2

[picodev]

Bonjour,

Qu'entends par «par un tableau d'entier uniquement en permutant les différentes valeurs» ?

Si par là tu entends utiliser un tableau de structures avec la propriété que fils_gauche(i)=2*i et fils_droit(i)=2*i+1, avec racine=1 et l'élément de rang 0 jouant le rôle d'un pointeur NULL, alors la réponse est oui.

Un tableau d'entiers uniquement ne pourra pas suffire à moins de disposer d'une valeur «interdite» signifiant qu'un nœud est non occupé. Sinon il te faudra passer par un tableau de structures.
Attention au gaspillage dans les cas d'ABR fortement dégénérés (réduits à une liste).

[hbx360]

Merci pour ta réponse. On est donc impérativement obliger de passer par une structure de ce style là :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
typedef struct noeud
{
    int donnée;
    struct noeud *gauche;
    struct noeud *droite;
};

[picodev]

Non, même si c'est une des manières les plus classiques d'implémenter un arbre.

Je te parlais de valeur interdite et de tableau d'entiers. Si tes entiers sont tous positifs ou nuls alors tu peux stocker ton arbre avec un simple tableau. Si on reprend ton exemple, avec comme valeur interdite -1, le début du tableau serait :

indice	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	...
valeur	7	4	8	3	-1	-1	10	2	4	-1	-1	-1	-1	9	-1	1	...

Les primitives seront :
racine = 0
fils_gauche(i)=2*i+1
fils_droit(i)=2*i+2
pere(i)=(i-1)/2
est_noeud(i)=tab[i]>=0
valeur(i)=tab[i]

C'est une des implémentations d'arbre avec un tableau.

[sambia39]

Bonjour
Il me semble qu'il y a une petite erreur dans le parcours en largeur d'abord du tas

Les primitives seront :
racine = 0
fils_gauche(i)=2*i+1
fils_droit(i)=2*i+2

C'est pas plutôt fils_gauche(i)=2*i[/B] & fils_droit(i)=2*i+1[/B] ?
à bientôt

[picodev]

Bonjour
Il me semble qu'il y a une petite erreur dans le parcours en largeur d'abord du tas

C'est pas plutôt fils_gauche(i)=2*i[/B] & fils_droit(i)=2*i+1[/B] ?
à bientôt

Pas quand le début des indices est 0. Dans ce cas on a fg(i)=2*i+1 et fd(i)=2*i+2 (sinon 0 serait sont propre fils gauche).
Quand le début des indices est 1 alors fg(i)=2*i et fd(i)=2*i+1.

Dans mon tout premier post je proposais une solution avec l'indice 0 étant un marqueur équivalent au NULL de la version avec les pointeurs. Cela mettait la racine ) l'indice 1.
Dans mon post précédent la racine se trouve ) l'indice 0.

Ce n'est pas un tas mais un arbre binaire de recherche. Avec un tas il n'y aurait pas besoin de valeur spéciale pour identifier les nœuds non utilisés.

[sambia39]

Bonsoir

Ce n'est pas un tas mais un arbre binaire de recherche. Avec un tas il n'y aurait pas besoin de valeur spéciale pour identifier les nœuds non utilisés.

En informatique un tas est une structure de données en arbres et on ne dit pas arbre binaire de recherche mais plutôt tas binaire et c'est le cas ici avec l'implémentation que tu as essaye d'expliquer. Elle utilise un tableau et les positions ou indices du tableau sont utilisées pour former un arbre (parfait) en claire Un tas binaire implémenté avec un tableau et D'ailleurs tu le dit toi même dans un de tes post

C'est une des implémentations d'arbre avec un tableau.

à bientôt

[hbx360]

Ok merci pour vos réponses

[picodev]

Bonsoir


En informatique un tas est une structure de données en arbres et on ne dit pas arbre binaire de recherche mais plutôt tas binaire et c'est le cas ici avec l'implémentation que tu as essaye d'expliquer. Elle utilise un tableau et les positions ou indices du tableau sont utilisées pour former un arbre (parfait) en claire Un tas binaire implémenté avec un tableau et D'ailleurs tu le dit toi même dans un de tes post

à bientôt

Effectivement c'est ce que j'explique. Ce que le primopostant cherche à implémenter est un abr et non un tas.
Implémenter un arbre avec un tableau est toujours faisaible. Comme un tas est un arbre parfait, sa représentation en tableau est simplifiée car on a besoin de ne connaître que la position de la dernière feuille car tout ajout dans le tas insère une feuille en fin de tableau. C'est une représentation simple et compacte.

Ici nous n'avons pas à faire à un tas mais à un arbre de recherche. Un arbre de recherche n'est en général pas parfait : certains nœuds internes n'auront pas deux fils . Il y aura des trous dans le tableau, trous que l'on doit être en mesure d'identifier. Si le tableau ne contient que des valeurs, alors on doit se baser sur des valeurs interdites. Cette représentation est toujours simple, mais elle est beaucoup moins compacte dans les cas dégénérés d'abr.

Je ne parlais de tas uniquement suite à ton post :

...
Il me semble qu'il y a une petite erreur dans le parcours en largeur d'abord du tas
...

[hbx360]

picodev merci pour ton dernier commentaire qui est lui aussi fort instructif je comprend mieux.
Mais construire un arbre de recherche avec un simple tableau doit être assez complexe à codé je pense en tout cas pour un débutant il est donc plus simple de passer par une struct.

[sambia39]

Bonjour

.....
Comme un tas est un arbre parfait, sa représentation en tableau est simplifiée car on a besoin de ne connaître que la position de la dernière feuille car tout ajout dans le tas insère une feuille en fin de tableau. C'est une représentation simple et compacte.

Suivant ton raisonnement dans sa généralité, on justifie qu'un tas est équilibré avec des noeuds externes de profondeur max qui sont tous à gauche et donc on parle d'un arbre parfait. En clair soit le tas Z, de taille n, de profondeur k qui justifie l'égalité ( k = lg(n)) dont le noeud externe est à (n+1-2^k) noeud en profondeur, égale à k. les autres sont donc à (k-1) ce qui définit le fait qu'un tas ou tout simplement un arbre binaire est équilibré (parfait) donc il peut avoir une implémentation sous forme de vecteur.

Un tas binaire peut être équilibré, dit parfait mais aussi incomplet.
Si on reprend les indices du tableau de ton exemple, on remarque que les indices sont de façon récurrente (0-n) et comme tu le dis la racine serait de 0.
Mais si "i" est un noeud interne alors le fils gauche et le fils droit seront à (2i+1) et (2i+2), et ceci correspond au parcours d'un tas ( doit-on alors l'appeler arbre de recherche , tas binaire , arbre binaire ou vecteur d'arbres binaire ?) 0 à n-1 en ordre de parcours et la définition d'un tas est claire: en retirant de Z tous les nœuds externes de profondeur k+1, on obtient bien un arbre complet, de taille 2^k+1 − 1 et si par l'application d'une récurrence, les indices seront de 2^k − 1 à 2^(k+1) − 2 ainsi donc on obtiendra X(i) = 2i+1 et Y(i)=2i+2 et pour tout entier i, X(i), Y(i), X(i 1) et Y(i 1), on obtient des entiers consécutifs.
On peut donc conclure que (2^k − 1) = 2^(k+1) − 1 et le k+1-ieme du tas représenté par des indices sont consécutifs.
On va donc pouvoir implémenter un tas de taille n sous la forme d’un vecteur ce qui se résume donc à ta formule
fils gauche = 2i+1
fils droite = 2i+2
père = (i-1)/2
avec un accès en O(1) à chaque noeud.

à bientôt

[picodev]

Je ne comprends pas trop.

J'ai parlé d'arbres et de leur implémentation utilisant un tableau sans jamais parler de tas jusqu'à ce que tu en parles. Maintenant tu parle d'arbre équilibré ce qui est encore une autre notion dont je n'ai pas fait mention.

Je t'avoue ne pas avoir lu avec énormément d'attention ton message. Cependant je relève :

...
On peut donc conclure que (2^k − 1) = 2^(k+1) − 1 et le k+1-ieme du tas représenté par des indices sont consécutifs.
...

Ce qui est faux.

[sambia39]

Bonsoir

Je ne comprends pas trop.
J'ai parlé d'arbres et de leur implémentation utilisant un tableau sans jamais parler de tas jusqu'à ce que tu en parles. Maintenant tu parle d'arbre équilibré ce qui est encore une autre notion dont je n'ai pas fait mention.

Effectivement j'ai parlé de tas ou encore d'arbres binaires pour justifier la compréhension et le rôle du tableau et dans un tableau chaque noeud de l'arbre binaire est stocké dans une cellule. Cependant dans tes arguments tu comptes représenter certains trous par des valeurs dites valeurs «interdite» ce qui veut dire: pour la cellule X il existe un noeud.

Ce n'est pas un tas mais un arbre binaire de recherche. Avec un tas il n'y aurait pas besoin de valeur spéciale pour identifier les nœuds non utilisés.

à bientôt