Différence entre la Tente et les Arbres?

- Je à distance rappelez-vous que tente de ne pas stocker l'ensemble des données par nœud, seul le suffixe pour le nœud parent.

Où les arbres ne stocker l'ensemble des données, mais seulement d'organiser eux-mêmes basés sur un préfixe.

Donc essaie d'obtenir de petites, ce qui permet par exemple de compresser des dictionnaires très bien.

Est-ce vraiment la seule différence?

De réelles applications je me souviens que les essais sont plus rapides dans la gamme des requêtes. Il y a même des solr/lucene trie les champs pour accélérer les requêtes d'intervalle. Mais comment est-ce possible?

Quelle est la réelle différence et quels sont les avantages et les inconvénients de la tente et les arbres?

InformationsquelleAutor The Surrican | 2011-01-19
  1. 59

    Un arbre est une structure générale de récursive nœuds. Il existe de nombreux types d'arbres. Les plus populaires sont arbre binaire et équilibré arbre. Un Trie est un genre d'arbre, connu par beaucoup de noms, y compris le préfixe de l'arbre, numérique de l'arbre de recherche, et de l'extraction de l'arbre (d'où le nom de 'trie').

    Chaque espèce d'arbre a un autre but, la structure et le comportement. Par exemple, un arbre binaire magasins une collection d'articles comparables (par exemple les numéros). Il peut donc être utilisé pour stocker un ensemble de nombres, ou d'indexer les autres données qui peuvent être représentés par des chiffres (par exemple des objets qui peuvent être hachées). Sa structure est triée et peut donc être recherché rapidement pour trouver un seul élément. D'autres structures en arbre, tel qu'un équilibre de l'arbre, sont semblables dans leur principe.

    Un trie représente une séquence dans sa structure. Il est très différent dans la mesure où il stocke les séquences de valeurs plutôt que des valeurs uniques. Chaque niveau de récursivité dit: "quelle est la valeur de l'élément I de la liste d'entrée'. Ce qui est différent d'un arbre binaire qui compare le seul cherché la valeur de chaque nœud.

    • N'est-ce pas trie comme le genre de boiteux? N'a pas d'arbre binaire battre trie, sauf pour l'espace de stockage?
    • Il y a une place pour chaque structure de données. ce sujet de trouver toutes les cordes avec le même préfixe? O(n) l'accès?
    • Ne serait pas de l'arbre le faire aussi? Nous allons avoir 1 milliard d'entrées, de trouver préfixe de 20. Trie le fait en 20 étapes. L'arbre est-il dans le lg 1B / lg 2 = 30 étapes. Maintenant, avec la même 1B entrées, nous trouvons préfixe de 40. Arbre toujours fait en 30 étapes, mais trie t-il dans 40. Avec le préfixe de 100, trie prend maintenant 100 étapes, tout arbre prend toujours 30.
    • Attendre quoi, à me Tente semblent si quelque chose de mieux. Depuis les recherches dans un trie sont O(m) dans la longueur de la chaîne, alors que, dans un arbre, ils sont O(m * log n) où n est le nombre de nœuds, car de la comparaison de deux chaînes de caractères prend le pire des cas O(m) temps, et vous avez besoin de faire pire des cas O(log n) comparaisons. Alors que Tente de faire O(1) comparaison de caractères.
    • Trie ont mieux asymptotique pratiquement toutes les opérations, depuis les comparaisons dans un Trie sont O(1) parce que vous comparez une taille constante sous-partie de la valeur, alors qu'ils sont O(m) dans un Arbre.
    InformationsquelleAutor Joe
  2. 4

    Un arbre binaire ou un bst est généralement utilisé pour stocker des valeurs numériques. La complexité du temps dans un bst est O(log(n)) pour l'insertion, la suppression et la recherche. Chaque nœud dans un arbre binaire a au plus 2 nœuds enfants.

    Trie : Chaque nœud de trie se compose de plusieurs branches. Chaque branche représente un possible caractère de touches. Nous avons besoin de marquer le dernier nœud de chaque touche en tant que nœud feuille. Un trie nœud de la valeur du champ sera utilisé pour distinguer le nœud nœud feuille (il y en a d'autres utilisations de la valeur de champ)

    Apprendre à propos de la tente de renvoyer cette topcoder tutoriel.
    https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/

    InformationsquelleAutor Harsh Gupta
  3. 2

    Viens de recevoir des idées de ce discours, même par le biais de la Racine de l'arbre utilisé dans le noyau de linux est légèrement différent de celui sur wikipédia.

    Arbres stockent uniquement les touches, ils n'ont pas stocker la valeur associée à la
    les touches.

    InformationsquelleAutor firo