Structure de données non-BTree où les insertions sont effectuées de manière triée, mais je peux plus tard supprimer des objets d'endroits aléatoires

Je veux trouver un objet avec O (logN) et supprimer aussi avec O (log N) - mais pas aller à mise en œuvre équilibrée arbreStructure de données non-BTree où les insertions sont effectuées de manière triée, mais je peux plus tard supprimer des objets d'endroits aléatoires

Une idée est pour cela?

Source

2010-10-10 nir

vous pourriez utiliser une liste de sauts, mais quel est le problème avec les arbres équilibrés? De plus, votre question n'est pas claire sur la possibilité d'ajouter des éléments après l'initialisation. Si ce n'est pas le cas, vous pouvez utiliser un tableau simple et simplement marquer les éléments supprimés ... – Christoph

B-tree

Source

2010-10-10 11:58:10

+1 pour avoir répondu à la question dans le titre, - 1 pour avoir ignoré que le questionneur (sans donner aucune raison) ne spécifie aucune tresse équilibrée. –

Fenwick tree

Source

2010-10-10 11:58:21

Oui, utiliser une liste de saut. C'est une structure de données probabiliste avec insertion/recherche/suppression logarithmique, mais sans le code complexe d'équilibrage des arbres.

Source

2010-10-11 06:40:59 zvrba

Structure de données non-BTree où les insertions sont effectuées de manière triée, mais je peux plus tard supprimer des objets d'endroits aléatoires

Répondre

Questions connexes