Les arbres rouge-noir doivent-ils être triés? - java, arbre, arbre rouge-noir

J'ai une question assez simple ici: Les arbres rouge-noir doivent-ils être triés? Je pose cette question parce que la petite boîte à droite de la page wikipedia (http://en.wikipedia.org/wiki/Red–black_tree) indique que la durée de la recherche est O (log (n)); cependant, cela ne serait pas vrai uniquement si l’arbre était trié. Par contre, les propriétés

Réponses:

Les arbres noirs et rouges sont triés (le tout toutLes arbres RB sont des arbres binaires triés, mais tous les arbres binaires triés ne sont pas des arbres rouges et noirs). La différence entre un arbre binaire simple et un arbre noir rouge est que les arbres RB garantie ce temps de recherche sera bûche₂(n) parce qu’elles sont "équilibrées". En substance, cela garantit que le nombre de couches pour n les nœuds ne seront jamais plus de bûche₂(n), en gardant la recherche binaire en échec.

Un arbre binaire simple sans équilibrage ne produira pas toujours un bûche₂(n) complexité temporelle. Par exemple, si j'ai un arbre comme celui-ci:

  4
/ 
3   6

7

10

12

Pour cet arbre non équilibré, le temps de recherche réel est presque linéaire pour trouver 12 (complexité temporelle dans le cas le plus défavorable, 5 comparaisons). Pour un arbre équilibré qui a au plus bûche₂(n) couches, l'arbre ci-dessus pourrait être:

     7
/   
4    10
/      
3   6    12

Et donc, trouver l’un des nœuds de la couche la plus basse prendra au plus 3 comparaisons (ce qui correspond à bûche₂(n) car il est en fait arrondi, ceil [log₂(6)] = 3)

La clé ici est de se rappeler que le nombre decouches est fonctionnellement équivalent au nombre de comparaisons que vous devez faire lorsque vous commencez à la racine. Les arbres rouge-noir limitent le nombre de couches au minimum via l’équilibrage, alors que les arbres binaires asymétriques à la vanille ne le sont pas.

Un arbre rouge-noir est un arbre de recherche binaire. Selon la définition d'un arbre de recherche binaire, l'enfant de gauche (et tous les descendants) doit être inférieur au parent et l'enfant de droite (et tous les descendants) doit être supérieur au parent. Il y a donc une commande.

Les arbres rouge-noir ont un temps de recherche de O (log n) en raison de la manière dont ils configurent leurs nœuds avec un ordre naturel.

Lorsque vous effectuez une comparaison de nœud, vous ignorez théoriquement la moitié des options lorsque vous prenez une branche.

Puisque tu ne peux que "la moitié" log n times Avant d’arriver à un élément, votre complexité de recherche est O(log n)

L'intérêt d'un arbre rouge-noir est de maintenir l'équilibre de l'arbre dans une certaine mesure. Si vous assouplissez la contrainte de tri, maintenir une arborescence équilibrée est trivial car vous pouvez placer des nœuds où vous le souhaitez.