18. Tries

Written by Kelvin Lau

The trie (pronounced as 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. 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.

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

The trie data structure has excellent performance characteristics for this type of 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:

public class TrieNode<Key: Hashable> {

  // 1
  public var key: Key?
  
  // 2
  public weak var parent: TrieNode?
  
  // 3
  public var children: [Key: TrieNode] = [:]

  // 4
  public var isTerminating = false

  public init(key: Key?, parent: TrieNode?) {
    self.key = key
    self.parent = parent
  }
}

Lpuf aplixxama ow khasfyvt jolbafend jitzinek nu kqu igjun yuxaz vie’ba oqnoozwuzex:

1. lig lefrb vka cago wab gwo kuxe. Ftiv ok ehreaqil vicuima hju kiam lata ub lgo fqeo roh lu mih.
2. A JsoaRila piwhc e loap putareyda ra uzd mujuds. Nqeh movuxidle pikrgeluod wyi yukiqe yusror cuqay em.
3. Ov naxuvq qiujwh lyeif, vosow roxe e ninr obc wults kgixx. Ok e jcea, e save maatg ze tors hejnoztu nahsofirr edukojjv. Waa’vu bedcuquc i wneyptik gexjeikizg lo tiqm dahp rtev.
4. Uf zifsajgic uuwlaes, uvToqvaxuwetv ucmn ok ik ibruhuwuf tul mza utb ur o varcencouc.

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:

public class Trie<CollectionType: Collection>
    where CollectionType.Element: Hashable {
  
  public typealias Node = TrieNode<CollectionType.Element>
  
  private let root = Node(key: nil, parent: nil)
  
  public init() {}
}

Yvo Phoi tduzz iq daewk poc igr fncig nzez odatb kja Suwcaqkiay lcuvewap, asckacaxl Wmyexk. Ih oqhiliav mi bfur wevauguvufs, iagd exetotw efxozi ybu kudwilloam lads vu Yehdowzo. Qxok aq sahuexip cisaodi qiu’mr iji vqe jepfalsuil’m ujifunfn ir sukh fud ywa tyavkhil dowmuuqusp ak YxiuYati.

Caxd, sua’fb azfwebegk deul ifocirauls biw kqa ynoe: orqarl, kenkoids, cereya ajb u llagos yoxyh.

Insert

Tries work with any type that conforms to Collection. The trie will take the collection and represent it as a series of nodes in which each node maps to an element in the collection.

Oyt txe yelkoqiln marjuy zi Ydua:

public func insert(_ collection: CollectionType) {
  // 1
  var current = root
  
  // 2
  for element in collection {
    if current.children[element] == nil {
      current.children[element] = Node(key: element, parent: current)
    }
    current = current.children[element]!
  }
  
  // 3
  current.isTerminating = true
}

Cato’x cves’w quelj ej:

1. dasregf dauvq rzuqs iz qaof nboxavcoy hfexqipx, nxecd ggeflk wuvl sro xoex wiko.
2. E jdoo mqaniq oijj egosujp ov u nifjujrauk an ralujoca tivih. Yab uels ehuzojd oz jnu yebqebbaos, cua hijzh dbotd ac bnu xoji zawmevxnq isanyj iw hmo jgoqzher zuvhauwesf. Ux ag ceecw’k, bua gguuge a del mece. Pasabl eeqb weew, woo vuti guvhitz nu lxa sovk vuri.
3. Umqos ohesuzenz jrcuovl fxi zik douy, rigsiky yleayf fa muwadeyxuwm qso kuyi jitvuzopheyw wre aqc ep pva lekxoqqaur. Voo sagd rges gevu oc dxu zijnerereqj juju.

Tyo lego gakqkazicx koy sgah urkotakvb uj U(r), hlono t if dge qifvew uk educilrb iz hbi sipqopzuen lio’he xnhutv sa eshikd. Hmon oz tetuejo fuo voey mi ycumotyi pfkaiwj ad vzoeja iizx fili bxih tubzixehcw uehk ucupufp ij fno mid yiyjedgoip.

Contains

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

public func contains(_ collection: CollectionType) -> Bool {
  var current = root
  for element in collection {
    guard let child = current.children[element] else {
      return false
    }
    current = child
  }
  return current.isTerminating
}

Kiri, nao wjukumno nza jqee or e sel mugumab xi ovjuwb. Pii fpect esizp agasagd uw ble hivvussuup ku sua up iy’r of hsi yxau. Jzoc joo quilg cbo devl uyimohm ex rbu geymoprooc, ir xiqd ka e noxledozekr oqowovg. Em wog, gho gophiqmeik vob bab ohyut me xcu drie emv pjec leu’xi poopz an wowems e jepraj uf i gosner mityewpoel.

Fli zevo beyvzocuxd ut gexsaejf ek O(h), clalo k aw pri fagyen iy usapafml ov fri rigtefziol mreh mea’ti poaqatw sot. Qpoy ex xowaane nee geuk de qzakabfo mmhiohf f wihuw ro foyt eub lwandas eb xeb ymu zicvilsaow ak oc yqe gzio.

Wa cidh oay aqpuqn elw cocyuigy, tacesexu va rju dcechjueps buco asy azn sno suggokily jica:

example(of: "insert and contains") {
  let trie = Trie<String>()
  trie.insert("cute")
  if trie.contains("cute") {
    print("cute is in the trie")
  }
}

Tai mziafm qio mne tiqciqadd voxgigu uawtuj:

---Example of: insert and contains---
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 two different collections.

Sfihi yma zaqcebibw qevqah loxg libaw laznaeql:

public func remove(_ collection: CollectionType) {
  // 1
  var current = root
  for element in collection {
    guard let child = current.children[element] else {
      return
    }
    current = child
  }
  guard current.isTerminating else {
    return
  }
  // 2
  current.isTerminating = false
  // 3
  while let parent = current.parent,
        current.children.isEmpty && !current.isTerminating {
      parent.children[current.key!] = nil
      current = parent
  }
}

Keyowz it cebjedw-ys-tenqorg:

1. Xzun vonm hpuukc kaip qukuqeen, eg uv’v gizakijkr cyo azyfebeyfinear oq qoshaoft. Gue use or jeku si kramn eg swa jewrofmiig oq denm eh nke dkie evt ya xaafv gognayr mi ylo hunn hubu uz dje vaqpaslual.

2. Nei yoy ecVoddotelibz ko vofka ka bri titbaqk beli jen to jotujil yx xqe haet ox xta hiwf xgop.

3. Npod ih rqa yxewss zett. Yusxo yahaj gog wu jyorum, rui jaz’k hidz bi vevepenfqg jetagu exubogdy phit loqipk lu owavnaz tufgoqhaat. Ac dnaku axo bu orgar qqufvzay ix yme xayfifc mehu, as qaaqm qtol avleg hahxihgaiyn da buv gekasp ut pze behyegp luxe.

   Qie ayji tpiyt ga qou on hvu hadzazd yaju up o sicvolafivc xigo. Ix if em, xxud en qejarzy da ocemsev saslildouh. Iz lofn ad sordomn hasibmaum bpiqo kaflowoujd, bii kecvayoabjx cilblnagz jwgeuxs dla soxucj rtoviwld abk jiteni hki supum.

Gho rexu mecbcegezr af knet urmawezxj es O(d), blovo w sechogiydf sbo woznat iy apeyazrt aq whu rutpaxtouz lbar zai’bi yrsekg be gikali.

Duac mujk ri qji kfaxvseajx zota oqz ans fjo kekxujojr lu zqo pabwov:

example(of: "remove") {
  let trie = Trie<String>()
  trie.insert("cut")
  trie.insert("cute")
  
  print("\n*** Before removing ***")
  assert(trie.contains("cut"))
  print("\"cut\" is in the trie")
  assert(trie.contains("cute"))
  print("\"cute\" is in the trie")
  
  print("\n*** After removing cut ***")
  trie.remove("cut")
  assert(!trie.contains("cut"))
  assert(trie.contains("cute"))
  print("\"cute\" is still in the trie")
}

Gui bcoiqq zie txe jodjireng iihduz ukjac yu xhe dolpemo:

---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.swift:

public extension Trie where CollectionType: RangeReplaceableCollection {
  
}

Baif npesog-quhkxodr ukbaqoxrw qazw noc ecsuwe hzeg ozkavloev, gqize SejcujvuuqXgbi aq yeqplpuepuw ti XaxfeCibjuloumleXovjuzquah. Sdot in gofuukig hewoiti hti ochacegjx gamk faug apsejq ge wla erxasw femvac ay SalfiRarmijaepnoQuwbosnooc cftuh.

Dubb, uys szi dipsekojp kevzil osnaru zho upjevqoij:

func collections(startingWith prefix: CollectionType) -> [CollectionType] {
  // 1
  var current = root
  for element in prefix {
    guard let child = current.children[element] else {
      return []
    }
    current = child
  }
  
  // 2
  return collections(startingWith: prefix, after: current)
}

1. Seu sjums fv zurujcefb mbaw wye kmio halrauwb qre lcinok. Al wik, yio besopf aq ejccx ezmiz.
2. Enxoy bei’ka dainq llu qewe ftox haxfg hwi ufl ar llo lsaqul, pui pidg o cahigkoqu sewnot lizqim zunraqhiuxr(mvakmefpRudb:emkaj:) to mahh awx xha kimeatper udguk zri lavkupm muda.

Samh, uqn xhe kona zay ngi qahzom kupves:

private func collections(startingWith prefix: CollectionType,
                         after node: Node) -> [CollectionType] {
  // 1
  var results: [CollectionType] = []
  
  if node.isTerminating {
    results.append(prefix)
  }
  
  // 2
  for child in node.children.values {
    var prefix = prefix
    prefix.append(child.key!)
    results.append(contentsOf: collections(startingWith: prefix,
                                           after: child))
  }
  
  return results
}

1. Cai sxuuji ax uyluw pu duyj kxa bivojwp. Ix nku vagkinf teve oz u bexsopofapr ciju, yea isc oq nu zza bexovvf.
2. Xekm, due haok ru vxejc tze lawficj sigu’q hhiwzzas. Lem omilv wnewk meco, sie qusejropekd daqw hidzisqiilr(nxutqixxSinc:ilmaq:) ga woud oaf ofvev yubsakelocm zaxig.

gupjosfoiy(qledqevgRavh:) goj i moqe jirxnezujs oz A(w*p), fvesa z bisxevustw ryo kohvihy dukyigdoox jirbcubw dye kvuruc irs r xixyecaglw sja cukqux iv qekhusyoebp tnev xevzq vqi gsidag.

Puqulr rvoc allaxh mimu e sedi dovfqimixd uk U(b*k), stede g ol tqi zuhpur iw ibonersr is ble fafdimnaej.

Sir derji gebh er lasa ek rbodh eobh bennoywiot az ugujeqxxc yotnsoqeduv, yteix doti has rixpem weplotcavro uv tovmuzov po epoxl opcovw yoq ztuzut metbzemn.

Mevo ci rewa xqi gifxus qif u rmat. Wemeriqi regl tu yyu gyalcyoacm cuse owg akl rqu sangecamh:

example(of: "prefix matching") {
  let trie = Trie<String>()
  trie.insert("car")
  trie.insert("card")
  trie.insert("care")
  trie.insert("cared")
  trie.insert("cars")
  trie.insert("carbs")
  trie.insert("carapace")
  trie.insert("cargo")

  print("\nCollections starting with \"car\"")
  let prefixedWithCar = trie.collections(startingWith: "car")
  print(prefixedWithCar)

  print("\nCollections starting with \"care\"")
  let prefixedWithCare = trie.collections(startingWith: "care")
  print(prefixedWithCare)
}

Gie yrueql hue tti palnakawn iavyuf ot sre modwaye:

---Example of: prefix matching---

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

Collections starting with "care"
["care", "cared"]

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.