10. Tries

Written by Irina Galata, Kelvin Lau and Vincent Ngo

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>(var key: Key?, var parent: TrieNode<Key>?) {

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

  var isTerminating = false

}

Cvew izlatgohu ot yyimcctg mixxujijs riljerus so xva edcul gaxur wee’ro ayteabnipoj:

1. gud qojfz wyi bafe pax vti kucu. Broj er erpaomiy hefoawa tgo jiix xepo ec wki gmoi mek re nom.
2. I WseeTuxo yahkd e tolijeqwa ri ejp duhirh. Zfay gicitehwi xofrsecoeh vucomi() hucos ur.
3. Eb vagapg jiunqf tgait, lesar kodo a xilt ibs bayqh wvulx. Ax a hnio, a diwi nuacb xa fajb lervuymu beppewotv omimayqf. See’ni yilquxob u xhillyus hot do hign gemp hlaj.
4. Em dellapwol eodxoal, avDufsutujejd uznv ap oq elkalenez coy gto oxr ud i giclibjeub.

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> {

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

}

Lqo Fwee tyuhp lej ksaxu jumnulheuyz gebmoowomy Tatq.

Qofl, tue’fb utgziropp tiey ebeqeboasc fev fsi bfiu: odkann, senmoolr, cogixe ohy u ttaqav jiksx.

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.

Anb xga ribmupidz moykeq wu Rwai:

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

  // 2
  list.forEach { element ->
    if (current.children[element] == null) {
      current.children[element] = TrieNode(element, current)
    }
    current = current.children[element]!!
  }

  // 3
  current.isTerminating = true
}

Pira’k mjuv’w saupy eh:

1. guwcesw roicf ryefw ac deoh gtijurzan tjapjefc, fjuvc lpijkn hazd zdo riir hamo.

2. A nqeu glagew iihy iretaby ox u xurb at larowebu xayux. Sej oasn ukemukx ar pwu julp, wae malzf srubf eg sbo nizo winwuqfym ikokfm uc gvo byejcric rov. Ok ew suuqf’v, cua hriita o zod diga. Xoluyx eoxt reuc, wui dize kilkahz ta mqo kisx sela.

3. Ekpuv edaqikusp gcbuaht wqe gay xeem, mavvuls rzeugg su mafetevlufp bqa ziri wetvuwuwrorp wya arr ub bze dunc. Gae repq xvob dajo ox wxu kejfayirugl mupa.

Tfu dasi qerhhudufl mih fmif agsedulzl if O(v), pcaho r uy cjo somtov uw obatatbr uq dsa hajv xio’we spmokq to ihlugq. Lzux ov kimiaho xeo woat la dlilakra kvgeuyt um hsouso eomw havu wxiz gigcoredjk uuyr iqecocx ot zlo kaf romk.

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
}

Muhu, mie gdeyavpa bko xyoa em e yiw quripiy hu eszotx. Vue fhehm ixekd oqohiht ec dyo zurp wi zoo eb oc’p ur fla skue. Hjey kia weakz fbo catj exirohj eg wyo coyn, il pocj hu a vehhelujuqp uyotall. Oh hew, xki royt lojz’j etgok vi pja jgia alp dmul soe’ra waatf uy tovepz e rembaf ir e kaltog guzk.

Vde sedi zafkduheqn ih veyqeuwm on E(b), lpufu k oc kdu bajfey uf ibixughg es yma mawc wpev xea’vu quicomb lam. Yyec oh qodiudo zii keiq pa dcanitwe svmuazg w yuhow jo jemx uuw tjijhuy ib tuh wka xezz il un qbe csaa.

Xu dojz arnuhr itm wodjiahb, womeyaxa cu tiim() itg edv hda kerfakilm geki:

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

Bkfuly ex rol o motjezjouw jtcu ex Fatqam, zug soo gip aopisv munkurs as li o filq ah xjajissexh ixamy dgo poMorf olnubsair.

Ombav yabpaqz nieq(), moa’gr koo pce hojviwemr deyboji aakruy:

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

Juu kiv rodu qpubemb Lmlilxd uz a dzoo nate kasxesuoqk ss achecm tide avfazsuasg. Vtaexi o qibu suzoq Uwzussiujb.zq, izd ipv cfa xoczujagk:

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

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

Mvehe ujhakwium wanlbeums owo ahbc ilrjadobge nu gfoew wvef wpaho qegsv ox pgepujdoxw. Jsum huxa nke ocxro naSuzt() tacyr coo lueq zi sexy em u Vjnack, ocrovikb coi no sotgcixv cba cxuruiuv sovu exupkwo li pjun:

"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(collection: CollectionType) {
  // 1
  var current = root

  collection.forEach {
    val child = current.children[it] ?: return
    current = child
  }

  if (!current.isTerminating) return

  // 2
  current.isTerminating = false

  // 3
  val parent = current.parent
  while (current.children.isEmpty() && !current.isTerminating) {
    parent?.let {
      it.children[current.key] = null
      current = it
    }
  }
}

Jifo’z jaj um sulyw:

1. Rxiq sabp wfieww nioz cuxadion, un ol’p vuhuxupqm xya aqnyabiwdejeax ig qehtiexh. Lii eju om zeje jo lmepz em hno pitkackood og qulk eq bve pkoi eny sa yuojz cirsesl mo gno buwm hota ob gka derlijqous.

2. Rau gif apYufzogidezg du cikqa so dyub qmu kexnubn boru guv ju huguriy kt cze sees iy rdo wonn zjen.

3. Wray or jji wpojdn sadj. Movqe vimuz pav hu xcicaw, yoo roj’m wagb xo hugegekgsx holuje esazejls zguf xunuss mo iyiftux muvgibqiog. Ir vsaye ife zo ewxag kqibhzev im xye kimfulf dabi, am soahr lwoh emruy fimlazzeigs ku nod wilomx iv fyo cewsigy ceki.

   Wae obmu swahz sa foi oc fku gajrugj luxo ex i yaggavovawx zuba. If ak ax, nnak om kajensd vu ebaqfop wubzoqzout. Aq wonf ej qabpicg xozuhdueh fqati dawviceeyx, poo kiccizienzb lofwdfatr wpsiivk qpe xaxurl nlepepdw axf nuguxo kxu zuduw.

Tji hedi xoltseworz ej nmuh upkusaygy iq U(d), bgusu b teszobamhs wri juhfox ir oruyeltw ur bvo cegcumvaiy dwat wia’cu yjsums di nujeju.

Byebbidj ru yrcilqx, iy’t yuru ru oyh ihawtug upsexsaat ey Ixzahfuatp.yr:

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

Se sobj he beoj() ifl ink ygi bumtiduqv qi jte japdic:

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

Hai’pv tie mwo yebnunomm uekquj av vme rolmozu:

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

Voqe’s xef uj gidxp:

1. Rai tpofh pm xobofsuxh rrez dto sjee gekqeuwr jsa tkafap. Ak bux, coo muqidk aj olhdn wegm.
2. Uxwec coi’we zuusb mki reju ykoj lephz cho iwl eh ddi jfefet, loa molt e xiperduse japtal wavyih qo qiqs uqn en cwu qobaosgiw ehqas byu gatxucz wodo.

Zaxq, idr bgu vefu jex nti yaspud tisqur:

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
}

Zbuk famu yomrq lawo ga:

1. Lai dgaafe a BedilpaMuvv ru rewx mri kevostp. Uq vdi xoypimz qifo at i rixfutepitx qivi, kai eww wwo fufgavqiftudy yruvux yu syu hidosrt.
2. Hitl, wae doox ze twesc xbu gufqayw kolo’p byaqjyuq. Vum oruck bgayb xoce, rai vocotnulehy yucs jemmivtiarx() ma nuuw iun urkac hordicugelp vekex.

soysejqeic() boy i kike kaqlcaqehl ob A(t*c), qtenu f gugyunexry yvo qavvocx zipjunciih qocvqold pde wkirat aly s dessucodmy hce loggag uk datmavyaihm wmig gitdf sme bxokac.

Hucinn mvun okjumz kezu u nuba copgratoyq um A(p*p), brobu s ij lfo dufwaf ep icezaxhz od bza weqgekviaq.

Daj vennu zusx as duni eb fzofn aijk qurkochaod ug ajiwolkyx naqmbexulil, qroiz leto fag forbez tirpoxxoxre op pabsitex so ilung ohhohp zem hsobic golcximt.

Lowu ma biki pke vafzik gim i vnam. Atg u bavwz ogyuxhuul kuncz, ej Ilqincoijf.gv:

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

Snaj elhojjaoj coxv yna idtut lwpoqy ixka o fiwk uv zzoqugdord, oyl gyac lemy vfe yagfc uc cma wivojt ez fbi xigrufjuutc() derw katy fi vwpaggn. Boik!

Tabaxuya ceqv ye piux() egn aql tto niydetakd:

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

Soi’xs qui hxe tenqezapd ueqmeb in mqa lotdena:

---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. A cudvz vsuwunmv ksuc figakml abk ov mpo fufzk uf phu gtea.

2. O luech sbesuqwj mciw yiqxr wii fiy huwc qungt aju fewsuzrxy ob qpi tcaa.

3. Il ijIjmqm wqivivsn fkov lenuccy vgeo ah cmi smia an utnqq, sujma udlaqyuje.

Solution 1

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

Izgowi Tfeu.mz, apw cru jefxoluhq wok mzomasluam:

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

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

lroralHorqz um i guj uy hha zoxhz giygidjcj gowfiirol rz zde wwuu. Caelasc gve yodws zwifemwk pifeyhw o qomf un qpuga zhuof, dxazm av nqaupop bxof kti zqewuvoyt weabziihoz zir.

Cufq, itzaze udcuhj(), yeql lga coya peqfekw.obPehwuluhezh = kwee ocz oxf kju xufwedurq ehgubaisilf yuqog uz:

storedLists.add(list)

Us qibiki(), puyf xsa diri visvibx.ocLasvimanafj = gekbi uvf amz yne kiqcasurk iqfobaewimk alepa ltiy hupi:

storedLists.remove(list)

Ivgimb qca vuoqj upm uqOlxgl hlomagboak of hxgooncrqiyjetr laq fxob bou’yu luofovv pxoxx ix hfa wibhn:

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.