Tries voor prefixopzoekingen

Een trie is een boom waarin woorden worden opgeslagen door gemeenschappelijke voorvoegsels te delen. Daardoor kun je vragen over voorvoegsels razendsnel beantwoorden. 🌳

Een verzameling kan volledige woorden opzoeken, maar met tries kun je ook vragen over voorvoegsels beantwoorden, zoals: begint een woord met pre?

Elke knoop is een positie in een woord en elke kant heeft als label een teken op het pad vanaf de wortel.

In Python is de eenvoudigste knoop een woordenboek dat een teken aan zijn kindknoop koppelt. Eenvoudig en flexibel.

Om een woord te invoegen, loop je teken voor teken door het woord en maak je een kind aan zodra dat ontbreekt.

Stel na het invoegen een vlag voor het einde in, zodat je een volledig woord van alleen een voorvoegsel kunt onderscheiden.

Om te zoeken, volg je de tekens; ontbreekt er een stap, dan staat het woord er niet in. Controleer daarna de vlag voor het einde.

Een vraag over een voorvoegsel doorloopt dezelfde route, maar je slaat de controle van de eindvlag over. Als je de laatste knoop bereikt, is het antwoord ja.

Invoegen en opzoeken kosten O(L), waarbij L de woordlengte is, ongeacht hoeveel woorden je hebt opgeslagen. Alleen de lengte telt.

Sla bij elke knoop een teller op, zodat je meteen kunt bepalen hoeveel opgeslagen woorden een bepaald voorvoegsel delen.

Tries vormen de basis voor automatisch aanvullen, woordenboekcontroles en problemen waarin je de maximale XOR van bits zoekt. Ze zijn vaste prik bij tekenreeksopgaven in wedstrijden.

Je kunt nu een trie bouwen, invoegen en zoeken in O(L), en snelle vragen over voorvoegsels en aantallen beantwoorden. 🌟