Le maintien d'un ordre efficace où vous pouvez insérer des éléments « entre » deux autres éléments dans l'ordre?

https://cs.stackexchange.com/questions/14708

16-10-2019
|

Question

Imaginez que j'ai un ordre sur un tas d'éléments comme ceci:

entrer image description ici

Si une flèche $ X \ Y leftarrow $ signifie $ X .

Pour répondre efficacement des requêtes telles que $ A de la stackrel {?} {<} D $, une sorte de structure d'étiquetage ou de données est nécessaire. Par exemple, vous pouvez numéroter les nœuds de gauche à droite, et donc vous pouvez simplement faire entier par rapport à répondre à la question: {?} $ A \ stackrel {<} D \ implique 1 <4 \ implique T $. Il ressemblerait à quelque chose comme ceci:

entrer image description ici

Lorsque le numéro est l'ordre, et la lettre est juste un nom.

Mais si vous avez besoin d'insérer des éléments « entre » deux autres éléments dans l'ordre, comme suit:

entrer image description ici

Comment pouvez-vous maintenir un tel ordre? Avec la numérotation simple, vous rencontrez le problème qu'il n'y a pas des entiers « entre » $ 2,3 $ à utiliser.

La solution

Ceci est connu comme le problème « maintien de l'ordre » . Il existe une solution relativement simple en utilisant O $ (1) $ amorti le temps pour les requêtes et les inserts. Maintenant, par « relativement simple », je veux dire que vous devez comprendre quelques blocs de construction, mais une fois que vous obtenez ceux-ci, le reste est pas difficile de voir.

http://courses.csail.mit.edu/6.851/ spring12 / conférences / L08.html

L'idée de base est une structure de données à deux niveaux. Le niveau supérieur est comme la solution d'arbre AVL par Realz Slaw, mais

Les noeuds sont marqués directement avec des chaînes de bits de longueur $ O (\ logn) $ avec un ordre qui correspond à leur ordre dans l'arbre. La comparaison prend donc constante de temps
Un arbre avec moins de rotations qu'un arbre AVL est utilisé, comme un arbre de bouc émissaire ou un arbre de poids équilibré, si relabellings sont moins fréquents.

Le niveau inférieur est les feuilles de l'arbre. Ce niveau utilise la même longueur d'étiquettes, $ O (\ n lg) $, mais ne détient que $ O (\ logn) $ articles dans chaque feuille dans une liste, de simple. Cela vous donne suffisamment de bits supplémentaires réétiqueter agressivement.

Les feuilles deviennent trop grand ou trop petit chaque $ O (\ logn) $ inserts, ce qui induit un changement dans le niveau supérieur, qui prend $ O (\ logn) $ temps amorti ($ \ Omega (n) $ pire temps -case). Amorti, ce n'est O $ (1) $.

Une grande partie des structures plus complexes existent pour effectuer des mises à jour dans O $ (1) $ dans le pire des cas.

Autres conseils

Au lieu de numérotation simple, vous pouvez répartir les chiffres sur une large gamme (taille constante), comme minimum entier et valeurs maximales d'un nombre entier de CPU. Ensuite, vous pouvez continuer à mettre des nombres « entre » en faisant la moyenne des deux nombres environnants. Si les chiffres sont trop serrés (par exemple vous vous retrouvez avec deux entiers adjacents et il n'y a pas de numéro entre les deux), vous pouvez faire une seule fois renumérotation de l'ordre entier, redistribuant les numéros uniformément sur toute la gamme.

Bien sûr, vous pouvez exécuter dans la limitation qui sont utilisés tous les numéros dans la plage de la grande constante. Tout d'abord, ce n'est pas généralement un problème, étant donné que la taille entière sur une machine est assez grand pour que si vous aviez plus d'éléments qu'il est probable ne serait pas tenir dans la mémoire de toute façon. Mais si c'est un problème, vous pouvez simplement les renumérotez avec une plus grande gamme entière.

Si l'ordre d'entrée est pathologique, cette méthode pourrait amortit les renumérotations.

Répondre à des requêtes

Une comparaison simple entier peut répondre à la requête $ de \ left (X \ {stackrel?} {<} Y \ right) $.

moment de la requête serait très rapide ($ \ mathcal {O} \ left (1 \ right) $) si vous utilisez des entiers de la machine, car il est une simple comparaison entier. En utilisant une plus grande gamme nécessiterait des entiers plus grands, et la comparaison prendrait $ \ mathcal {O} \ left (\ log {| entier |} \ right). $

Insertion

Tout d'abord, vous maintiendrait la liste chaînée de l'ordre, a démontré dans la question. L'insertion ici, étant donné les noeuds pour placer le nouvel élément entre les deux, serait $ \ mathcal {O} \ left (1 \ right) $.

Étiquetage le nouvel élément serait généralement rapide $ \ mathcal {O} \ left (1 \ right) $ parce que vous devez calculer le nouveau numeber facilement en moyenne les numéros environnants. De temps en temps, vous pourriez manquer de numéros "entre", ce qui déclencherait le $ \ mathcal {O} \ left (n \ right) $ Temps de procédure renumérotation.

Éviter renumérotation

Vous pouvez utiliser des flotteurs au lieu des entiers, donc quand vous obtenez deux entiers « adjacents », ils peut être en moyenne. Ainsi, vous pouvez éviter la renumérotation face à deux flotteurs entiers: il suffit de les diviser en deux. Cependant, par la suite le type à virgule flottante viderait de précision, et deux flotteurs de « adacent » ne sera pas en mesure d'être en moyenne (la moyenne des nombres environnants sera probablement égal à l'un des numéros environnants).

Vous pouvez utiliser de la même un nombre entier de « virgule », où vous maintenez deux entiers pour un élément; un pour le nombre et l'autre pour la décimale. De cette façon, vous pouvez éviter renumérotation. Cependant, le nombre entier décimal finira par déborder.

Utilisation d'une liste de nombres entiers ou bits pour chaque étiquette peut entièrement éviter la renumérotation; cela est essentiellement équivalent à l'utilisation des nombres décimaux avec une longueur illimitée. La comparaison serait fait lexicographique, et les temps de comparaison augmentera à la longueur des listes concernées. Cependant, cela peut déséquilibrer l'étiquetage; certaines étiquettes peuvent nécessiter qu'un seul entier (pas décimal), d'autres peuvent avoir une liste de longue longueur (décimaux longues). Ceci est un problème, et renumérotation peut aider ici aussi, en redistribuant la numérotation (ici des listes de numéros) uniformément sur une plage choisie (plage ici signifie peut-être la longueur des listes) de sorte qu'après un tel renumérotation, les listes sont de la même longueur .

Cette méthode est en fait utilisé réellement dans cet algorithme ( , relevant ); au cours de l'algorithme, un ordre arbitraire doit être conservé et l'auteur utilise des nombres entiers et renumérotation pour y parvenir.

Essayer de coller à votre espace numéros rend la clé un peu limité. On pourrait utiliser la variable length au lieu des chaînes, en utilisant la logique de comparaison "a" < "ab" < "b". Encore deux problèmes restent à résoudre A. Les clés peuvent être arbitrairement longues B. Longue comparaison des clés pourrait devenir coûteux

Vous pouvez maintenir un arbre sans clé AVL ou similaire.

Il fonctionnerait comme suit: L'arbre maintient un ordre sur les nœuds comme un arbre AVL fait normalement, mais au lieu de la clé de déterminer où le noeud « devrait » mensonge, il n'y a pas de clés, et vous devez explicitement insérer la noeuds « après » un autre noeud (ou en d'autres termes « entre » deux noeuds), où « après » moyens il vient après lui dans l'ordre dans la traversée de l'arbre. L'arbre sera donc de maintenir l'ordre pour vous naturellement, et il équilibrerait aussi, en raison de l'AVL construit dans les rotations. Cela permet de garder tout uniformément répartie automatiquement.

Insertion

En plus de l'insertion régulière dans la liste, comme le montre la question, vous maintiendrait un arbre séparé AVL. L'insertion à la liste elle-même est $ \ mathcal {O} \ left (1 \ right) $, que vous avez les "avant" et "après" noeuds.

Temps d'insertion dans l'arbre est $ \ mathcal {O} \ left (\ log {n} \ right) $, le même que l'insertion d'un arbre AVL. L'insertion implique d'avoir une référence au nœud que vous souhaitez insérer après, et vous suffit d'insérer le nouveau nœud dans la gauche du nœud de gauche à droite l'enfant; cet endroit est « à côté » dans l'ordre de l'arbre (il se trouve à côté du parcours dans l'ordre). Ensuite, faites les rotations AVL typiques pour rééquilibrer l'arbre. Vous pouvez faire une opération similaire pour « insérer avant »; Ceci est utile lorsque vous devez insérer quelque chose dans le début de la liste, et il n'y a pas de noeud « avant » noeud.

Répondre à des requêtes

Pour répondre aux questions de $ \ gauche (X \ stackrel {?} {<} Y \ right) $, vous trouvez simplement tous les ancêtres de $ X $ et $ Y $ dans l'arbre, et vous analysez l'emplacement où dans l'arbre des ancêtres diverger; celui qui diverge à la « gauche » est le moindre des deux.

Cette procédure prend $ \ mathcal {O} \ left (\ log {n} \ right) $ temps à grimper l'arbre à la racine et l'obtention des listes ancêtres. Il est vrai que cela semble plus lent que la comparaison entière, la vérité est, il est le même; seulement que la comparaison entière sur une CPU est limitée par une grande constante pour le rendre $ \ mathcal {O} \ left (1 \ right) $; si vous débordez cette constante, vous devez maintenir plusieurs entiers ($ \ mathcal {O} \ left (\ log {n} \ right) $ entiers en fait) et faire la même $ \ mathcal {O} \ left (\ log { n} \ right) $ comparaisons. Vous pouvez également « lié » à la hauteur de l'arbre par une quantité constante, et « tricher » de la même façon la machine fait avec des nombres entiers: maintenant les requêtes sembleront $ \ mathcal {O} \ left (1 \ right) $