Quelles sont les structures de données complexes dont vous devriez avoir entendu parler?

Question

Il s'agit d'une question dérivée, mais je me renseigne sur les structures de données que vous devriez au moins connaître pour leur utilité. Ces structures sont trop difficiles à mettre en œuvre sans une certaine expertise cependant.

Je dirais qu'une bonne limite entre les deux est un tas - vous devriez pouvoir coder un tas, mais cela vous prendrait un jour. Editer: Je vois le point que cela dépend de ce que vous faites. Je pense que ce serait génial d'avoir une liste avec une phrase résumant pourquoi vous l'utilisez!

Voici une liste pour commencer:

1. B + arbres: une bonne structure d'indexation générale sur une seule touche
2. arbre K-d: les données spatiales
3. arbre rouge-noir: auto-équilibrage BST; aussi AVL ou évasement arbre
4. liste Ignorer: bonne structure hybride pour aléatoire ou (pseudo) d'accès séquentiel
5. Trie: recherche de chaîne temporelle linéaire

Answer 1

C'est un bon début; il existe une liste complète des structures de données sur wikipedia, certaines d'entre elles doivent être examinées. Mais pour ce qui est de vous avez besoin, cela dépend de la zone que vous avez l'intention de ... faire tout ce que vous faites.

Les utilisateurs de systèmes embarqués auront des idées très différentes de celles des utilisateurs du Web qui seront fortement en désaccord avec la logique métier. Déterminez ce que vous voulez faire; les langues et la plateforme auront également une incidence sur la liste dont vous avez besoin.

Answer 2

Qu'en est-:

• Binomial Heaps
• Fibonacci Heaps
• Disjoint Set Data Structures
• Splay Trees

Answer 3

Je voudrais ajouter Hash Tables à la liste. Ils sont assez simples dans le concept, mais peuvent être compliqués une fois que vous regardez comment implémenter une bonne fonction de hachage et des méthodes de sondage efficaces.

Answer 4

Pour citer Martin Kay:

Suffix trees constituent un puits compris, très élégant, mais malheureusement des données mal appréciées la structure avec potentiellement un grand nombre applications (...)

Voir aussi : What are the lesser known but cool data structures?

Answer 5

Bloom filters

Answer 6

R-Tree

Answer 7

étroitement liée à l'arbre B + vous avez mentionné: B*-tree.Avec une approche d'équilibrage connue sous le nom d'approche «arbre dansant», ils forment la base de Reiser4.

Answer 8

Binary Decision Diagrams, spécifiquement réduit Diagrammes de décision binaire (ROBDD). Ceux-ci se réinventent (mal) beaucoup quand quelqu'un décide de créer son propre système de filtrage.

Answer 9

van Emde Boas trees. Je ne pense pas littéralement que vous "auriez dû" en avoir entendu parler, mais je crois qu'ils sont un exemple intéressant de ce genre de complexité que vous pouvez réaliser avec des "trucs", à savoir O (log log n), exponentiellement mieux que les arbres binaires!

Answer 10

Cuckoo hashing, une manière simple et élégante de résoudre des collisions de table de hachage dans le temps constant prévu.

Answer 11

Deterministic finite automata (DFA), ou finite state machines, utile pour exprimer beaucoup de choses, comme lexers de base, les expressions régulières, des transitions d'état, etc . Voir aussi le directed acyclic word graphs correspondant, qui peut être utile pour stocker des dictionnaires de manière compacte.

Answer 12

Finger trees

Answer 13

R-Tree et ses variantes, telles que R*-Tree, X-Tree, Pyramid-Tree. Diverses variantes de M-Tree, comme le Slim-Tree.

Comme souvent, l'interrogation de l'arbre est facile. Il peut aussi y avoir un chargement en masse facile (pour les arbres R, STR fait souvent du bon travail). La partie délicate est généralement la maintenance d'un bon arbre à travers les mises à jour.

Answer 14

Vous pouvez:

• y-rapide arbres
• approximative ensembles ordonnés
• tas select
• tableaux compacts
• liste Monolithic
• listes succinctes