fusionner deux arborescence splay

Question

Comment fusionner deux arborescence splay avec le coût amorti de log (n)?

Answer 1

Je suppose que les arbres de jeu que vous voulez fusionner contiennent n objets chacun. (c'est-à-dire au total, nous avons 2n objets). Ensuite, je pense qu'il n'est pas possible de les fusionner avec log(n) coût amorti, sauf si vous imposer d'autres hypothèses. Si vous n'avez aucune information sur les objets contenus dans les arbres, vous devrez au moins regarder chaque élément de l'un des deux arbres, ce qui aura coûté O(n). Cependant, si vous pouvez faire certaines hypothèses sur les objets, vous pouvez le faire dans O(log(n)). Vous pouvez extraire certains sous-arbres de sorte que vous puissiez insérer la sous-arborescence entière dans l'autre arborescence de splay. Cependant, je ne connais pas un algorithme exact comment acchieve O(log(n)). Par exemple, si nous savons que l'objet le plus grand dans Tree1 est plus petit que le plus petit objet dans Tree2, alors nous pourrions simplement afficher le nœud le plus à gauche de Tree2 et ensuite nous suspendons la racine de Tree1 sous la nouvelle racine de Tree2.