streamalism.org

1. Overzicht

Datastructuren vormen een cruciale troef bij het programmeren van computers, en het is erg belangrijk om te weten wanneer en waarom ze moeten worden gebruikt.

Dit artikel is een korte inleiding tot de gegevensstructuur trie (uitgesproken als "proberen"), de implementatie ervan en de analyse van de complexiteit.

2. Trie

Een trie is een discrete datastructuur die in typische algoritmecursussen niet zo bekend of algemeen genoemd wordt, maar toch een belangrijke.

Een trie (ook bekend als een digitale boom) en soms zelfs een radixboom of voorvoegselboom (omdat ze kunnen worden doorzocht op voorvoegsels), is een geordende boomstructuur, die gebruik maakt van de sleutels die erin worden opgeslagen - meestal strings.

De positie van een knooppunt in de boom bepaalt de sleutel waarmee dat knooppunt is geassocieerd, wat pogingen anders maakt dan binaire zoekbomen, waarin een knooppunt een sleutel opslaat die alleen overeenkomt met dat knooppunt.

Alle nakomelingen van een knooppunt hebben een gemeenschappelijk voorvoegsel van een Draad geassocieerd met dat knooppunt, terwijl de root is geassocieerd met een leeg Draad.

Hier hebben we een preview van TrieNode die we zullen gebruiken bij onze implementatie van de Proberen:

openbare klasse TrieNode {privé HashMap-kinderen; privé String-inhoud; private boolean isWord; // ...}

Er kunnen gevallen zijn waarin een trie een binaire zoekboom is, maar over het algemeen zijn deze anders. Zowel binaire zoekbomen als pogingen zijn bomen, maar elk knooppunt in binaire zoekbomen heeft altijd twee kinderen, terwijl pogingen 'knooppunten daarentegen meer kunnen hebben.

In een trie slaat elk knooppunt (behalve het hoofdknooppunt) één teken of een cijfer op. Door de trie van het hoofdknooppunt naar een bepaald knooppunt te doorlopen nkan een gemeenschappelijk voorvoegsel van tekens of cijfers worden gevormd dat ook door andere takken van de trie wordt gedeeld.

Door de trie van een bladknooppunt naar het hoofdknooppunt te doorkruisen, wordt een Draad of er kan een reeks cijfers worden gevormd.

Hier is de proberen class, die een implementatie van de trie-datastructuur vertegenwoordigt:

openbare klasse Trie {privé TrieNode-root; // ...}

3. Veel voorkomende handelingen

Laten we nu eens kijken hoe we basisbewerkingen kunnen implementeren.

3.1. Elementen invoegen

De eerste bewerking die we zullen beschrijven, is het invoegen van nieuwe knooppunten.

Voordat we met de implementatie beginnen, is het belangrijk om het algoritme te begrijpen:

1. Stel een huidig ​​knooppunt in als een hoofdknooppunt
2. Stel de huidige letter in als de eerste letter van het woord
3. Als het huidige knooppunt al een bestaande verwijzing naar de huidige letter heeft (via een van de elementen in het veld "kinderen"), stel het huidige knooppunt dan in op dat knooppunt waarnaar wordt verwezen. Maak anders een nieuw knooppunt, stel de letter gelijk aan de huidige letter en initialiseer ook het huidige knooppunt naar dit nieuwe knooppunt
4. Herhaal stap 3 totdat de sleutel wordt doorlopen

De complexiteit van deze operatie is Aan), waar n vertegenwoordigt de sleutelgrootte.

Hier is de implementatie van dit algoritme:

public void insert (String word) {TrieNode current = root; voor (char l: word.toCharArray ()) {current = current.getChildren (). computeIfAbsent (l, c -> nieuwe TrieNode ()); } current.setEndOfWord (true); }

Laten we nu eens kijken hoe we deze methode kunnen gebruiken om nieuwe elementen in een trie in te voegen:

private Trie createExampleTrie () {Trie trie = nieuwe Trie (); trie.insert ("Programmering"); trie.insert ("is"); trie.insert ("a"); trie.insert ("way"); trie.insert ("van"); trie.insert ("leven"); terugkeer trie; }

We kunnen testen dat trie al is gevuld met nieuwe knooppunten uit de volgende test:

@Test openbare leegte gegevenATrie_WhenAddingElements_ThenTrieNotEmpty () {Trie trie = createTrie (); assertFalse (trie.isEmpty ()); }

3.2. Elementen vinden

Laten we nu een methode toevoegen om te controleren of een bepaald element al aanwezig is in een trie:

1. Haal kinderen van de wortel
2. Herhaal elk karakter van de Draad
3. Controleer of dat personage al deel uitmaakt van een subtrie. Als het nergens in de trie aanwezig is, stop dan met zoeken en keer terug false
4. Herhaal de tweede en de derde stap totdat er geen teken meer in het Draad. Als het einde van het Draad is bereikt, keer terug waar

De complexiteit van dit algoritme is Aan), waarbij n staat voor de lengte van de sleutel.

Java-implementatie kan er als volgt uitzien:

openbare boolean find (String-woord) {TrieNode current = root; for (int i = 0; i <word.length (); i ++) {char ch = word.charAt (i); TrieNode-knooppunt = current.getChildren (). Get (ch); if (node ​​== null) {return false; } current = knooppunt; } return current.isEndOfWord (); }

En in actie:

@Test openbare ongeldig gegevenATrie_WhenAddingElements_ThenTrieContainsThoseElements () {Trie trie = createExampleTrie (); assertFalse (trie.containsNode ("3")); assertFalse (trie.containsNode ("vida")); assertTrue (trie.containsNode ("leven")); }

3.3. Een element verwijderen

Afgezien van het invoegen en vinden van een element, is het duidelijk dat we ook elementen moeten kunnen verwijderen.

Voor het verwijderingsproces moeten we de volgende stappen volgen:

1. Controleer of dit element al deel uitmaakt van de trie
2. Als het element is gevonden, verwijder het dan uit de trie

De complexiteit van dit algoritme is Aan), waarbij n staat voor de lengte van de sleutel.

Laten we de implementatie snel bekijken:

public void delete (String word) {delete (root, word, 0); } private boolean delete (TrieNode current, String word, int index) {if (index == word.length ()) {if (! current.isEndOfWord ()) {return false; } current.setEndOfWord (false); retourneer current.getChildren (). isEmpty (); } char ch = word.charAt (index); TrieNode-knooppunt = current.getChildren (). Get (ch); if (node ​​== null) {return false; } boolean shouldDeleteCurrentNode = delete (knooppunt, woord, index + 1) &&! node.isEndOfWord (); if (shouldDeleteCurrentNode) {current.getChildren (). remove (ch); retourneer current.getChildren (). isEmpty (); } return false; }

En in actie:

@Test ongeldig whenDeletingElements_ThenTreeDoesNotContainThoseElements () {Trie trie = createTrie (); assertTrue (trie.containsNode ("Programmering")); trie.delete ("Programmering"); assertFalse (trie.containsNode ("Programmering")); }

4. Conclusie

In dit artikel hebben we een korte introductie gezien van trie-datastructuur en de meest voorkomende bewerkingen en hun implementatie.

De volledige broncode voor de voorbeelden die in dit artikel worden getoond, is te vinden op GitHub.