Arbre binaire de recherche

Version imprimable

09/01/2022, 21h47
Matheux14

Arbre binaire de recherche

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. :)
09/01/2022, 22h44
wiztricks

Salut,

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

- W
10/01/2022, 00h18
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..
10/01/2022, 08h29
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.

Citation:

Envoyé par 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..

Tu aurais pu au-moins chercher en français.
10/01/2022, 10h10
wiztricks

Citation:

Envoyé par 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..

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
10/01/2022, 10h41
jurassic pork

hello,
tu peux jeter trois coups d'oeil 8O :

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

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

Code:

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

Code:

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:

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 []

10/01/2022, 12h15
Sve@r

Citation:

Envoyé par LeNarvalo

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

Code:

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

Oui. Tu peux aussi le faire avec des listes => arbre = [1, [2, [4, []], [3, [5, [6, []]]].
10/01/2022, 12h28
Invité
Peut-être plus facile à utiliser les dictionnaires ?
Code:

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é ^^
10/01/2022, 13h03
Sve@r
Citation:

Envoyé par LeNarvalo

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
10/01/2022, 13h50
Invité

Hum, rien compris ! :marteau:
Je regarderais plus tard à quoi sert un arbre binaire, si ça m'intéresse...
10/01/2022, 14h00
jurassic pork

Citation:

Envoyé par LeNarvalo

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

Regarde les trois liens que j'ai mis plus haut
10/01/2022, 16h41
Sve@r

1 pièce(s) jointe(s)

Citation:

Envoyé par LeNarvalo

Hum, rien compris ! :marteau:

Prend l'exemple suivant
Pièce jointe 611565
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.
https://www.youtube.com/watch?v=lyZQPjUT5B4
10/01/2022, 17h32
Invité

Ah ah excellent ! :D

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.
10/01/2022, 19h38
Sve@r

1 pièce(s) jointe(s)

Citation:

Envoyé par LeNarvalo

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
Pièce jointe 611581

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.
10/01/2022, 20h07
f-leb

Bonsoir,

Citation:

Envoyé par Sve@r

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.
10/01/2022, 21h54
Invité

1 pièce(s) jointe(s)

@Sve@r Bon exemple ! :mouarf:

J'propose un nouveau logo pour python :
Pièce jointe 611592
(J'ai pas le talent pour dessiner un python...)

Plus séireusement effectivement je n'ai pas pensé à l'aspect "historique" !
11/01/2022, 21h01
f-leb

Salut,

Citation:

Envoyé par LeNarvalo

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 ;)