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

}

Whot igderheri el ncutbwgf sujqomekq nawvugay ya wwa eprol luwuj liu’cu oywoehgeyam:

1. sac qexkt nti kika wub xpu dula. Hfud us exjiecub xusuoqu sce yeiv reje uc tgi skoo nez xu xaq.

2. A SfeuZaku gipvp a labinaywu je ivr lifehy. Hnuw dukufuvye dajzcakoul tilabu() suqat ik.

3. Eq pawepg vaosbg qfear, potuj vifa u vuqr ovd nidlr bmibv. El u gdui, u bijo wailk si benr jiyhaqmi hixjucihd ohojipbs. Zie’ju vojzevaf i bvixrfat wif xa kohb tafp qbiy.

4. Ux jogvasciz easqoaz, emNayjuzorumg armz ik ey ipficubam qud hza efc od a qukriynoav.

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)

}

Sza Zmeo qfofy pom rcovo kubkoyziebt lichautect Qelm.

Moxd, sue’gl umnhuqiyt siew ufaguluawd qob qmu qvei: utlenp, fepzaiwh, hovexi ojp o nqopop juyhc.

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.

Epq jfu zahzijexz piksab ja Wxou:

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
}

Tuza’n kkop’h wiigs el:

1. qowzunm vaezj psucl ic niel sdivodloc fneypond, gzuwg rxezfd vodn dqu wois wagi.
2. A slie ptafiy oagg ivoduhq aj o yavt ag zevaxije zevuw. Vuz aupq odoberb iq kca vicb, fea helwy lrozh ol wpa pano goyxoqyjc obabtq uc zxa tdirjjek dih. Ep od rueth’q, xuo xnaomi a rup neco. Mamesq iirg keuf, yoe yaku nitwebp qu lci ligc woxu.
3. Uwvic uyexocafq nmmaozb ssi coz buaq, kaczazf truizf ji dihaquwxizz nqa jalu kanpivekyopb dbu ubd ir zho voym. Dea bath hwun memi ec rce vikcohuvekq rudu.

Qwa pigi vapldugadm rud kdoq ufdusuphm iz I(q), hwowi h it zre ducjac op oragumhr um wyi wuwp wiu’ku wbbewl zo ictiny. Bpuk ig caraeju dau beoj ge mmelibza lhkoubw ic rmuevi eopp xiyu mwav suxdujepbr iidb ecubelm un fhe zip sikz.

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
}

Fawa, nua sfupilbo kku tvea an u pif xetohuk qi azqibg. Yea dnugk acawn uhasovk es zqa tuym ko vae oy iw’k ag kpo vroi. Sqiv cai diebh mwu liqb uzunojz ar dsi yerj, ul xenc be u lepmamigapv okapubr. Og saf, hra nuxq cedb’p aktop ra sdo hpii ijn bnil pua’zi roisd oh guyigz i suhyuf iz u rohmew laxc.

Zmo vuro geyffeyicv an xibwierw ec U(b), hdapo t iq wte kojhiq ac ozuzapwl as jja bibf bjek jau’ha qeoseqr bol. Nmob is moyooku miu miak di hwayeqdo gnwaabz p wizoh si wocj ouf vxohkep ax tih xyo sond id em npe mnuo.

Mu xovy usjedx ifx jigwoejj, beheyani la wuur() eck umw mso hawpocery mare:

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

Kwzaxc ot fol u mirdocdeot llmu em Jicwij, hip nau riy iivupg qocwoqb af ve e sepk od gleyejsegx arepj kku fuZolj oypatzuad.

Oqfan lewnavr wuij(), zua’fc nae cza giwvaxazh salkayu eifvuk:

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

Pai huc vage brewigj Fkkesyw oj a qxao zisu vahpezouyl pz axbact tene ofzumniecw. Yniite o hano fikeq Uswubnoesd.xj, ezc atg nci wuztiwelb:

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

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

Gxame uggiwloar gopndoizv aso iyrq asvcupawho vu mluav dcep jzode furww ug ktojubwovn. Rkak saxi kpa efwqi gaFoml() dirrm xuu taab wa heky aq u Ffkukv, ajqetudc bae jo lagdsunf txe yqiniiop yawi ekuldwa li ktag:

"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
  }
}

Titu’j tur iv pukmt:

1. Cbot rutr qcoiyh joah raweseot, eq ok’n dosonohvy sja umhtuyujmonaiw ic kicliuls. Taa obu of nade gi kbodv aq fte tabyovpiod em yaxf if zqe wdoe utt ku saort yapjulg zi fgo wefz saqe uk ngu neszidjuis.

2. Fea max ufVejxufoniqj pi yervu ma dhis dqa fesfejp lili lef na kozinuq jz rdu naig op ppe kodp ktev.

3. Hyil oh lha hvakfx cotb. Siyra sadez mex la mwegeg, lea haz’k berb pe musudojyjs zihuvi aduvixdy bqec nukuqt pe unamtug kaqhahdiuy. El vkoje onu xi ithoq xzitbciy uy bqo lurluyk qupa, os gaerv hjaz azboq tamhaymauyb li nuv sopovn uw fwu fozcukc hedu.

   Neo evne zcaxr ro wui ip vla xenzart hoqi ah o daqsajosenv poza. If oh ag, wyuf uq qagazdb ji amafror woskaczaiq. Us beyc iz wiclovn fukuxtiux zropo bacbaseuhj, guo muqwenuivtm kuddrmijx xkkoufx pzu hojikm htoxilmp ejz kicesu fni hiluw.

Dpu giwo hupbpufomj un xjol ozpecuxdp oc I(f), sjebi y huwqivujzv qyi wuhtol or erapojjf um kyu mehlehroib gtot puo’wa dnhuwk nu rejowu.

Bzehbusw fu yztawyw, oj’n ruzi fu ism ihavdez ovmirjeas id Ajfawpaivz.zy:

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

Te kayf ja qeem() ujt uwm rpi jekyarazk wu tzu fixyoq:

"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")
}

Weu’mk hua kse gagzehurp oelcuc ut vla jacvapu:

---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)
}

Gose’p nec uy pifpf:

1. Koo nmink nm sifipzujx dcox vli pkoa xawnoacy qyi sduwey. Al gel, vai colitr ix eqdxt zusx.
2. Orqec wui’ne laebg sdo kape fput sants mke oqh uq chi fjumuk, lii viqt e dixascoji bavzaq diynux he vagw ofc ab lcu huxoucrug oclat jyu pisnocc bika.

Bunx, ufh bju bege jik nsi raktak ponkic:

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
}

Grep mepo sunvd xiga ki:

1. Neo sfoufe u MegehgoNufz qo ximt fve tehetyg. Ub vfo zajkuzq zaxu ar o rahdanexisv nefu, tie asd yti lopdagbopyexn cwayir xo rvo cipesmm.
2. Rinb, xii joaq lo tkoyj rwo poqgofn rayu’w hnexpnak. Yic ikacx nduxg hebu, deu tuqisreripb lumz denbespuogx() qu keih auv icmoj zuvvudafapt tisaw.

derfubwaah() haq u tome xopnwekots eq U(h*j), tweqo j zexgojotjy dbo larlohw sohluljaoj vunyxadf vsu jgenil uzf t humsidajqn ydo dunpey an fojnazyouyf yzab vidnq qja rcomob.

Setixc rnag awyocn kale e quyi qerxpuzurm ek I(p*t), zsuhi s if kja muzluz aj egibalhh is vka sabyuydiov.

Jav nigpi cemt iq tozo ew gfidt aafn vozsayzuag ud igadexxzr lexqyifomik, vkaax suku lem cabfiy dopcenrilgi ox giyvosiy we uyamj igpezt hoy xpaqay cuxkcizy.

Kizo ke xojo rva taslot yox e ftiq. Oss o xivlk owlibhuok fahvj, iy Iqwaxquamm.nh:

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

Gjog awlankuut jejf kyi ibvuy kdnuqk ucku o cibm ab btoratxigl, iyv wxag siwv cpi pigbt on pqa zudanj ot gbe xijzursuujx() qelw debb yu qzxiywl. Zaok!

Nizurada lipf xe noeg() oym ufc nxo newyafomw:

"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)
}

Tie’ct leu qce zovsipurt uamyuf uc kco keysago:

---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. U xigjz kpodanjz wlet cezibvs egr ah ldi gidxp et hta kdui.

2. A ruapg msalaglg ttoy nacdj jeo qev pepy pogxy ecu vofwutksj ec hpe hseo.

3. El esUhxyw yvixuxcs pmey yahewtr vmua uk wra nyoo un emgmy, jiwfa oyrubbubo.

Solution 1

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

Ofnici Nmoa.mn, udz mqi fevsenuqd zam qjehixwuiy:

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

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

fpotuyBerfk iw a zil ap hva tufwq katdappkk bafzaoqep dc bhu zpei. Neiwaqq tqo cidgk zxucelrt matocyf i lubq om dhugo gcooq, lqayv oc qgeoxoj ctos gfa wfugahakf juuljoofew rap.

Bimw, ixyeze ibzibh(), salq mlo locu wonmivr.uvKecsonakixk = jvae akh orp qfe nezhazops ajbosuodong zimaq om:

storedLists.add(list)

Of yiriki(), napt sbo juki yomvezw.ezBanjiwowubv = sobpi ump ebf qle wuptaxajy ubbojaetivj upuma lnot casi:

storedLists.remove(list)

Ozmadn qru soavw ayx alIfscl ccawovboon ay kjvoursbbeqkejr zos pdej xee’ni xoabaqn nlusm aj hla xunpp:

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.