J'enseigne un cours sur les structures de données et couvrirai les arbres splay au début de la semaine prochaine. J'ai lu à plusieurs reprises l'article sur les arbres splay et je connais l'analyse et l'intuition derrière la structure des données. Cependant, je n'arrive pas à trouver une solide intuition pour la fonction potentielle que Sleator et Tarjan utilisent dans leur analyse.

L'analyse fonctionne en attribuant à chaque élément de l'arbre un poids arbitraire , puis en définissant la taille s ( x ) d'un nœud comme étant la somme des poids des nœuds du sous-arbre enraciné en x . Ils prennent ensuite le log de cette valeur pour obtenir le rang r ( x ) du nœud, donc r ( x ) = log s ( x ) . Enfin, la fonction potentielle de l'arbre est définie comme la somme des rangs de tous les nœuds.$w_i$$s(x)$$x$$r(x)$$r(x) = \log s(x)$

Je comprends que cette fonction potentielle fonctionne correctement et je peux suivre l'analyse, mais je ne vois pas pourquoi ils choisiraient ce potentiel. L'idée d'attribuer une taille à chaque nœud est logique pour moi, car si vous résumez les tailles, vous obtenez la longueur de chemin pondérée de l'arbre. Cependant, je ne peux pas comprendre pourquoi ils ont décidé de prendre les journaux des poids et de les résumer à la place - je ne vois aucune propriété naturelle de l'arbre à laquelle cela correspond.

La fonction potentielle de l'arbre splay correspond-elle à une propriété naturelle de l'arbre? Y a-t-il une raison particulière, autre que «ça marche», pour qu'ils choisissent ce potentiel? (Je suis particulièrement curieux car cet ensemble de notes de cours mentionne que "l'analyse est de la magie noire. [N] aucune idée de la façon dont on l'a découvert")

Merci!

Comment trouver un potentiel de somme de journaux

Considérons l'algorithme BST pour chaque accès pour l'élément x , il réorganise uniquement les éléments du chemin de recherche P de x appelé avant-chemin, en un arbre appelé après-arbre. Pour tout élément a , soit s ( a ) et s ' ( a ) la taille du sous-arbre enraciné respectivement à a avant et après le réarrangement. Alors s ( a ) et l ' ( a ) peut différer ssi un ∈ P .$A$$x$$P$$x$$a$$s(a)$$s'(a)$$a$$s(a)$$s'(a)$$a \in P$

De plus, ne fait que réorganiser à tout moment de nombreux éléments du chemin de recherche. Appelons ce type d'algorithme "local". Par exemple, l'arbre d'affichage est local. Il réorganise seulement au plus 3 éléments à la fois par zig, zigzig et zigzag.$A$

Maintenant, tout algorithme local qui crée "beaucoup" de feuilles dans l'arbre secondaire, comme l'arbre splay, a la belle propriété suivante.

On peut créer un mapping tel que$f: P \rightarrow P$

1. Il y a linéairement plusieurs , où s ′$a \in P$ .$s'(f(a)) \le s(a)/2$
2. Il y a toujours beaucoup , où $a \in P$ peut être grand mais au plus trivialement n .$s'(f(a))$$n$
3. Autres éléments , s $a \in P$ .$s'(f(a)) \le s(a)$

Nous pouvons le voir en déployant le changement de chemin de recherche. La cartographie est en fait assez naturelle. Cet article, A Global Geometric View of Splaying , montre précisément les détails pour voir l'observation ci-dessus.

Après avoir connu ce fait, il est très naturel de choisir un potentiel de somme de logs. Parce que nous pouvons utiliser le changement potentiel des éléments de type 1 pour payer la totalité du réarrangement. De plus, pour les éléments d'un autre type, nous devons payer le changement potentiel par au plus logarithmique. Par conséquent, nous pouvons dériver le coût amorti du logarithme.

Je pense que la raison pour laquelle les gens pensent que c'est de la "magie noire" est que l'analyse précédente ne "dévoile" pas le changement global du chemin de recherche et ne voit pas ce qui se passe réellement en une seule étape. Au lieu de cela, ils montrent le changement de potentiel pour chaque «transformation locale», puis montrent que ces changements potentiels peuvent être télescopés comme par magie.

PS Le papier montre même une certaine limitation du potentiel de somme de logs. Autrement dit, on peut prouver la satisfiabilité du lemme d'accès via un potentiel de somme de journaux à l'algorithme local uniquement.

Interprétation du potentiel de somme des journaux

Il existe une autre façon de définir le potentiel de BST dans le papier de Georgakopoulos et McClurkin qui est essentiellement le même que le potentiel de somme de journaux dans le papier de Sleator Tarjan. Mais cela me donne une bonne intuition.

Maintenant, je passe à la notation du papier. Nous attribuons un poids à chaque nœud u . Soit W ( $w(u)$$u$$W(u)$$u$$u$

Maintenant, au lieu de définir le rang sur les nœuds, nous définissons le rang aux bords, qu'ils ont appelé facteur de progression .

$S$

$(u,v)$$u$$v$$W(u)/W(v)$

Observez que c'est le potentiel de Sleator Tarjan presque égal et qu'il est additif sur les chemins.

edit: Il s'avère que cette définition alternative et l'intuition derrière elle ont été décrites il y a longtemps par Kurt Mehlhorn. Voir son livre "Structures de données et algorithmes" Volume I, Section III. 6.1.2 Arbres évasés, pages 263 - 274.