Schlagwort: Trie

Double Array Tries (Teil 4)

In den ersten drei Beiträgen dieser Reihe wurde das Thema Löschen aus einem Double Array Trie immer wieder umgangen. Eine kleine Sünde, die in diesem Beitrag nun endlich ihr Ende findet. Außerdem wird die Einsatzmöglichkeit des Trie erweitert, in dem eine Map Implementierung basierend auf dem Double Array Trie Algorithmus vorgestellt wird.

Weiterlesen

Double Array Tries

Seit Jahren schaue ich mir immer wieder mal den Artikel „An Efficient Implementation of Trie Structures“ von Aoe, Morimot und Sato an. Es ist eines meiner Steckenpferde, obwohl ich selber keine eigene Implementierung in Java beendet oder jemals Tries in meinen Projekten verwendet habe. Ein Trie ist ein Suchbaum, dessen Zweige Zeichen repräsentieren und jeder Weg von der Wurzel zu einem Blatt eine im

Weiterlesen