<
CD95
script type="application/json" data-target="react-app.embeddedData">{"payload":{"allShortcutsEnabled":false,"path":"Trie","repo":{"id":207164632,"defaultBranch":"master","name":"swift-algorithm-club","ownerLogin":"timrc","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2019-09-08T19:44:48.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/3773639?v=4","public":true,"private":false,"isOrgOwned":false},"currentUser":null,"refInfo":{"name":"master","listCacheKey":"v0:1615617031.636876","canEdit":false,"refType":"branch","currentOid":"667d265e3520929aa22251751ac6b331af660506"},"tree":{"items":[{"name":"Trie","path":"Trie/Trie","contentType":"directory"},{"name":"images","path":"Trie/images","contentType":"directory"},{"name":"ReadMe.md","path":"Trie/ReadMe.md","contentType":"file"}],"templateDirectorySuggestionUrl":null,"readme":{"displayName":"ReadMe.md","richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eTrie\u003c/h1\u003e\u003ca id=\"user-content-trie\" class=\"anchor\" aria-label=\"Permalink: Trie\" href=\"#trie\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003eThis topic has been tutorialized \u003ca href=\"https://www.raywenderlich.com/139410/swift-algorithm-club-swift-trie-data-structure\" rel=\"nofollow\"\u003ehere\u003c/a\u003e\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eWhat is a Trie?\u003c/h2\u003e\u003ca id=\"user-content-what-is-a-trie\" class=\"anchor\" aria-label=\"Permalink: What is a Trie?\" href=\"#what-is-a-trie\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eA \u003ccode\u003eTrie\u003c/code\u003e, (also known as a prefix tree, or radix tree in some other implementations) is a special type of tree used to store associative data structures. A \u003ccode\u003eTrie\u003c/code\u003e for a dictionary might look like this:\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ca target=\"_blank\" rel=\"noopener noreferrer\" href=\"/timrc/swift-algorithm-club/blob/master/Trie/images/trie.png\"\u003e\u003cimg src=\"/timrc/swift-algorithm-club/raw/master/Trie/images/trie.png\" alt=\"A Trie\" style=\"max-width: 100%;\"\u003e\u003c/a\u003e\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eStoring the English language is a primary use case for a \u003ccode\u003eTrie\u003c/code\u003e. Each node in the \u003ccode\u003eTrie\u003c/code\u003e would represent a single character of a word. A series of nodes then make up a word.\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eWhy a Trie?\u003c/h2\u003e\u003ca id=\"user-content-why-a-trie\" class=\"anchor\" aria-label=\"Permalink: Why a Trie?\" href=\"#why-a-trie\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eTries are very useful for certain situations. Here are some of the advantages:\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eLooking up values typically have a better worst-case time complexity.\u003c/li\u003e\n\u003cli\u003eUnlike a hash map, a \u003ccode\u003eTrie\u003c/code\u003e does not need to worry about key collisions.\u003c/li\u003e\n\u003cli\u003eDoesn't utilize hashing to guarantee a unique path to elements.\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003eTrie\u003c/code\u003e structures can be alphabetically ordered by default.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eCommon Algorithms\u003c/h2\u003e\u003ca id=\"user-content-common-algorithms\" class=\"anchor\" aria-label=\"Permalink: Common Algorithms\" href=\"#common-algorithms\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eContains (or any general lookup method)\u003c/h3\u003e\u003ca id=\"user-content-contains-or-any-general-lookup-method\" class=\"anchor\" aria-label=\"Permalink: Contains (or any general lookup method)\" href=\"#contains-or-any-general-lookup-method\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e\u003ccode\u003eTrie\u003c/code\u003e structures are great for lookup operations. For \u003ccode\u003eTrie\u003c/code\u003e structures that model the English language, finding a particular word is a matter of a few pointer traversals:\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func contains(word: String) -\u0026gt; Bool {\n guard !word.isEmpty else { return false }\n\n // 1\n var currentNode = root\n \n // 2\n var characters = Array(word.lowercased())\n var currentIndex = 0\n \n // 3\n while currentIndex \u0026lt; characters.count, \n let child = currentNode.children[characters[currentIndex]] {\n\n currentNode = child\n currentIndex += 1\n }\n\n // 4\n if currentIndex == characters.count \u0026amp;\u0026amp; currentNode.isTerminating {\n return true\n } else {\n return false\n }\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e contains\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eword\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eString\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eBool\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eguard\u003c/span\u003e !word\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eisEmpty \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n // 1\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ecurrentNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e root\n \n // 2\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003echaracters\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eArray\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eword\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003elowercased\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ecurrentIndex\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e\n \n // 3\n \u003cspan class=\"pl-k\"\u003ewhile\u003c/span\u003e currentIndex \u003cspan class=\"pl-c1\"\u003e\u0026lt;\u003c/span\u003e characters\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount\u003cspan class=\"pl-kos\"\u003e,\u003c/span\u003e \n \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e child \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e currentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003echildren\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003e\u003cspan class=\"pl-en\"\u003echaracters\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003ecurrentIndex\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n\n currentNode \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e child\n currentIndex \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n // 4\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e currentIndex \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e characters\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003ecount \u0026amp;\u0026amp; currentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eisTerminating \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003etrue\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eThe \u003ccode\u003econtains\u003c/code\u003e method is fairly straightforward:\u003c/p\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eCreate a reference to the \u003ccode\u003eroot\u003c/code\u003e. This reference will allow you to walk down a chain of nodes.\u003c/li\u003e\n\u003cli\u003eKeep track of the characters of the word you're trying to match.\u003c/li\u003e\n\u003cli\u003eWalk the pointer down the nodes.\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003eisTerminating\u003c/code\u003e is a boolean flag for whether or not this node is the end of a word. If this \u003ccode\u003eif\u003c/code\u003e condition is satisfied, it means you are able to find the word in the \u003ccode\u003etrie\u003c/code\u003e.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eInsertion\u003c/h3\u003e\u003ca id=\"user-content-insertion\" class=\"anchor\" aria-label=\"Permalink: Insertion\" href=\"#insertion\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eInsertion into a \u003ccode\u003eTrie\u003c/code\u003e requires you to walk over the nodes until you either halt on a node that must be marked as \u003ccode\u003eterminating\u003c/code\u003e, or reach a point where you need to add extra nodes.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func insert(word: String) {\n guard !word.isEmpty else {\n return\n }\n\n // 1\n var currentNode = root\n\n // 2\n for character in word.lowercased() {\n // 3\n if let childNode = currentNode.children[character] {\n currentNode = childNode\n } else {\n currentNode.add(value: character)\n currentNode = currentNode.children[character]!\n }\n }\n // Word already present?\n guard !currentNode.isTerminating else {\n return\n }\n\n // 4\n wordCount += 1\n currentNode.isTerminating = true\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e insert\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eword\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eString\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eguard\u003c/span\u003e !word\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eisEmpty \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n // 1\n \u003cspan class=\"pl-k\"\u003evar\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ecurrentNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e root\n\n // 2\n \u003cspan class=\"pl-k\"\u003efor\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003echaracter\u003c/span\u003e \u003cspan class=\"pl-k\"\u003ein\u003c/span\u003e word\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003elowercased\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n // 3\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e childNode \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e currentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003echildren\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003echaracter\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n currentNode \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e childNode\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n currentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eadd\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003evalue\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e character\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n currentNode \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e currentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003e\u003cspan class=\"pl-en\"\u003echildren\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e[\u003c/span\u003echaracter\u003cspan class=\"pl-kos\"\u003e]\u003c/span\u003e!\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n // Word already present?\n \u003cspan class=\"pl-k\"\u003eguard\u003c/span\u003e !currentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eisTerminating \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n // 4\n wordCount \u003cspan class=\"pl-c1\"\u003e+=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n currentNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eisTerminating \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003etrue\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003eOnce again, you create a reference to the root node. You'll move this reference down a chain of nodes.\u003c/li\u003e\n\u003cli\u003eBegin walking through your word letter by letter\u003c/li\u003e\n\u003cli\u003eSometimes, the required node to insert already exists. That is the case for two words inside the \u003ccode\u003eTrie\u003c/code\u003e that shares letters (i.e \"Apple\", \"App\"). If a letter already exists, you'll reuse it, and simply traverse deeper down the chain. Otherwise, you'll create a new node representing the letter.\u003c/li\u003e\n\u003cli\u003eOnce you get to the end, you mark \u003ccode\u003eisTerminating\u003c/code\u003e to true to mark that specific node as the end of a word.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eRemoval\u003c/h3\u003e\u003ca id=\"user-content-removal\" class=\"anchor\" aria-label=\"Permalink: Removal\" href=\"#removal\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eRemoving keys from the trie is a little tricky, as there are a few more cases you'll need to take into account. Nodes in a \u003ccode\u003eTrie\u003c/code\u003e may be shared between different words. Consider the two words \"Apple\" and \"App\". Inside a \u003ccode\u003eTrie\u003c/code\u003e, the chain of nodes representing \"App\" is shared with \"Apple\".\u003c/p\u003e\n\u003cp dir=\"auto\"\u003eIf you'd like to remove \"Apple\", you'll need to take care to leave the \"App\" chain in tact.\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-swift notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"func remove(word: String) {\n guard !word.isEmpty else {\n return\n }\n\n // 1\n guard let terminalNode = findTerminalNodeOf(word: word) else {\n return\n }\n\n // 2\n if terminalNode.isLeaf {\n deleteNodesForWordEndingWith(terminalNode: terminalNode)\n } else {\n terminalNode.isTerminating = false\n }\n wordCount -= 1\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-en\"\u003efunc\u003c/span\u003e remove\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eword\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eString\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003eguard\u003c/span\u003e !word\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eisEmpty \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n // 1\n \u003cspan class=\"pl-k\"\u003eguard\u003c/span\u003e \u003cspan class=\"pl-k\"\u003elet\u003c/span\u003e terminalNode \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003efindTerminalNodeOf\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eword\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e word\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n\n // 2\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e terminalNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eisLeaf \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n \u003cspan class=\"pl-en\"\u003edeleteNodesForWordEndingWith\u003c/span\u003e\u003cspan class=\"pl-kos\"\u003e(\u003c/span\u003eterminalNode\u003cspan class=\"pl-kos\"\u003e:\u003c/span\u003e terminalNode\u003cspan class=\"pl-kos\"\u003e)\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-kos\"\u003e{\u003c/span\u003e\n terminalNode\u003cspan class=\"pl-kos\"\u003e.\u003c/span\u003eisTerminating \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003efalse\u003c/span\u003e\n \u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\n wordCount \u003cspan class=\"pl-c1\"\u003e-=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e\n\u003cspan class=\"pl-kos\"\u003e}\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003col dir=\"auto\"\u003e\n\u003cli\u003e\u003ccode\u003efindTerminalNodeOf\u003c/code\u003e traverses through the Trie to find the last node that represents the \u003ccode\u003eword\u003c/code\u003e. If it is unable to traverse through the chain of characters, it returns \u003ccode\u003enil\u003c/code\u003e.\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003edeleteNodesForWordEndingWith\u003c/code\u003e traverse backwords, deleting the nodes represented by the \u003ccode\u003eword\u003c/code\u003e.\u003c/li\u003e\n\u003c/ol\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eTime Complexity\u003c/h3\u003e\u003ca id=\"user-content-time-complexity\" class=\"anchor\" aria-label=\"Permalink: Time Complexity\" href=\"#time-complexity\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003eLet n be the length of some value in the \u003ccode\u003eTrie\u003c/code\u003e.\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003ccode\u003econtains\u003c/code\u003e - Worst case O(n)\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003einsert\u003c/code\u003e - O(n)\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003eremove\u003c/code\u003e - O(n)\u003c/li\u003e\n\u003c/ul\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eOther Notable Operations\u003c/h3\u003e\u003ca id=\"user-content-other-notable-operations\" class=\"anchor\" aria-label=\"Permalink: Other Notable Operations\" href=\"#other-notable-operations\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e\u003ccode\u003ecount\u003c/code\u003e: Returns the number of keys in the \u003ccode\u003eTrie\u003c/code\u003e - O(1)\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003ewords\u003c/code\u003e: Returns a list containing all the keys in the \u003ccode\u003eTrie\u003c/code\u003e - O(1)\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003eisEmpty\u003c/code\u003e: Returns \u003ccode\u003etrue\u003c/code\u003e if the \u003ccode\u003eTrie\u003c/code\u003e is empty, \u003ccode\u003efalse\u003c/code\u003e otherwise - O(1)\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eSee also \u003ca href=\"https://en.wikipedia.org/wiki/Trie\" rel=\"nofollow\"\u003eWikipedia entry for Trie\u003c/a\u003e.\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003cem\u003eWritten for the Swift Algorithm Club by Christian Encarnacion. Refactored by Kelvin Lau\u003c/em\u003e\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003eChanges by Rick Zaccone\u003c/h1\u003e\u003ca id=\"user-content-changes-by-rick-zaccone\" class=\"anchor\" aria-label=\"Permalink: Changes by Rick Zaccone\" href=\"#changes-by-rick-zaccone\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003eAdded comments to all methods\u003c/li\u003e\n\u003cli\u003eRefactored the \u003ccode\u003eremove\u003c/code\u003e method\u003c/li\u003e\n\u003cli\u003eRenamed some variables. I have mixed feelings about the way Swift infers types. It's not always apparent what type a variable will have. To address this, I made changes such as renaming \u003ccode\u003eparent\u003c/code\u003e to \u003ccode\u003eparentNode\u003c/code\u003e to emphasize that it is a node and not the value contained within the node.\u003c/li\u003e\n\u003cli\u003eAdded a \u003ccode\u003ewords\u003c/code\u003e property that recursively traverses the trie and constructs an array containing all of the words in the trie.\u003c/li\u003e\n\u003cli\u003eAdded a \u003ccode\u003eisLeaf\u003c/code\u003e property to \u003ccode\u003eTrieNode\u003c/code\u003e for readability.\u003c/li\u003e\n\u003cli\u003eImplemented \u003ccode\u003ecount\u003c/code\u003e and \u003ccode\u003eisEmpty\u003c/code\u003e properties for the trie.\u003c/li\u003e\n\u003cli\u003eI tried stress testing the trie by adding 162,825 words. The playground was very slow while adding the words and eventually crashed. To fix this problem, I moved everything into a project and wrote \u003ccode\u003eXCTest\u003c/code\u003e tests that test the trie. There are also several performance tests. Everything passes.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/article\u003e","errorMessage":null,"headerInfo":{"toc":[{"level":1,"text":"Trie","anchor":"trie","htmlText":"Trie"},{"level":2,"text":"What is a Trie?","anchor":"what-is-a-trie","htmlText":"What is a Trie?"},{"level":2,"text":"Why a Trie?","anchor":"why-a-trie","htmlText":"Why a Trie?"},{"level":2,"text":"Common Algorithms","anchor":"common-algorithms","htmlText":"Common Algorithms"},{"level":3,"text":"Contains (or any general lookup method)","anchor":"contains-or-any-general-lookup-method","htmlText":"Contains (or any general lookup method)"},{"level":3,"text":"Insertion","anchor":"insertion","htmlText":"Insertion"},{"level":3,"text":"Removal","anchor":"removal","htmlText":"Removal"},{"level":3,"text":"Time Complexity","anchor":"time-complexity","htmlText":"Time Complexity"},{"level":3,"text":"Other Notable Operations","anchor":"other-notable-operations","htmlText":"Other Notable Operations"},{"level":1,"text":"Changes by Rick Zaccone","anchor":"changes-by-rick-zaccone","htmlText":"Changes by Rick Zaccone"}],"siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Ftimrc%2Fswift-algorithm-club%2Ftree%2Fmaster%2FTrie"}},"totalCount":3,"showBranchInfobar":true},"fileTree":{"":{"items":[{"name":".github","path":".github","contentType":"directory"},{"name":"3Sum and 4Sum","path":"3Sum and 4Sum","contentType":"directory"},{"name":"AVL Tree","path":"AVL Tree","contentType":"directory"},{"name":"All-Pairs Shortest Paths","path":"All-Pairs Shortest Paths","contentType":"directory"},{"name":"Array2D","path":"Array2D","contentType":"directory"},{"name":"B-Tree","path":"B-Tree","contentType":"directory"},{"name":"Binary Search Tree","path":"Binary Search Tree","contentType":"directory"},{"name":"Binary Search","path":"Binary Search","contentType":"directory"},{"name":"Binary Tree","path":"Binary Tree","contentType":"directory"},{"name":"Bit Set","path":"Bit Set","contentType":"directory"},{"name":"Bloom Filter","path":"Bloom Filter","contentType":"directory"},{"name":"Bounded Priority Queue","path":"Bounded Priority Queue","contentType":"directory"},{"name":"Boyer-Moore-Horspool","path":"Boyer-Moore-Horspool","contentType":"directory"},{"name":"Breadth-First Search","path":"Breadth-First Search","contentType":"directory"},{"name":"Brute-Force String Search","path":"Brute-Force String Search","contentType":"directory"},{"name":"Bubble Sort","path":"Bubble Sort","contentType":"directory"},{"name":"Bucket Sort","path":"Bucket Sort","contentType":"directory"},{"name":"Closest Pair","path":"Closest Pair","contentType":"directory"},{"name":"Comb Sort","path":"Comb Sort","contentType":"directory"},{"name":"Combinatorics","path":"Combinatorics","contentType":"directory"},{"name":"Convex Hull","path":"Convex Hull","contentType":"directory"},{"name":"Count Occurrences","path":"Count Occurrences","contentType":"directory"},{"name":"Counting Sort","path":"Counting Sort","contentType":"directory"},{"name":"Depth-First Search","path":"Depth-First Search","contentType":"directory"},{"name":"Deque","path":"Deque","contentType":"directory"},{"name":"Dijkstra Algorithm","path":"Dijkstra Algorithm","contentType":"directory"},{"name":"DiningPhilosophers","path":"DiningPhilosophers","contentType":"directory"},{"name":"Egg Drop Problem","path":"Egg Drop Problem","contentType":"directory"},{"name":"Encode and Decode Tree","path":"Encode and Decode Tree","contentType":"directory"},{"name":"Fixed Size Array","path":"Fixed Size Array","contentType":"directory"},{"name":"Fizz Buzz","path":"Fizz Buzz","contentType":"directory"},{"name":"GCD","path":"GCD","contentType":"directory"},{"name":"Genetic","path":"Genetic","contentType":"directory"},{"name":"Graph","path":"Graph","contentType":"directory"},{"name":"Hash Set","path":"Hash Set","contentType":"directory"},{"name":"Hash Table","path":"Hash Table","contentType":"directory"},{"name":"Hashed Heap","path":"Hashed Heap","contentType":"directory"},{"name":"HaversineDistance","path":"HaversineDistance","contentType":"directory"},{"name":"Heap Sort","path":"Heap Sort","contentType":"directory"},{"name":"Heap","path":"Heap","contentType":"directory"},{"name":"Huffman Coding","path":"Huffman Coding","contentType":"directory"},{"name":"Images","path":"Images","contentType":"directory"},{"name":"Insertion Sort","path":"Insertion Sort","contentType":"directory"},{"name":"Introsort","path":"Introsort","contentType":"directory"},{"name":"K-Means","path":"K-Means","contentType":"directory"},{"name":"Karatsuba Multiplication","path":"Karatsuba Multiplication","contentType":"directory"},{"name":"Knuth-Morris-Pratt","path":"Knuth-Morris-Pratt","contentType":"directory"},{"name":"Kth Largest Element","path":"Kth Largest Element","contentType":"directory"},{"name":"LRU Cache","path":"LRU Cache","contentType":"directory"},{"name":"Linear Regression","path":"Linear Regression","contentType":"directory"},{"name":"Linear Search","path":"Linear Search","contentType":"directory"},{"name":"Linked List","path":"Linked List","contentType":"directory"},{"name":"Longest Common Subsequence","path":"Longest Common Subsequence","contentType":"directory"},{"name":"Merge Sort","path":"Merge Sort","contentType":"directory"},{"name":"Miller-Rabin Primality Test","path":"Miller-Rabin Primality Test","contentType":"directory"},{"name":"Minimum Edit Distance","path":"Minimum Edit Distance","contentType":"directory"},{"name":"Minimum Spanning Tree (Unweighted)","path":"Minimum Spanning Tree (Unweighted)","contentType":"directory"},{"name":"Minimum Spanning Tree","path":"Minimum Spanning Tree","contentType":"directory"},{"name":"MinimumCoinChange","path":"MinimumCoinChange","contentType":"directory"},{"name":"Monty Hall Problem","path":"Monty Hall Problem","contentType":"directory"},{"name":"Multiset","path":"Multiset","contentType":"directory"},{"name":"Myers Difference Algorithm","path":"Myers Difference Algorithm","contentType":"directory"},{"name":"Naive Bayes Classifier","path":"Naive Bayes Classifier","contentType":"directory"},{"name":"Octree","path":"Octree","contentType":"directory"},{"name":"Ordered Array","path":"Ordered Array","contentType":"directory"},{"name":"Ordered Set","path":"Ordered Set","contentType":"directory"},{"name":"Palindromes","path":"Palindromes","contentType":"directory"},{"name":"Points Lines Planes","path":"Points Lines Planes","contentType":"directory"},{"name":"Priority Queue","path":"Priority Queue","contentType":"directory"},{"name":"QuadTree","path":"QuadTree","contentType":"directory"},{"name":"Queue","path":"Queue","contentType":"directory"},{"name":"Quicksort","path":"Quicksort","contentType":"directory"},{"name":"Rabin-Karp","path":"Rabin-Karp","contentType":"directory"},{"name":"Radix Sort","path":"Radix Sort","contentType":"directory"},{"name":"Radix Tree","path":"Radix Tree","contentType":"directory"},{"name":"Red-Black Tree","path":"Red-Black Tree","contentType":"directory"},{"name":"Ring Buffer","path":"Ring Buffer","contentType":"directory"},{"name":"Rootish Array Stack","path":"Rootish Array Stack","contentType":"directory"},{"name":"Run-Length Encoding","path":"Run-Length Encoding","contentType":"directory"},{"name":"Segment Tree","path":"Segment Tree","contentType":"directory"},{"name":"Select Minimum Maximum","path":"Select Minimum Maximum","contentType":"directory"},{"name":"Selection Sampling","path":"Selection Sampling","contentType":"directory"},{"name":"Selection Sort","path":"Selection Sort","contentType":"directory"},{"name":"Set Cover (Unweighted)","path":"Set Cover (Unweighted)","contentType":"directory"},{"name":"Shell Sort","path":"Shell Sort","contentType":"directory"},{"name":"Shortest Path (Unweighted)","path":"Shortest Path (Unweighted)","contentType":"directory"},{"name":"Shuffle","path":"Shuffle","contentType":"directory"},{"name":"Shunting Yard","path":"Shunting Yard","contentType":"directory"},{"name":"Simulated annealing","path":"Simulated annealing","contentType":"directory"},{"name":"Single-Source Shortest Paths (Weighted)","path":"Single-Source Shortest Paths (Weighted)","contentType":"directory"},{"name":"Singly Linked List","path":"Singly Linked List","contentType":"directory"},{"name":"Skip-List","path":"Skip-List","contentType":"directory"},{"name":"Slow Sort","path":"Slow Sort","contentType":"directory"},{"name":"Sorted Set","path":"Sorted Set","contentType":"directory"},{"name":"Sparse Table","path":"Sparse Table","contentType":"directory"},{"name":"Splay Tree","path":"Splay Tree","contentType":"directory"},{"name":"Stack","path":"Stack","contentType":"directory"},{"name":"Strassen Matrix Multiplication","path":"Strassen Matrix Multiplication","contentType":"directory"},{"name":"Ternary Search Tree","path":"Ternary Search Tree","contentType":"directory"},{"name":"Threaded Binary Tree","path":"Threaded Binary Tree","contentType":"directory"},{"name":"Topological Sort","path":"Topological Sort","contentType":"directory"},{"name":"Treap","path":"Treap","contentType":"directory"},{"name":"Tree","path":"Tree","contentType":"directory"},{"name":"Trie","path":"Trie","contentType":"directory"},{"name":"Two-Sum Problem","path":"Two-Sum Problem","contentType":"directory"},{"name":"Union-Find","path":"Union-Find","contentType":"directory"},{"name":"Z-Algorithm","path":"Z-Algorithm","contentType":"directory"},{"name":"swift-algorithm-club.xcworkspace","path":"swift-algorithm-club.xcworkspace","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":".swiftlint.yml","path":".swiftlint.yml","contentType":"file"},{"name":".travis.yml","path":".travis.yml","contentType":"file"},{"name":"Algorithm Design.markdown","path":"Algorithm Design.markdown","contentType":"file"},{"name":"Big-O Notation.markdown","path":"Big-O Notation.markdown","contentType":"file"},{"name":"LICENSE.txt","path":"LICENSE.txt","contentType":"file"},{"name":"README.markdown","path":"README.markdown","contentType":"file"},{"name":"Under Construction.markdown","path":"Under Construction.markdown","contentType":"file"},{"name":"What are Algorithms.markdown","path":"What are Algorithms.markdown","contentType":"file"},{"name":"Why Algorithms.markdown","path":"Why Algorithms.markdown","contentType":"file"},{"name":"gfm-render.sh","path":"gfm-render.sh","contentType":"file"},{"name":"install_swiftlint.sh","path":"install_swiftlint.sh","contentType":"file"}],"totalCount":120}},"fileTreeProcessingTime":5.218559,"foldersToFetch":[],"treeExpanded":true,"symbolsExpanded":false,"csrf_tokens":{"/timrc/swift-algorithm-club/branches":{"post":"vnZ6Az2GV1SLqdrQn7PpIi6jr1IAL92Dge764cyoFn5BzDjJFprgcCZ6HWFS6it-NE_P6yUYxiMWbn54fEopsg"},"/timrc/swift-algorithm-club/branches/fetch_and_merge/master":{"post":"yYxLOvNYTeLJnBCYEmR1RyafGjcSwdblE5yDp4HB1ALYj4Ye2WKaAOk_BMuoylv-CSuOIogsQR1qwULT8Zd5Kg"},"/timrc/swift-algorithm-club/branches/fetch_and_merge/master?discard_changes=true":{"post":"zoM1TQbangOVWGU_mOO4jAjzazmczhqUVbqAZsagQgffgPhpLOBJ4bX7cWwiTZY1J0f_LAYjjWws50EStvbvLw"}}},"title":"swift-algorithm-club/Trie at master · timrc/swift-algorithm-club","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-b3c7e81bdc2f.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-8572513277ba.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true}}}
You can’t perform that action at this time.