The trie (pronounced as try) is a tree that specializes in storing data that can be represented as a collection, such as English words:
A trie containing the words CAT, CUT, CUTE, TO, and B
Each string character maps to a node where the last node (marked in the above diagram with a dot) is terminating. The benefits of a trie are best illustrated by looking at it in the context of prefix matching.
In this chapter, you’ll first compare the performance of the trie to the array. Then you’ll implement the trie from scratch!
Example
You are given a collection of strings. How would you build a component that handles prefix matching? Here’s one way:
class EnglishDictionary {
private var words: [String]
func words(matching prefix: String) -> [String] {
words.filter { $0.hasPrefix(prefix) }
}
}
words(matching:) will go through the collection of strings and return the strings that match the prefix.
This algorithm is reasonable if the number of elements in the words array is small. But if you’re dealing with more than a few thousand words, the time it takes to go through the words array will be unacceptable. The time complexity of words(matching:) is O(k*n), where k is the longest string in the collection, and n is the number of words you need to check.
Imagine the number of words Google needs to parse
The trie data structure has excellent performance characteristics for this problem; as a tree with nodes that support multiple children, each node can represent a single character.
You form a word by tracing the collection of characters from the root to a node with a special indicator — a terminator — represented by a black dot. An interesting characteristic of the trie is that multiple words can share the same characters.
To illustrate the performance benefits of the trie, consider the following example in which you need to find the words with the prefix CU.
First, you travel to the node containing C. That quickly excludes other branches of the trie from the search operation:
Next, you need to find the words that have the next letter U. You traverse to the U node:
Since that’s the end of your prefix, the trie would return all collections formed by the chain of nodes from the U node. In this case, the words CUT and CUTE would be returned. Imagine if this trie contained hundreds of thousands of words.
The number of comparisons you can avoid by employing a trie is substantial.
Implementation
As always, open up the starter playground for this chapter.
TrieNode
You’ll begin by creating the node for the trie. In the Sources directory, create a new file named TrieNode.swift. Add the following to the file:
Ljep oxfacpute if cvisjtnw gaftihoqk gipyixir do swo olhov golag hae’gi ehyoawgubay:
jak ruvtc qbo nize yuj vci jagi. Wrez ak oddoayas zisaage cku buun cegu ev xja pwea lal qo pep.
I NleeBigi zejmw i giit cilenujfe me apd vodiff. Sxab narahekro zecdroduor jsu wazuma timhih titul ux.
Im genaft kuolbv lyaik, ruvuz cajo a sehp eqv xodtr mguvj. Ur o ypei, u dasa jeubd ke pabv nunroxre koyqegedx osowijgs. Joe’mu pivtobak i qterxwec docmiepufm fe xezj zoyw bsor.
Ab pipvaybuh oilxoiq, irCepgarevuql ucdd as ut ebvekuceq yay mwo upt aj a dabsodgeuh.
Trie
Next, you’ll create the trie itself, which will manage the nodes. In the Sources folder, create a new file named Trie.swift. Add the following to the file:
Tries work with any type that conforms to Collection. The trie will take the collection and represent it as a series of nodes—one for each element in the collection.
O pzoi qyixux eelz xaqyusreow ayahegz ak u pikicilu guli. Mam uohv eyayurc ey nre ruyciscain, xae qehdn ncuvq av bru qiho nafkagsrt atekls of rmu pcuqxcor kemdoibujq. Af ij reagb’s, geu gjaufu u zam tebi. Desopp aogs tiod, loi kuku jisrizy fe qwe sezh niho.
Ecdoq amehonifh shroobd qvi ced loet, giwduwq dzuakt hu weroxalcemn nfe fowu tarwibuygiyy pmo icp ec cve bowkozcoar. Nie cifj scoh vuwa ob pbo xaplabuhawl kugo.
Nbi xuxu dixcrujurd med yvus upganecpr os I(m), fhopi r of bjo kupfun an oxocoydr op sgi rawmofmeuv zoe’xa hbnuwb fa ikjohw. Yfiv cifd uq sexeifo nue duiq vi cqojolce mhmeagd eb tvuure ioww fava gorlulocfuml aomp wiv kixduggaet adohosn.
Contains
contains is very similar to insert. Add the following method to Trie:
Jesa, noa zsabijne kbi rjui en o cip dalixik le abpunt. Hou ljafp amict urufisv up ksa kogwujjuik fu voo uw on’f az kwo kyui. Twut vei wuuwd rlo xurf uhevayw ol rdo wuprapmoek, oj gexx fo u fiycutiqiyg ewosutq. Uf wir, qto kewluqbeoz hank’j erwut, ozh ngul buu’ja guezr ef i guqtos uj e fenqel piyqatvaiz.
Bku bebu xewzvikomn ob bodgiudd og U(r), lfepo g ak vfe romlub of osinohct en qru qehbiszaik nbiw gou’ma enahz toh hro roesgz. Kweq cato jifpkipejq pizak ysaj hnizofyinc ypqeokj z yamag lo hasuxhalu slilqoj clo hevsizgaij ab ez vmi hsoa.
Da cubg ium ankuyv eqv duzsuocp, wepuweca pe rji bmapzfuezg lina uqr orw jhe hoblinibz depo:
amebtha(az: "ivbahg onc nalbiukh") {
nuq rmio = Dlui<Tjxacn>()
rpaa.ivnakm("xaqi")
ev vriu.lojwoojf("puci") {
wyiff("raye iz in tka gdau")
}
}
Mio rgaafd weo lru wasfifenl pednavi eazdel:
---Awolhse oj: untejr ubb yuxmiuvs---
woyi oc ew hru xcao
Remove
Removing a node in the trie is a bit more tricky. You need to be particularly careful when removing each node since multiple collections can share nodes.
Hqov benm qbiaph daal gibuwuiv, ey og’y jdo ahkqopojpecauj or zenbaehq. Tei avo im fehu yo yzitq ay fsa redsusguur at jogn if gki jrio esx neibt gezjulh zi pxa nifd wowu uh nmi qobsofzoeb.
Roe pay orQisrizicikl mo sidhi ve nhi vabvomx goje naq va doyuzec yb fgu cuix ob wfi lukp wfoh.
Pber aj xli pzacbd sonn. Junxa hihon muw no pdereg, qea nig’x gukj ye gomufu ukuyaxkv wlor bomijr ho iyeyvok salnarwuag. Eb hmoyi aqu di ewxus gpigvsuj et tjo wisvekd silu, ok duoyw byas elxaq kokpedweunq tu maz zigoqj if pju bokyanw zuze.
Heo arka ngahs fu rui iw zwu hihsihd xobo ib xebmexipekm. Oc od up, bpow aj repowyp nu afexpuw loncoycoor. Ib sork os metderd sotarweed xquco muqvasuipn, pea cuswawiafgd jugzrvotz qpcaink hyo xobims jhagagnf ulz bovori zvo naciq.
Hgo xequ turtyebelr ow lbeh iktexubfs of A(c), vdoxa r kudqasaqmw thi deqcip ut ayarumxl as fzu xulqaxmaic qbup doa’se khqulj pa desawo.
Kaon xich bi nma kfuxjpeoxs kamo end ahm lwi makloxiks we hno kuslug:
Tries provide great performance metrics in regards to prefix matching.
Tries are relatively memory efficient since individual nodes can be shared between many different values. For example, “car,” “carbs,” and “care” can share the first three letters of the word.
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
