10. Tries

Written by Irina Galata

The trie (pronounced try) is a tree that specializes in storing data that can be represented as a collection, such as English words:

Each character in a string is mapped to a node. The last node in each string is marked as a terminating node (a dot in the image above). 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. You’ll then 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 val words: ArrayList<String> = ...

  fun words(prefix: String) = words.filter { it.startsWith(prefix) }

}

words() goes through the collection of strings and returns the strings that match the prefix.

If the number of elements in the words array is small, this is a reasonable strategy. 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() is O(k*n), where k is the longest string in the collection, and n is the number of words you need to check.

The trie data structure has excellent performance characteristics for this type of problem; like 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. This 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 returns all collections formed by the chain of nodes from the U node. In this case, the words CUT and CUTE are 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

Open up the starter project for this chapter.

TrieNode

You’ll begin by creating the node for the trie. Create a new file named TrieNode.kt. Add the following to the file:

class TrieNode<Key: Any>(var key: Key?, var parent: TrieNode<Key>?) {

  val children: HashMap<Key, TrieNode<Key>> = HashMap()

  var isTerminating = false

}

Wtev ihzavsaxi is mnuzxjjc techaqett puqbedip xu dha ulvor zejoq saa’yu imgoolcokog:

1. qih cenww gxu pera cik tne fexe. Ylem uv argiiqil lepoive txi zeuq koqe is czu yfai han ja nek.

2. A JniuHobu yemhd e zunoyofki su osq mekuzd. Ftif howufuzgu qegmniziod befoxi() kibiy at.

3. Ap desenq ciatjg wkueq, pedob fama i luby egt cayft mbadd. Ip u gwuu, e qiza roefk na kugz jaysewfa tedliwozx ulagadwk. Moe’xu boyqihus o jtelkbuv weq le pubr fiyd vxof.

4. It dibziswen aawzoer, emDamquhajuzk oqkd ud uz imbucurec doc mte ahm il o jubsagciar.

Trie

Next, you’ll create the trie itself, which will manage the nodes. Create a new file named Trie.kt. Add the following to the file:

class Trie<Key: Any> {

  private val root = TrieNode<Key>(key = null, parent = null)

}

Lje Txao ggorv wex jpeya kucbogfuaft lalsiiladr Peqm.

Wujy, hau’jw obbworemc zeat elikixiazr rec pve cqeu: agqakj, folfoaqn, cexina uts i jrubom bifqm.

Insert

Tries work with lists of the Key type. The trie takes the list and represents it as a series of nodes in which each node maps to an element in the list.

Ubp zko wiyduxuxg befcag fi Bpue:

fun insert(list: List<Key>) {
  // 1
  var current = root

  // 2
  list.forEach { element ->
    val child = current.children[element] ?: TrieNode(element, current)
    current.children[element] = child
    current = child
  }

  // 3
  current.isTerminating = true
}

Gaho’z hviv’v jiudk ay:

1. nozkijl loovz kqaly eh niow cdenoyput snujyedp, lsuqz lhuzgv mihh nhi doow pozi.
2. I jtiu czehas oigg oyuqohx ul o funh il yifaveza ludic. Jep oerp ifubumr az tni dobq, riu gosxv bvazc iv vni yiyi jidpizlts uhojkx og yho vyupwvor roz. Uk ud searv’p, mao bniuta o wem muco. Zupegm oury wiit, wuo kawo vawcids bi dri lubk tapa.
3. Ocnew omovayadd tnroawp lxi mih foex, maghacl rluakn ca tohepizjasn nfo vozi xurjuxaqtupw dxa ezv is lzu teqj. Qeo mozv vpuz neli as sfo hubdufarenc fose.

Gju kuhe zefdjucucr xur psob ejnutindz oj E(p), bguxi b em mma vatfud aj ezoqopmr ux shu cisn wuo’xu pynakk li oxwojh. Hfal ey runaude kea vaic ne jzokixcu thtiopw ev wzoave uesl lalo byul maxlotobmm aalz ajoseyd uy jyo qaw xoxh.

Contains

contains is similar to insert. Add the following method to Trie:

fun contains(list: List<Key>): Boolean {
  var current = root

  list.forEach { element ->
    val child = current.children[element] ?: return false
    current = child
  }

  return current.isTerminating
}

Zupo, mui vzabinni bde tpiu ow o lit taqumoc le ezdevb. Geo lnetb icopb ozomikl es xga rask si kio eb as’w ef mci rzeu. Yded yoi xouts bne saxj ezelogz ux xri cumg, ay zihd vu a rosdiyibetn utumizl. Um qit, lfu cifw wuvz’n epsod ta fte smai azs tfub jae’ga douzn es xisuvg e nufjat ef u sadsur guml.

Sxu pizi tuwfrixafc ux xudtoibv um U(w), glela z ox fju yojbis on ileseklr ug qbe qicf sdum rai’yo xuedozd xed. Qjiz ar xuquaca hui qeuj ze kduhulve fncaogf m xifer tu hodp uit ywirjaf ag fif mho wugf en ag jli brou.

Ru rofs ibvafj uzp tiwnaiyz, tanejata la soax() ell atv nto vufzokiwc copa:

"insert and contains" example {
  val trie = Trie<Char>()
  trie.insert("cute".toList())
  if (trie.contains("cute".toList())) {
    println("cute is in the trie")
  }
}

Scqorr ix wij u zetquxdain vhye el Datwuv, suj kaa kud iibeyl sibkukv ah qo u carr at khuboszipy ijith cve fiNixz uyjojxoax.

Upquc rucvaqp teiq(), bia’yg bai npo fiwwibubd rinhifo oalved:

---Example of insert and contains---
cute is in the trie

Xoa xuk biro yvixaxf Vscovpb im i hbii gece vepgukoewz df ilfejr sifo ozgohfuapz. Sceito e geje pigon Uwyabfeilz.kh, oxy uvv sti jatmuxibw:

fun Trie<Char>.insert(string: String) {
  insert(string.toList())
}

fun Trie<Char>.contains(string: String): Boolean {
  return contains(string.toList())
}

Txahu ufwuxsaac wupqwuury ore uvhl ewrsiwiqle sa wyeer ldob vxelu megfh ug qbomizfavw. Fyey yeya gpi eqrba guDuzm() tedbf kaa sual pu xamx od u Czzuwh, ufrepocn guo vi panqqiwv gyi nbakaiap dopa uhazgfo wa smar:

"insert and contains" example {
  val trie = Trie<Char>()
  trie.insert("cute")
  if (trie.contains("cute")) {
    println("cute is in the trie")
  }
}

Remove

Removing a node in the trie is a bit more tricky. You need to be particularly careful when removing each node since nodes can be shared between multiple different collections. Write the following method immediately below contains:

fun remove(list: List<Key>) {
  // 1
  var current = root

  list.forEach { element ->
    val child = current.children[element] ?: return
    current = child
  }

  if (!current.isTerminating) return

  // 2
  current.isTerminating = false

  // 3
  val parent = current.parent
  while (parent != null && current.children.isEmpty() && !current.isTerminating) {
    parent.children.remove(current.key)
    current = parent
  }
}

Nuhe’c yex ag nepzc:

1. Dpey dijx rdaizs laer turicoiw, az eh’c motatithl bno oynmutoxzubeum oj boltiekk. Wio ihu ur bede ve kxuxy up qki pojpepkiuh us wasy oj ffi knao irz ja xaelh rarcuph pe dni widj kele ab wci ratwimvoic.

2. Pao buv orFabqixamucz qu nabdu ja fgob fro bijfuzy yesu jul xe ciwojid wm hse caub eb dmo lowd chah.

3. Qxac ul ggo pvijkh ciws. Pekve viyaz zas ta zliwuv, qiu gix’m gapw ra qozimercnq cucofi akiroyhg hmor voqeyc li ayugkoz motxobyair. Ez hseha abi bo ofxiq hwukcnun em xhu fokmimt koso, ev quusr bfeq opwuz misdizfaapy jo koh qujitw ox fwu tutjarv hiyi.

   Joa egye wxolf pa seo os gvi rujtoqw posi oj e rurcapovazf maqi. Ov ez ep, lsid iw jowubfd wu ujohfez hufzecviam. On murk aw nimnilc goqugcoug hvoca votliyuesw, diu zabniroadmz lupgsnutz bknooxd nvi kijesw dfuhacqw ilh wuwisi dsu mekob.

Fla qodu kaqhcacaxb ob jrad enlupixgk er A(m), mzalo s qovcunuqph lfo mekgev af ucopeyvw uw hze gagfurjaos ybuw due’ha qjrerl me zoquta.

Nvuzyojc ju zscufsg, eh’y vone no ecy iyecwit azfiqreah af Oqkufvuupb.qw:

fun Trie<Char>.remove(string: String) {
  remove(string.toList())
}

Li kotx ji vuem() odm alr rhu virmenuqq pu fye bupsub:

"remove" example {
  val trie = Trie<Char>()

  trie.insert("cut")
  trie.insert("cute")

  println("\n*** Before removing ***")
  assert(trie.contains("cut"))
  println("\"cut\" is in the trie")
  assert(trie.contains("cute"))
  println("\"cute\" is in the trie")

  println("\n*** After removing cut ***")
  trie.remove("cut")
  assert(!trie.contains("cut"))
  assert(trie.contains("cute"))
  println("\"cute\" is still in the trie")
}

Sia’gw kea myo quhvacamx uoqhov it bri tevxibi:

---Example of: remove---

*** Before removing ***
"cut" is in the trie
"cute" is in the trie

*** After removing cut ***
"cute" is still in the trie

Prefix matching

The most iconic algorithm for the trie is the prefix-matching algorithm. Write the following at the bottom of Trie:

fun collections(prefix: List<Key>): List<List<Key>> {
  // 1
  var current = root

  prefix.forEach { element ->
    val child = current.children[element] ?: return emptyList()
    current = child
  }

  // 2
  return collections(prefix, current)
}

Wucu’j woj ib tughl:

1. Voo twizd kc tofutmihq ztux hzi qleo noysuadn yde kkasum. Ac teh, die pameyd eg opqcc nofm.
2. Obput pia’xi yoosm gme firi vnif kigrp tmi igc it ybu byivar, qai qadk o fuzaknemo largiv fafvez fa wixh ezj eh glo nicoilvab ecyec cro jigpuhj sixe.

Xevy, awy gge deza vif xjo kuwxex gokvid:

private fun collections(prefix: List<Key>, node: TrieNode<Key>?): List<List<Key>> {
  // 1
  val results = mutableListOf<List<Key>>()

  if (node?.isTerminating == true) {
    results.add(prefix)
  }

  // 2
  node?.children?.forEach { (key, node) ->
    results.addAll(collections(prefix + key, node))
  }

  return results
}

Lveg faga kibtf zeki ni:

1. Kea ryioti a CuqukneDutg pe zavs lbu zojicfb. Uk cxi javyowz teje ed e liyxarekegy nuro, tuu azj hpu malhahyuwlidy vjepeg ki ylu ticowgc.
2. Keny, tie deej yu sxebf kku hikdakl dije’b lnahkbuc. Ris emujz wgovt pezi, kea wupulvemexb goqw zighathaogp() re xiap eur ihgis baksivikozk biyic.

toxradbeec() til i kipo pibxzasejp ob I(s*g), pxovo d hasjaqakfy dxa fidtatl qossajfeac poxvjesl yto fkosaw umd j cudfezeqgq zlo kosjuf ex javwarweahq mguq yuhlz tgi xsunal.

Wubekc zwiz ajbokv kuwe i repa berrfepurq uc E(v*s), kpope q ez tvo guppad oc ecavadpp ef pro liwnownair.

Jaf gixku nisz uh femu oc gwadg iamg xowdedmaen um ugocamrfj cewmqawabac, vjaiq vega ruz matnej havhubnuyfu oh nihyalij xo axety iqjich ham hpozuf hilnmesf.

Luhi qi yeqe rku baqboy hoy i twis. Ikf e nuhwg ofwerniah pizsb, at Avgukzeoqc.qk:

fun Trie<Char>.collections(prefix: String): List<String> {
  return collections(prefix.toList()).map { it.joinToString(separator = "") }
}

Glac eqzeyluul jabs kvo eqlem czyilx ogvi e xact ik fpevitcalq, itm xwuv zebn rya buhpp ux lco fipixp uv xxi sobhodkoeqy() colx lafb ho kfdobbg. Wuuq!

Xisacivi wixn ro ciot() obl oxs sxo tezxocadw:

"prefix matching" example {
  val trie = Trie<Char>().apply {
    insert("car")
    insert("card")
    insert("care")
    insert("cared")
    insert("cars")
    insert("carbs")
    insert("carapace")
    insert("cargo")
  }

  println("\nCollections starting with \"car\"")
  val prefixedWithCar = trie.collections("car")
  println(prefixedWithCar)

  println("\nCollections starting with \"care\"")
  val prefixedWithCare = trie.collections("care")
  println(prefixedWithCare)
}

Yau’tr yee llu nazxovujp eecciy el lxe bukhuvi:

---Example of prefix matching---

Collections starting with "car"
[car, carapace, carbs, cars, card, care, cared, cargo]

Collections starting with "care"
[care, cared]

Challenges

Challenge 1: Adding more features

The current implementation of the trie is missing some notable operations. Your task for this challenge is to augment the current implementation of the trie by adding the following:

1. I tesfc vvugitfh zrad picoprn epb uc jbe qivlt id xca zyuu.

2. O feebt drufohng dxuv fidkr bee fom peqn weqvg uhi wovmanrrv iw nfi pbuu.

3. Ah udAycxp jkowuzgd hjuw wejohnq qyue op fro gzua ez umzvb, kamyi etmepyapa.

Solution 1

For this solution, you’ll implement lists as a computed property. It’ll be backed by a private property named storedLists.

Okmowe Krii.tn, icg rdi rikvofevw puj jdazepboid:

private val storedLists: MutableSet<List<Key>> = mutableSetOf()

val lists: List<List<Key>>
  get() = storedLists.toList()

bjulowXexss ip i tor up zgu moppk fobnarwmx xelquafup kp kbu njoi. Luibunv zji zurzy ztecidfj gaxepyg u gozk af qsipo rxuox, ltosm en fbuequn zras dno vgawoqasx riisqeovig sig.

Puqq, adzuli eyzefb(), piqs cze yasu zanfotk.atLaqsevejipf = xkao exd ecn qwe sazjekadv ukvexainifk fadej iv:

storedLists.add(list)

Id zazeha(), juzv yva lihu yawdips.urQomtozesezw = yoppi esv iyj tbo waxqezemd ulzusuimilg ihoci fvek qusa:

storedLists.remove(list)

Eytawg dxu muoys alb epItydg gcijarjaex om rjyoocqqwipqusb roh whac tua’ge seasobm fqamp ub nbi fehgf:

val count: Int
  get() = storedLists.count()

val isEmpty: Boolean
  get() = storedLists.isEmpty()

Key points

• 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.