Discussion :

[Matheux14]

Bonsoir,

Je dois écrire un programme Python implémentant l'arbre de recherche binaire.

Il doit y avoir ci-dessous 4 fonctions comme ci-dessous :

1. Ajouter un élément à l'arbre de recherche binaire.

2. Rechercher/rechercher un élément dans l'arbre binaire de recherche.

3. Imprimer la valeur maximale de l'arbre.

4. Imprimer la profondeur de l'arbre.

pour chacun des quatre fonctions ci-dessus, veuillez donner et écrire des commentaires décrivant la complexité de l'algorithme.

Merci d'avance.

[wiztricks]

Salut,

Et vous avez fait quoi? Qu'est ce qui vous bloque?

- W

[Matheux14]

J'ai jété un coup d'oeil par ici https://en.wikipedia.org/wiki/Binary_search_tree

Mais je ne comprends pas grand chose..

[Sve@r]

Bonjour
Si ton prof t'a donné cet exo, c'est que tu es censé connaitre les bases et les principes concernant les arbres binaires. Parce que sinon de toute façon tu ne pourras pas t'en sortir et on n'est pas là pour t'expliquer ce qui a probablement été expliqué par ton prof et aussi déjà expliqué de partout sur le net.

J'ai jété un coup d'oeil par ici https://en.wikipedia.org/wiki/Binary_search_tree

Mais je ne comprends pas grand chose..

Tu aurais pu au-moins chercher en français.

[wiztricks]

J'ai jété un coup d'oeil par ici https://en.wikipedia.org/wiki/Binary_search_tree

Mais je ne comprends pas grand chose..

Peut être qu'il faut plus qu'y jeter un œil? De toutes façons, on ne pourra pas vous expliquer ce qu'il y a à faire mieux que ce que vous trouverez déjà sur Internet.

- W

[jurassic pork]

hello,
tu peux jeter trois coups d'oeil :

un ici : Structures de données : les arbres
un autre ici : Algorithmes sur les arbres binaires
et un autre ici : Projet : implémentation en Python des algorithmes sur les arbres binaires

Ami calmant, J.P

[Invité]

Je n'y connais rien mais en gros c'est ça un arbre binaire en python ?

Code :

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

arbre = {1: {2: {4:{}}, 3: {5:{}, 6:{}}}}

Code :

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

1
2
3
4
5
6
7
8
9
def recursive(tree,pcd=''):
	if isinstance(tree,dict):
		if pcd:
			pcd += ' contient '+str(list(tree.keys()))
		else:
			pcd = str(list(tree.keys()))
		print(pcd)
		for k in tree:
			recursive(tree[k],pcd+' -> '+str(k))

Code :

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

1
2
3
4
5
6
7
8
>>> recursive(arbre)
[1]
[1] -> 1 contient [2, 3]
[1] -> 1 contient [2, 3] -> 2 contient [4]
[1] -> 1 contient [2, 3] -> 2 contient [4] -> 4 contient []
[1] -> 1 contient [2, 3] -> 3 contient [5, 6]
[1] -> 1 contient [2, 3] -> 3 contient [5, 6] -> 5 contient []
[1] -> 1 contient [2, 3] -> 3 contient [5, 6] -> 6 contient []

??

[Sve@r]

Je n'y connais rien mais en gros c'est ça un arbre binaire en python ?

Code :

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

arbre = {1: {2: {4:{}}, 3: {5:{}, 6:{}}}}

Oui. Tu peux aussi le faire avec des listes => arbre = [1, [2, [4, []], [3, [5, [6, []]]].

[Invité]

Peut-être plus facile à utiliser les dictionnaires ?

Code :

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

1
2
3
>>> arbre = {'C:': {'Windows': {'System':{}}, 'Users': {'Toto':{'Coucou'}, 'Lala':{}}}}
>>> arbre['C:']['Users']['Toto']
{'Coucou'}

J'ai tenté de faire une représentation graphique d'un arbre bien symétrique, j'ai abandonné ^^

[Sve@r]

Peut-être plus facile à utiliser les dictionnaires ?

Ce n'est pas le but d'un arbre (sinon autant rester sur le dictionnaire pur ou autres outils plus adaptés, comme par exemple le JSON qui serait parfait pour ton exemple). Par ailleurs certains langages ne connaissent pas cette notion de dictionnaire.
Un arbre binaire a pour objectif d'économiser les comparaisons et éviter les déplacements de valeurs (opérations présumées "longues") dans les tris. Chaque nouvelle valeur descend l'arbre existant en allant à gauche si elle est plus petite et à droite si elle est plus grande que le noeud courant. Et vient se placer à la première place libre, formant alors un nouveau noeud puis ne bouge plus.
Si l'arbre est parfaitement équilibré, alors tout nouveau noeud n'aura besoin que de log(n)/log(2) comparaisons pour trouver sa place ("n" étant le nombre de noeuds déjà placés). Exemple ave 1024 noeuds, seulement 10 comparaisons suffisent pour placer le 1025° (à condition qu'il soit bien équilibré).

Et pour récupérer la liste des valeurs triées, suffit d'appliquer l'algo récursif suivant

• lire branche gauche
• afficher valeur courante
• lire branche droite

[Invité]

Hum, rien compris !
Je regarderais plus tard à quoi sert un arbre binaire, si ça m'intéresse...

[jurassic pork]

Hum, rien compris !
Je regarderais plus tard à quoi sert un arbre binaire, si ça m'intéresse...

Regarde les trois liens que j'ai mis plus haut

[Sve@r]

Hum, rien compris !

Prend l'exemple suivant

Si tu veux rajouter ensuite la valeur 4, tu compares d'abord avec 10 (plus petit donc à gauche) puis avec 5 (pareil) puis avec 3 (plus grand donc à droite). Total 7 éléments présents dans l'arbre mais seulement 3 comparaisons pour trouver sa bonne place qui sera sous le 3 à droite. Et ensuite il ne bougera plus (gain de temps car dans les algortihmes de tris ce qui coûte le plus ce sont les comparaisons et les déplacements), ce seront les autres nombres qui viendront se placer par rapport à celui-ci.

Dans cette vidéo qui montre de façon poétique le tri à bulle (le plus pourri de tous les tris mais le plus simple à coder), il y a 25 comparaisons et 13 déplacements pour trier 10 éléments.

[Invité]

Ah ah excellent !

Et en pratique ça sert à quoi ? Gérer un tournoi comme dans l'exemple donné dans un des liens ?
Bizarre j'aurai pas pensé à coder un tournoi avec un arbre binaire, ça me paraît compliqué à mettre en œuvre, plus simplement j'aurai utilisé une liste qui se vide petit à petit en retirant les perdants.

[Sve@r]

Et en pratique ça sert à quoi ? Gérer un tournoi comme dans l'exemple donné dans un des liens ?
Bizarre j'aurai pas pensé à coder un tournoi avec un arbre binaire, ça me paraît compliqué à mettre en œuvre, plus simplement j'aurai utilisé une liste qui se vide petit à petit en retirant les perdants.

Tu n'as pas bien lu ledit lien. Le tournoi n'est pas "géré" par un arbre binaire mais "représenté" par un graphique "montré" en arbre, ce n'est pas la même chose. Et donc la façon dont on peut représenter un tournoi varie effectivement selon ce qu'on veut montrer du tournoi. Avec un arbre on peut plus facilement voir le passé (qui a gagné le 1er round, le second, etc) chose que ne permet pas ta liste.
Il n'y a pas longtemps tu as cité John Kreese de Karaté Kid. Tu n'as pas remarqué que aussi bien dans le film que dans la série dérivé Cobra Kai ils utilisent des arbres pour montrer l'évolution du tournoi ? Par exemple ici on voit que c'est Hawk et Stone qui (entre autres) ont gagné le premier round


Mais là on ne parle pas d'arbre binaire, juste d'arbre. L'arbre binaire c'est celui qui est expliqué en bas dudit lien (ce que j'ai représenté de façon grossière) et qui sert principalement à trier des données.

[f-leb]

Bonsoir,

Un arbre binaire a pour objectif d'économiser les comparaisons et éviter les déplacements de valeurs (opérations présumées "longues") dans les tris. Chaque nouvelle valeur descend l'arbre existant en allant à gauche si elle est plus petite et à droite si elle est plus grande que le noeud courant...

ça c'est pour un arbre binaire de recherche, un cas particulier d'arbre binaire.
Un tournoi peut être représenté par un arbre binaire, mais ce n'est pas un arbre binaire de recherche.

[Invité]

@Sve@r Bon exemple !

J'propose un nouveau logo pour python :

(J'ai pas le talent pour dessiner un python...)


Plus séireusement effectivement je n'ai pas pensé à l'aspect "historique" !

[f-leb]

Salut,

Et en pratique ça sert à quoi ? Gérer un tournoi comme dans l'exemple donné dans un des liens ?
Bizarre j'aurai pas pensé à coder un tournoi avec un arbre binaire, ça me paraît compliqué à mettre en œuvre, plus simplement j'aurai utilisé une liste qui se vide petit à petit en retirant les perdants.

Les arbres (dont les arbres binaires) ne sont que des structures de données dont les algorithmes de manipulation sont le plus souvent récursifs. Voir la FAQ et les exercices de la rubrique Algorithmes