Quel intérêt d'utiliser un RBTree dans l'algorithme de Fortune ?

[invite1390086e]

Bonjour,

Raymond Hill utilise un RB Tree pour gérer sa ligne de rivage dans l’algorithme de Fortune : http://www.raymondhill.net/voronoi/rhill-voronoi.html
Quel est l’intérêt de ce choix ?

Merci.
-----

[polo974]

rb tree = red black tree = arbre bicolore = arbre PRESQUE équilibré (en longueur) https://fr.wikipedia.org/wiki/Arbre_bicolore

AVL tree = arbre équilibré (en longueur) https://fr.wikipedia.org/wiki/Arbre_AVL

le premier est un poil plus rapide en insertion que le second, alors que le second est en moyenne plus rapide en recherche...

et puis parfois le choix se fait en prenant le premier algo remplissant la fonction qu'on trouve...

(il y a des rbtree dans linux: https://www.kernel.org/doc/Documentation/rbtree.txt )

[invite1390086e]

Merci.
Mais ça n'explique toujours pas pourquoi un RBTree, voir même un arbre quelconque.
La ligne de rivage, comme son nom l'indique, est une ligne, pas un arbre.
On est obligé de tester x paraboles jusqu'à trouver la bonne.
Donc pourquoi ne pas simplement utiliser une liste, chaînée ou pas ?

[polo974]

je n'ai pas vraiment fouillé le source, mais lorsqu'il faut insérer un point entre 2 autres, de façon aléatoire, il est plus efficace de ranger les points existants dans un arbre.
sinon, il faudrait parcourir la liste jusqu'à trouver le point d'insertion (en moyenne la demi longueur de la liste), ce qui devient de plus en plus coûteux alors que dans un arbre ((quasi) équilibré), la progression est seulement en log(n).

[A voir en vidéo sur Futura]