Red&Black - Tree

[ampholyte]

Bonjour,

J'ai des difficultés à comprendre, pourquoi les arbres Rouge-Noir sont plus rapides que des arbres de recherche "standarts".

Je m'explique :

Je dispose d'un algorithme me permettant de vérifier qu'un nombre n'est pas saisi plus de 2 fois par seconde.
Pour cela je dispose d'une structure C dans laquelle je stocke ce nombre et la date UTC de la dernière mise à jour.
Cette structure est stockée dans un arbre Rouge-Noir à chaque fois qu'il n'est pas trouvé dans cette arbre et dans le cas contraire vérifie que la dernière mise à jour est supérieur à 500ms.

Ma question est donc, en quoi stocker cette structure dans un arbre Rouge-Noir est-il plus approprié lors d'un ajout, d'une recherche d'un élément qu'un arbre binaire ?

Merci d'avance.

[Dlzlogic]

J'ai pas vraiment compris les détails.
Je ne connais pas l'expression "Arbre Rouge-Noir"
Qu'appelez-vous arbre binaire ?
A mon avis la distinction entre les deux est un choix entre hachage et séquentiel.

[fatal_error]

hello,

par exemple suppose que tes noeuds au lieu de construire des structures contiennent une valeur.

voici un exemple de worst case pour un arbre binaire:
Je note en parenthésé, le parent au milieu
(1,2,3)
arrive la valeur 4
(1,2,(--,3,4))
puis arrive la valeur 5
(1,2,(--,3,(--,4,5)))
...etc.
Suppose que tu veuilles ajouter 10.
tu regardes 1, puis 3, puis 4, puis 5...jusqu'à 10. et enfin tu l'insères.
Pour rechercher 10, rebelote.

Avec un arbre rouge et noire, tu fais pas autant d'étapes.

[ampholyte]

Bonjour,

@Dlzlogic :
Un arbre bicolore (ou noir rouge) est un arbre binaire de recherche dans lequel chaque nœud a un attribut supplémentaire : sa couleur, qui est soit rouge soit noire. En plus des restrictions imposées aux arbres binaires de recherche, on ajoute les règles suivantes :

Un nœud est soit rouge soit noir.
La racine est noire.
Le parent d'un nœud rouge est noir.
Le chemin de chaque feuille à la racine contient le même nombre de nœuds noirs.

@fatal_error : Merci pour ta réponse, mais je ne comprends pas pourquoi on effectue moins d'étape lors de la recherche d'un élément. Qu'est-ce qui permet à un arbre bicolore de ne pas passer par 1, 3, 4,5 jusqu'à 10 dans ton exemple ?

[fatal_error]

parce que tous les chemins de la racine a la feuille sont a peu pres de meme longueur (moyennant un rouge).
Tu peux pas avoir un chemin de longueur 1 (1-3)et un chemin de longueur 7(1-10)

[ampholyte]

:mur: Evidemment c'était plus qu'évident !

Merci pour cette réponse, j'y vois nettement plus clair :ptdr: