Déséquilibre maximum dans les arbres noirs rouges

J'ai du mal à comprendre ce concept, Question étant donné que les nœuds noirs sont équilibrés, quel est le déséquilibre maximal qu'un arbre RB peut avoir si l'on considère l'arbre dans son ensemble?Déséquilibre maximum dans les arbres noirs rouges

Source

2017-09-23 Bhargav

Je cite Wikipedia: the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.

Ce qui signifie que le déséquilibre maximal est deux fois la longueur du plus court chemin vers une feuille. Le article explique la raison d'une bonne manière.

Source

2017-09-23 23:58:02

Non, mais cela ne tient pas compte du fait que les nœuds noirs sont équilibrés. – Bhargav

C'est. Si le nombre de nœuds noirs dans un chemin est B, alors la profondeur maximum contiendra des nœuds rouges et noirs alternés, sa profondeur sera donc 2 * B (2 * B-1 pour être exact au début et à la fin avec des nœuds noirs) et la profondeur minimale ne contiendra que des nœuds noirs, donc ce sera B. –

Déséquilibre maximum dans les arbres noirs rouges

Répondre

Questions connexes