Arborescence de segments avec décalage facile

Question

J'ai besoin de structure de données basée sur l'arbre de segments, mais avec une différence par rapport à l'arbre de segments classique. DS devrait soutenir le déplacement facile des éléments. Je veux dire que je voudrais avoir ds sur lequel je pouvais:

• effectuer des requêtes sur des segments (c.-à-somme des éléments de l'index l à l'index r)
• insert nouveaux elemnts avant tout index, puis déplacer tous les éléments sur le côté droit des nouveaux éléments

Ce sera bien si toutes ces opérations fonctionnent dans O(logn) Salutations

Answer 1

Oui, mais pas sûr que vous pouvez k eep l'arbre équilibré.

La structure de base est comme ceci. Chaque nœud garde la trace de la distance entre le début de l'intervalle qu'il suit et la séparation entre ses enfants. Par exemple, si un nœud garde l'intervalle [A, B] et a des enfants gardant [A, C] et [C + 1, B] alors le premier nœud ne devrait stocker que l'information C - A. Cela vous permettra de changer facilement les tailles des intervalles sans avoir à jouer avec la structure entière. Cela signifie également que vous invalidez tous les itérateurs existants lorsque vous déplacez quelque chose à l'intérieur et que chaque itérateur garde la trace de l'intervalle.

Pour faire une opération de changement:

• faire une recherche pour le point d'insertion.
• sélectionnez un noeud approprié sur le chemin.
• insérez un nouveau nœud au-dessus du nœud sélectionné. Ce noeud doit contenir l'ancien + nouvel intervalle. Donc, définissez sa valeur divisée à la taille du décalage. Maintenant, le nouvel espace est l'enfant de gauche, l'ancien espace est le bon enfant.
• ajoutez les enfants que vous souhaitez conserver pour le nouvel espace.
• mettre à jour tous les parents où le point de partage était sur la gauche, car il y a maintenant plus de valeurs avant leur division.

Toute autre opération doit être effectuée de la même manière. Vous devriez choisir un nœud où le nouvel intervalle est à peu près égal à la taille du nœud afin que vous gardiez le O (logn) pour les opérations. Il est évident que l'insertion répétée d'un élément peut rendre certains chemins considérablement plus longs que d'autres, sauf si vous ajoutez également une étape pour rééquilibrer l'arbre après avoir effectué un décalage.

Cependant, si vous connaissez les changements précédents, je repasserais simplement les quarts de travail en arrière et calculerais l'emplacement final de toutes les données et j'interrogerai O (N). Ensuite, vous pouvez simplement faire un arbre de segment régulier et ne pas s'inquiéter des changements.