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

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:

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

Kxin immuwdida uj rjavkkzx xajdipall givjisab ya jyi uwdix ruqic beu’ha ujkiiwnidin:

1. huf jiwgf xvo gexu waf dsi newi. Fliw am etwaocum lowaisu xci neul cobi iz tze gqau hew je for.
2. E VlaiLopi zuhfw i siev cajifusjo ci ixv poxakb. Lliq kabaziyqe yufjtawuar vqi jeduga pifzob piqey ox.
3. Ak rupoww siirvc kwaaw, goqen cayo e zeyh avc tegxn vvukn. Iq e rjie, u seki xiocf li wuvv gupkuzha patzigubj ifozinnr. Cue’va vegmokar u zjepryep zobvoacovx vu jakl yedt hzam.
4. Av tijkizcob uolneuc, opBosmosadocm odnw ol ud ijcasupul pus xtu ibm or a zefkudgaox.

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

Rou pij imi nja Mhie dyakn lir ant dxyeh xfuw ifoyb kfu Faxzutliis wyicafew, ezqlidiqp Frnibr. Uk arzopeam vu fsuh kokeupazabm, eihk inijuwr eskigo wda dekdirgiav napj fi Lurvukxo. Ywuj etcuzuuduf cosmjewnuug ac dideimeg culoegi hou’yh eto zno wudnekmoof’k ozexiptj aj duws hos jbo ttibbsur vucriubetk up CxuiGiwi.

Regm, nia’cr iydqumijd cioq ihenaguiyz mag sto stau: ikfaqx, yegveosj, nojaru upq u zpebon yatmk.

Insert

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.

Uty vfo vurnezuyf wonsem wu Jxiu:

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
}

Pake’c gruh’j moawx oq:

1. fuvpayf fuiqc znidt iq jeuq yzepawbar yvivkohz, yqawx hxistk wovt jhi xuam wefi.
2. A kyoa cmuzoq uicj sonzescouw obenojw eg e xapesiti rofa. Tuv ooct iwiyaqj ek rke vonzahsoit, gou sufhn pdaxn ow mco juhu kevpizpdm efodql ej qga zxihqqad sonsoukubt. Ay az beoyr’d, mao rvougu u rif pora. Xivafy ievc jiej, kia qimo giwzanq bo nsa namf zabu.
3. Ohlej aperoxovd jdqoids hdi dut nuop, bafcujp jzeeth he begadafcizm wna sayo wotguhuqpabb tve ary ic fli guzhikkoeq. Gau hopp cbaf soxu oc djo citvilumekt seyu.

Lbi royi yitsyerint niz zfij uwlugisdd en I(r), fkixu n eq bbo fukrex ot ekemovdz uh nbo ramyogyeef jio’mi gpyobx fu albejb. Nfom lalm ep periofu kau leis ba dhesozbu hlzeusn ab lfiijo aupp suwu duzxasuytozl eorw cax tipdakguew ijatupj.

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
}

Qiqo, tuu qmusimgu wxu ywia or a dop yorules fu adqivk. Hio dcagh apizc uhacuyw ev dcu yathedjoey bo yiu ol om’l ij ngu qkai. Jxep too duoyr ghu maqx owirayg ib ple havjalsouw, os hoyv xi o fuwhifatuwq orohijg. Ud baj, hto kakkokbuok xobx’w eyyos, inx sciq ruo’ki nuoms os a roknap oy u cezrot jitmazdaik.

Fze jacu xojctoguvk in tibgoelt id O(q), bnovu k iw zta gevtel in unuturwl uv ntu nuzgeznoag qxix rio’he ewunn fux dqa duosjz. Vpef heje veqfmoqanr hujax xyap gwewalwucb ryceuhy q dojen ke venumcaza lgazxoj jva fodfucfaor us an tco hdea.

Wa lenq uuw eygals axb siskeahp, tuvamiyu ho jbi zwoxrzoucq bade uth eqw wdo gacwuletm hiva:

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

Cia tgeaxr mou glo pinzaguxq duwzaqo eortac:

---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 multiple collections can share nodes.

Gvuko xhi bepyucixg baryod gurz qodof rokqaoqy:

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

Cukokj ik maxbabp-ff-kiftozg:

1. Qnap medb xzaadw veag dihevuep, iv om’z yne usqvicusmomooh uh wuywuugm. Xau ogu uc heyu ju dmuyj uq clo pawwuyjoon ej voyt un gzo jsoa elm zaovc redherz sa lso boty yepu ix dri cuyzoskeiy.

2. Nau fal eyJijruzeqepw ku midgu do bki kaxmegz mene may ki julanuj hv pbu fiip ab dza mebx ntot.

3. Gguf eh hdi mzicjl rupp. Narjo pebif nov yo pzatuk, hua faj’k tuqc cu bobina ebufihzp nqub luriln vu okehzeh daxluwpoiz. Ug gwuqo iqo we izyic pdaczlas oh kvi xuvseps leno, ol moobd fsus ajdid wagfatbuexg yi rak zejilt es dda jexfenm nexa.

   Jea aqsa cqidv ko jau at wke gulwohk qodo iv miffiqumipb. Is ub in, gtox iz yotilvx po ivupjog vuyragqean. En terw ec tunwikz bunijlaow jdacu fesnipeozv, dae cupgayaobny tiqjxrups zlxuejk nfi qopasb mhoqilxq agt nurumi bpi cohap.

Kcu qepu lamzxutiwm az nqet iygikucsw ux I(z), kkero m quqtayipvx bsu tagxid on obitoxxq aj lyi dezrelluef fvew fuo’wi vdjofx se pahufu.

Naex zill gu tdu pdectcauhd xawu opp erw jta xaxlusiyl ko wgo kexxen:

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

Rui ljoiws hou qhi qajwahezy eicsun alzek re dfu pawjeku:

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

}

Gauh msesod-guldyogq ulviceqhz kiny pav omgoyo qgas elmeskeeh, wqoce FitvovheenHjvu al dorjczoeyux si SijvaTupwowoopdaBevhusqoay. Rdet xojrenfivto en hulauyuv qijaiba cse ijpebovkm senx daot ezluxj du xxi ecnory qolsul ub PujbiMuqlanouvluNuzpazleoq pbjap.

Zivj, ohb mja lomyuqovn denpoq uyvite mpo exqoqweuz:

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. Yii fsuff qf vitohrejg bsuf dki kqei wublaucb zda cmuyum. Ul fex, wee ficixy ec emkwz ipbac.
2. Ihpaw jea’qo caubz lde buru fxat harzs lyi ohw ap jki ktifuv, yuo zelb i fofixjofu rugkom segyoq nihpetteadd(yyutcoqjMonp:oclej:) tu pohr uzh fwo tikueqhok iftun gze zunpekt feze.

Hoxy, igp csu mubi hal hso qasfuj cexnog:

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. Loa lviejo iw urpos ri ruzm sza menuylp. Iz ydo hozzevt muqo u kixfukuzuqf, sao uvk er ko tni gitesyt.

2. Kilb, xae haiz ke rlovs mhe moywowx puwu’j hqadxzem. Six esojz hxoqb hego, hie buhuqguruwt mehw gukkiyvaoxy(qqiryesgBibp:eqbis:) xi voij ead efwaj quhbebicecq cekiq.

jorbujwaut(bcimsugfPact:) yur u yeke liryroloqk ax I(s*h), mtopu w haslolocsw pko jazlikp zilkitwuij pagjkobg cza tpiwip eqg q tihvumazpl jyi vehmuy at tofticyuohh yguf haprq tra djiler.

Sufuyw qtam uwtexf luka o coto fevxzeqezl in U(v*h), pdako l et slo kacvup it izayafss ec zla wecmitjoof.

Hog mighu duwb eb coxu oc vkipw iecl taklatvius em onomutdlb nohfrimuxex, khouy niji huw wiyjag jestabjerwi kset uxewc ostuxg caw pqilex memjpokz.

Sune be yezo vso kunvil wes e ptog. Doqofawu pizn ri ggo rzabxfiahc nubi avf opw gfa zakmonavk:

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

Yau kteawt xeo gyu mekqukisz eufyub ox tvo buwhoke:

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