CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Trie - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"a6658c7c-e1a8-4471-b24d-2dcbeb6ff8ed","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Trie","wgTitle":"Trie","wgCurRevisionId":1250000773,"wgRevisionId":1250000773,"wgArticleId":31274,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Good articles","Commons category link from Wikidata","Articles with example Python (programming language) code","Trees (data structures)","Finite automata"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Trie","wgRelevantArticleId":31274,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[], "wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q387015","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false, "wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init", "ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/1200px-Trie_example.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1125"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/800px-Trie_example.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="750"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/640px-Trie_example.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="600"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Trie - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Trie"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Trie&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Trie"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Trie rootpage-Trie skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Trie" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Trie" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Trie" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Trie" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-History,_etymology,_and_pronunciation" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#History,_etymology,_and_pronunciation"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>History, etymology, and pronunciation</span> </div> </a> <ul id="toc-History,_etymology,_and_pronunciation-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Overview" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Overview"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Overview</span> </div> </a> <ul id="toc-Overview-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Operations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Operations</span> </div> </a> <button aria-controls="toc-Operations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Operations subsection</span> </button> <ul id="toc-Operations-sublist" class="vector-toc-list"> <li id="toc-Searching" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Searching"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Searching</span> </div> </a> <ul id="toc-Searching-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Insertion" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Insertion"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Insertion</span> </div> </a> <ul id="toc-Insertion-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Deletion" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Deletion"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Deletion</span> </div> </a> <ul id="toc-Deletion-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Replacing_other_data_structures" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Replacing_other_data_structures"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Replacing other data structures</span> </div> </a> <button aria-controls="toc-Replacing_other_data_structures-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Replacing other data structures subsection</span> </button> <ul id="toc-Replacing_other_data_structures-sublist" class="vector-toc-list"> <li id="toc-Replacement_for_hash_tables" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Replacement_for_hash_tables"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Replacement for hash tables</span> </div> </a> <ul id="toc-Replacement_for_hash_tables-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Implementation_strategies" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Implementation_strategies"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Implementation strategies</span> </div> </a> <button aria-controls="toc-Implementation_strategies-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Implementation strategies subsection</span> </button> <ul id="toc-Implementation_strategies-sublist" class="vector-toc-list"> <li id="toc-Bitwise_tries" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bitwise_tries"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Bitwise tries</span> </div> </a> <ul id="toc-Bitwise_tries-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Compressed_tries" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Compressed_tries"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2</span> <span>Compressed tries</span> </div> </a> <ul id="toc-Compressed_tries-sublist" class="vector-toc-list"> <li id="toc-Patricia_trees" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Patricia_trees"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2.1</span> <span>Patricia trees</span> </div> </a> <ul id="toc-Patricia_trees-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Applications</span> </div> </a> <button aria-controls="toc-Applications-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Applications subsection</span> </button> <ul id="toc-Applications-sublist" class="vector-toc-list"> <li id="toc-Sorting" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Sorting"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.1</span> <span>Sorting</span> </div> </a> <ul id="toc-Sorting-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Full-text_search" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Full-text_search"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.2</span> <span>Full-text search</span> </div> </a> <ul id="toc-Full-text_search-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Web_search_engines" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Web_search_engines"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.3</span> <span>Web search engines</span> </div> </a> <ul id="toc-Web_search_engines-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bioinformatics" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bioinformatics"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.4</span> <span>Bioinformatics</span> </div> </a> <ul id="toc-Bioinformatics-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Internet_routing" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Internet_routing"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.5</span> <span>Internet routing</span> </div> </a> <ul id="toc-Internet_routing-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Trie</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 23 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-23" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">23 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%A7%D9%84%D8%B4%D8%AC%D8%B1%D8%A9_%D8%A7%D9%84%D8%B1%D9%82%D9%85%D9%8A%D8%A9" title="الشجرة الرقمية – Arabic" lang="ar" hreflang="ar" data-title="الشجرة الرقمية" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-be mw-list-item"><a href="https://be.wikipedia.org/wiki/%D0%9F%D1%80%D1%8D%D1%84%D1%96%D0%BA%D1%81%D0%BD%D0%B0%D0%B5_%D0%B4%D1%80%D1%8D%D0%B2%D0%B0" title="Прэфікснае дрэва – Belarusian" lang="be" hreflang="be" data-title="Прэфікснае дрэва" data-language-autonym="Беларуская" data-language-local-name="Belarusian" class="interlanguage-link-target"><span>Беларуская</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Trie" title="Trie – Catalan" lang="ca" hreflang="ca" data-title="Trie" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Trie" title="Trie – Czech" lang="cs" hreflang="cs" data-title="Trie" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Trie" title="Trie – German" lang="de" hreflang="de" data-title="Trie" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-et mw-list-item"><a href="https://et.wikipedia.org/wiki/Prefiksipuu" title="Prefiksipuu – Estonian" lang="et" hreflang="et" data-title="Prefiksipuu" data-language-autonym="Eesti" data-language-local-name="Estonian" class="interlanguage-link-target"><span>Eesti</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Trie" title="Trie – Spanish" lang="es" hreflang="es" data-title="Trie" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D9%BE%DB%8C%D8%B4%D9%88%D9%86%D8%AF%DB%8C" title="درخت پیشوندی – Persian" lang="fa" hreflang="fa" data-title="درخت پیشوندی" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Trie_(informatique)" title="Trie (informatique) – French" lang="fr" hreflang="fr" data-title="Trie (informatique)" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/Trie" title="Trie – Galician" lang="gl" hreflang="gl" data-title="Trie" data-language-autonym="Galego" data-language-local-name="Galician" class="interlanguage-link-target"><span>Galego</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)" title="트라이 (컴퓨팅) – Korean" lang="ko" hreflang="ko" data-title="트라이 (컴퓨팅)" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Trie" title="Trie – Italian" lang="it" hreflang="it" data-title="Trie" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/Trie" title="Trie – Hebrew" lang="he" hreflang="he" data-title="Trie" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)" title="トライ (データ構造) – Japanese" lang="ja" hreflang="ja" data-title="トライ (データ構造)" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Drzewo_trie" title="Drzewo trie – Polish" lang="pl" hreflang="pl" data-title="Drzewo trie" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Trie" title="Trie – Portuguese" lang="pt" hreflang="pt" data-title="Trie" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Префиксное дерево – Russian" lang="ru" hreflang="ru" data-title="Префиксное дерево" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Trie" title="Trie – Simple English" lang="en-simple" hreflang="en-simple" data-title="Trie" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target"><span>Simple English</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%A2%D1%80%D0%B8%D0%B5" title="Трие – Serbian" lang="sr" hreflang="sr" data-title="Трие" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%97%E0%B8%A3%E0%B8%B1%E0%B8%A2_(%E0%B9%82%E0%B8%84%E0%B8%A3%E0%B8%87%E0%B8%AA%E0%B8%A3%E0%B9%89%E0%B8%B2%E0%B8%87%E0%B8%82%E0%B9%89%E0%B8%AD%E0%B8%A1%E0%B8%B9%E0%B8%A5)" title="ทรัย (โครงสร้างข้อมูล) – Thai" lang="th" hreflang="th" data-title="ทรัย (โครงสร้างข้อมูล)" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D1%84%D1%96%D0%BA%D1%81%D0%BD%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="Префіксне дерево – Ukrainian" lang="uk" hreflang="uk" data-title="Префіксне дерево" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/Trie" title="Trie – Vietnamese" lang="vi" hreflang="vi" data-title="Trie" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/Trie" title="Trie – Chinese" lang="zh" hreflang="zh" data-title="Trie" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q387015#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Trie" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Trie" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Trie"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Trie&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Trie&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Trie"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Trie&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Trie&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Trie" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Trie" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Trie&oldid=1250000773" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Trie&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Trie&id=1250000773&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FTrie"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FTrie"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Trie&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Trie&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Trie" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q387015" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> <div id="mw-indicator-good-star" class="mw-indicator"><div class="mw-parser-output"><span typeof="mw:File"><a href="/wiki/Wikipedia:Good_articles*" title="This is a good article. Click here for more information."><img alt="This is a good article. Click here for more information." src="//upload.wikimedia.org/wikipedia/en/thumb/9/94/Symbol_support_vote.svg/19px-Symbol_support_vote.svg.png" decoding="async" width="19" height="20" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/94/Symbol_support_vote.svg/29px-Symbol_support_vote.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/94/Symbol_support_vote.svg/39px-Symbol_support_vote.svg.png 2x" data-file-width="180" data-file-height="185" /></a></span></div></div> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Search tree data structure</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable"><span>This article is about a specific type of tree data structure. For tree data structures generally, see <a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">tree (data structure)</a>.</span> <span>For other uses of "tree", see <a href="/wiki/Tree_(disambiguation)" class="mw-disambig" title="Tree (disambiguation)">tree (disambiguation)</a>.</span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="/wiki/Tri_(disambiguation)" class="mw-redirect mw-disambig" title="Tri (disambiguation)">tri</a>, <a href="/wiki/Try_(disambiguation)" class="mw-redirect mw-disambig" title="Try (disambiguation)">try</a>, or <a href="/wiki/Tray" title="Tray">tray</a>.</div> <p class="mw-empty-elt"> </p> <style data-mw-deduplicate="TemplateStyles:r1257001546">.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme) div:not(.notheme){background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table tr{display:table-row!important}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Trie</th></tr><tr><th scope="row" class="infobox-label"><a href="/wiki/List_of_data_structures" title="List of data structures">Type</a></th><td class="infobox-data">Tree</td></tr><tr><th scope="row" class="infobox-label">Invented</th><td class="infobox-data">1960</td></tr><tr><th scope="row" class="infobox-label">Invented by</th><td class="infobox-data"><a href="/wiki/Edward_Fredkin" title="Edward Fredkin">Edward Fredkin</a>, <a href="/wiki/Axel_Thue" title="Axel Thue">Axel Thue</a>, and René de la Briandais</td></tr><tr><td colspan="2" class="infobox-full-data"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1257001546"><table class="infobox-subbox infobox-3cols-child infobox-table"><tbody><tr><th colspan="4" class="infobox-header"><a href="/wiki/Time_complexity" title="Time complexity">Time complexity</a> in <a href="/wiki/Big_O_notation" title="Big O notation">big O notation</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Operation</th><td class="infobox-data infobox-data-a"> <b>Average</b></td><td class="infobox-data infobox-data-b"> <b>Worst case</b></td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Search</th><td class="infobox-data infobox-data-a"> <span class="texhtml">O(<i>n</i>)</span></td><td class="infobox-data infobox-data-b"> <span class="texhtml">O(<i>n</i>)</span></td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Insert</th><td class="infobox-data infobox-data-a"> <span class="texhtml">O(<i>n</i>)</span></td><td class="infobox-data infobox-data-b"> <span class="texhtml">O(<i>n</i>)</span></td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Delete</th><td class="infobox-data infobox-data-a"> <span class="texhtml">O(<i>n</i>)</span></td><td class="infobox-data infobox-data-b"> <span class="texhtml">O(<i>n</i>)</span></td></tr><tr><th colspan="4" class="infobox-header"><a href="/wiki/Space_complexity" title="Space complexity">Space complexity</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Space</th><td class="infobox-data infobox-data-a"> <span class="texhtml">O(<i>n</i>)</span></td><td class="infobox-data infobox-data-b"> <span class="texhtml">O(<i>n</i>)</span></td></tr></tbody></table></td></tr></tbody></table> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Trie_example.svg" class="mw-file-description"><img alt="Depiction of a trie. Single empty circle, representing the root node, points to three children. The arrow to each child is marked by a different letter. The children themselves have similar set of arrows and child nodes, with nodes that correspond to full words bearing blue integer values." src="//upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/250px-Trie_example.svg.png" decoding="async" width="250" height="234" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/375px-Trie_example.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/500px-Trie_example.svg.png 2x" data-file-width="400" data-file-height="375" /></a><figcaption>A trie for keys "A", "to", "tea", "ted", "ten", "i", "in", and "inn". Each complete English word has an arbitrary integer value associated with it.</figcaption></figure> <p>In computer science, a <b>trie</b> (<span class="rt-commentedText nowrap"><span class="IPA nopopups noexcerpt" lang="en-fonipa"><a href="/wiki/Help:IPA/English" title="Help:IPA/English">/<span style="border-bottom:1px dotted"><span title="/ˈ/: primary stress follows">ˈ</span><span title="'t' in 'tie'">t</span><span title="'r' in 'rye'">r</span><span title="/aɪ/: 'i' in 'tide'">aɪ</span></span>/</a></span></span>, <span class="rt-commentedText nowrap"><span class="IPA nopopups noexcerpt" lang="en-fonipa"><a href="/wiki/Help:IPA/English" title="Help:IPA/English">/<span style="border-bottom:1px dotted"><span title="/ˈ/: primary stress follows">ˈ</span><span title="'t' in 'tie'">t</span><span title="'r' in 'rye'">r</span><span title="/iː/: 'ee' in 'fleece'">iː</span></span>/</a></span></span>), also called <b>digital tree</b> or <b>prefix tree</b>,<sup id="cite_ref-cvr14_1-0" class="reference"><a href="#cite_note-cvr14-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> is a type of <a href="/wiki/Search_tree" title="Search tree">search tree</a>: specifically, a <a href="/wiki/M-ary_tree" title="M-ary tree"><i>k</i>-ary tree</a> data structure used for locating specific keys from within a set. These keys are most often <a href="/wiki/String_(computer_science)" title="String (computer science)">strings</a>, with links between nodes defined not by the entire key, but by individual <a href="/wiki/Character_(computing)" title="Character (computing)">characters</a>. In order to access a key (to recover its value, change it, or remove it), the trie is traversed <a href="/wiki/Depth-first_search" title="Depth-first search">depth-first</a>, following the links between nodes, which represent each character in the key. </p><p>Unlike a <a href="/wiki/Binary_search_tree" title="Binary search tree">binary search tree</a>, nodes in the trie do not store their associated key. Instead, a node's <i>position</i> in the trie defines the key with which it is associated. This distributes the value of each key across the data structure, and means that not every node necessarily has an associated value. </p><p>All the children of a node have a common <a href="/wiki/Prefix_(computer_science)" class="mw-redirect" title="Prefix (computer science)">prefix</a> of the string associated with that parent node, and the root is associated with the <a href="/wiki/Empty_string" title="Empty string">empty string</a>. This task of storing data accessible by its prefix can be accomplished in a memory-optimized way by employing a <a href="/wiki/Radix_tree" title="Radix tree">radix tree</a>. </p><p>Though tries can be keyed by character strings, they need not be. The same algorithms can be adapted for ordered lists of any underlying type, e.g. <a href="/wiki/Permutation" title="Permutation">permutations</a> of digits or shapes. In particular, a <b>bitwise trie</b> is keyed on the <a href="/wiki/Bit_(computing)" class="mw-redirect" title="Bit (computing)">individual bits</a> making up a piece of fixed-length binary data, such as an <a href="/wiki/Integer_(computer_science)" title="Integer (computer science)">integer</a> or <a href="/wiki/Memory_address" title="Memory address">memory address</a>. The key <a href="/wiki/Lookup_complexity" class="mw-redirect" title="Lookup complexity">lookup complexity</a> of a trie remains proportional to the key size. Specialized trie implementations such as compressed tries are used to deal with the enormous space requirement of a trie in naive implementations. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="History,_etymology,_and_pronunciation"><span id="History.2C_etymology.2C_and_pronunciation"></span>History, etymology, and pronunciation</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=1" title="Edit section: History, etymology, and pronunciation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The idea of a trie for representing a set of strings was first abstractly described by <a href="/wiki/Axel_Thue" title="Axel Thue">Axel Thue</a> in 1912.<sup id="cite_ref-thue_2-0" class="reference"><a href="#cite_note-thue-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-KnuthVol3_3-0" class="reference"><a href="#cite_note-KnuthVol3-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Tries were first described in a computer context by René de la Briandais in 1959.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-KnuthVol3_3-1" class="reference"><a href="#cite_note-KnuthVol3-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-brass_5-0" class="reference"><a href="#cite_note-brass-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 336">: 336 </span></sup> </p><p>The idea was independently described in 1960 by <a href="/wiki/Edward_Fredkin" title="Edward Fredkin">Edward Fredkin</a>,<sup id="cite_ref-triememory_6-0" class="reference"><a href="#cite_note-triememory-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> who coined the term <i>trie</i>, pronouncing it <span class="rt-commentedText nowrap"><span class="IPA nopopups noexcerpt" lang="en-fonipa"><a href="/wiki/Help:IPA/English" title="Help:IPA/English">/<span style="border-bottom:1px dotted"><span title="/ˈ/: primary stress follows">ˈ</span><span title="'t' in 'tie'">t</span><span title="'r' in 'rye'">r</span><span title="/iː/: 'ee' in 'fleece'">iː</span></span>/</a></span></span> (as "tree"), after the middle syllable of <i>retrieval</i>.<sup id="cite_ref-DADS_7-0" class="reference"><a href="#cite_note-DADS-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Liang1983_8-0" class="reference"><a href="#cite_note-Liang1983-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> However, other authors pronounce it <span class="rt-commentedText nowrap"><span class="IPA nopopups noexcerpt" lang="en-fonipa"><a href="/wiki/Help:IPA/English" title="Help:IPA/English">/<span style="border-bottom:1px dotted"><span title="/ˈ/: primary stress follows">ˈ</span><span title="'t' in 'tie'">t</span><span title="'r' in 'rye'">r</span><span title="/aɪ/: 'i' in 'tide'">aɪ</span></span>/</a></span></span> (as "try"), in an attempt to distinguish it verbally from "tree".<sup id="cite_ref-DADS_7-1" class="reference"><a href="#cite_note-DADS-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Liang1983_8-1" class="reference"><a href="#cite_note-Liang1983-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-KnuthVol3_3-2" class="reference"><a href="#cite_note-KnuthVol3-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=2" title="Edit section: Overview"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Tries are a form of string-indexed look-up data structure, which is used to store a dictionary list of words that can be searched on in a manner that allows for efficient generation of <a href="/wiki/Autocomplete" title="Autocomplete">completion lists</a>.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 1">: 1 </span></sup> A prefix trie is an <a href="/wiki/Ordered_tree" class="mw-redirect" title="Ordered tree">ordered tree</a> data structure used in the representation of a set of strings over a finite alphabet set, which allows efficient storage of words with common prefixes.<sup id="cite_ref-cvr14_1-1" class="reference"><a href="#cite_note-cvr14-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p>Tries can be efficacious on <a href="/wiki/String-searching_algorithm" title="String-searching algorithm">string-searching algorithms</a> such as <a href="/wiki/Predictive_text" title="Predictive text">predictive text</a>, <a href="/wiki/Approximate_string_matching" title="Approximate string matching">approximate string matching</a>, and <a href="/wiki/Spell_checking" class="mw-redirect" title="Spell checking">spell checking</a> in comparison to binary search trees.<sup id="cite_ref-aho75_11-0" class="reference"><a href="#cite_note-aho75-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Liang1983_8-2" class="reference"><a href="#cite_note-Liang1983-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-reema18_12-0" class="reference"><a href="#cite_note-reema18-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 358">: 358 </span></sup> A trie can be seen as a tree-shaped <a href="/wiki/Deterministic_finite_automaton" title="Deterministic finite automaton">deterministic finite automaton</a>.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Operations">Operations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=3" title="Edit section: Operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Trie_representation.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c0/Trie_representation.png/400px-Trie_representation.png" decoding="async" width="400" height="158" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c0/Trie_representation.png/600px-Trie_representation.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c0/Trie_representation.png/800px-Trie_representation.png 2x" data-file-width="1053" data-file-height="416" /></a><figcaption>Trie representation of the string sets: sea, sells, and she.</figcaption></figure> <p>Tries support various operations: insertion, deletion, and lookup of a string key. Tries are composed of nodes that contain links, which either point to other suffix child nodes or <i>null</i>. As for every tree, each node but the root is pointed to by only one other node, called its <i>parent</i>. Each node contains as many links as the number of characters in the applicable <a href="/wiki/Alphabet_(formal_languages)" title="Alphabet (formal languages)">alphabet</a> (although tries tend to have a substantial number of null links). In some cases, the alphabet used is simply that of the <a href="/wiki/Character_encoding" title="Character encoding">character encoding</a>—resulting in, for example, a size of 256 in the case of (unsigned) <a href="/wiki/ASCII" title="ASCII">ASCII</a>.<sup id="cite_ref-robert11_14-0" class="reference"><a href="#cite_note-robert11-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 732">: 732 </span></sup> </p><p>The null links within the children of a node emphasize the following characteristics:<sup id="cite_ref-robert11_14-1" class="reference"><a href="#cite_note-robert11-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 734">: 734 </span></sup><sup id="cite_ref-brass_5-1" class="reference"><a href="#cite_note-brass-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 336">: 336 </span></sup> </p> <ol><li>Characters and string keys are implicitly stored in the trie, and include a character <a href="/wiki/Sentinel_value" title="Sentinel value">sentinel value</a> indicating string termination.</li> <li>Each node contains one possible link to a <a href="/wiki/Prefix" title="Prefix">prefix</a> of strong keys of the set.</li></ol> <p>A basic <a href="/wiki/Composite_data_type" title="Composite data type">structure type</a> of nodes in the trie is as follows; <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Node}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>Node</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{Node}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cabf40beef6b74eccc3111ca1d3ad46e193b891" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.23ex; height:2.176ex;" alt="{\displaystyle {\text{Node}}}"></span> may contain an optional <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Value}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>Value</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{Value}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/59e4e2326758050572cdc00ba44c87ca4cf5fb86" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.877ex; height:2.176ex;" alt="{\displaystyle {\text{Value}}}"></span>, which is associated with each key stored in the last character of string, or terminal node. </p> <table> <tbody><tr style="vertical-align:top"> <td> <pre><b>structure</b> Node Children <b>Node[</b><i>Alphabet-Size</i><b>]</b> Is-Terminal <b>Boolean</b> Value <b>Data-Type</b> <b>end structure</b> </pre> </td></tr></tbody></table> <div class="mw-heading mw-heading3"><h3 id="Searching">Searching</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=4" title="Edit section: Searching"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Searching for a value in a trie is guided by the characters in the search string key, as each node in the trie contains a corresponding link to each possible character in the given string. Thus, following the string within the trie yields the associated value for the given string key. A null link during the search indicates the inexistence of the key.<sup id="cite_ref-robert11_14-2" class="reference"><a href="#cite_note-robert11-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 732-733">: 732-733 </span></sup> </p><p>The following pseudocode implements the search procedure for a given string <style data-mw-deduplicate="TemplateStyles:r886049734">.mw-parser-output .monospaced{font-family:monospace,monospace}</style><span class="monospaced">key</span> in a rooted trie <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">x</span>.<sup id="cite_ref-gonnet91_15-0" class="reference"><a href="#cite_note-gonnet91-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 135">: 135 </span></sup> </p> <table> <tbody><tr style="vertical-align:top"> <td> <pre>Trie-Find(x, key) <b>for</b> 0 ≤ i < key.length <b>do</b> <b>if</b> x.Children[key[i]] = nil <b>then</b> <b>return</b> false <b>end if</b> x := x.Children[key[i]] <b>repeat</b> <b>return</b> x.Value </pre> </td></tr></tbody></table> <p>In the above pseudocode, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">x</span> and <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">key</span> correspond to the pointer of trie's root node and the string key respectively. The search operation, in a standard trie, takes <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\text{dm}})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>dm</mtext> </mrow> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O({\text{dm}})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0dd01f3d292bc51089f1f5d7f71f2c50ae734c9b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.811ex; height:2.843ex;" alt="{\displaystyle O({\text{dm}})}"></span> time, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{m}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>m</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{m}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f0bc572b5b756f7664b00d78664d45ffd067ab2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.936ex; height:1.676ex;" alt="{\displaystyle {\text{m}}}"></span> is the size of the string parameter <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{key}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>key</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{key}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc268562460c208c54914d6659d7ca87231c4770" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.487ex; height:2.509ex;" alt="{\displaystyle {\text{key}}}"></span>, and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{d}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>d</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{d}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/456bbc5b1f688ef084982272e2f620fbd6634324" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.293ex; height:2.176ex;" alt="{\displaystyle {\text{d}}}"></span> corresponds to the <a href="/wiki/Alphabet_(formal_languages)" title="Alphabet (formal languages)">alphabet size</a>.<sup id="cite_ref-patil_12_16-0" class="reference"><a href="#cite_note-patil_12-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 754">: 754 </span></sup> <a href="/wiki/Binary_search_trees" class="mw-redirect" title="Binary search trees">Binary search trees</a>, on the other hand, take <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(m\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b5506080ab4729276d04139ae5593fbbe9571884" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.764ex; height:2.843ex;" alt="{\displaystyle O(m\log n)}"></span> in the worst case, since the search depends on the height of the tree (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \log n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/317ab5292da7c7935aec01a570461fe0613b21d5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.754ex; height:2.509ex;" alt="{\displaystyle \log n}"></span>) of the BST (in case of <a href="/wiki/Balanced_tree" class="mw-redirect" title="Balanced tree">balanced trees</a>), where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>n</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/eaaf79c97c17e3d4d0a55bc13e965bacfbff279e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.293ex; height:1.676ex;" alt="{\displaystyle {\text{n}}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{m}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>m</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{m}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1f0bc572b5b756f7664b00d78664d45ffd067ab2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.936ex; height:1.676ex;" alt="{\displaystyle {\text{m}}}"></span> being number of keys and the length of the keys.<sup id="cite_ref-reema18_12-1" class="reference"><a href="#cite_note-reema18-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 358">: 358 </span></sup> </p><p>The trie occupies less space in comparison with a BST in the case of a large number of short strings, since nodes share common initial string subsequences and store the keys implicitly.<sup id="cite_ref-reema18_12-2" class="reference"><a href="#cite_note-reema18-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 358">: 358 </span></sup> The terminal node of the tree contains a non-null value, and it is a search <i>hit</i> if the associated value is found in the trie, and search <i>miss</i> if it is not.<sup id="cite_ref-robert11_14-3" class="reference"><a href="#cite_note-robert11-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 733">: 733 </span></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Insertion">Insertion</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=5" title="Edit section: Insertion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Insertion into trie is guided by using the <a href="/wiki/Character_encoding#Character_sets,_character_maps_and_code_pages" title="Character encoding">character sets</a> as indexes to the children array until the last character of the string key is reached.<sup id="cite_ref-robert11_14-4" class="reference"><a href="#cite_note-robert11-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 733-734">: 733-734 </span></sup> Each node in the trie corresponds to one call of the <a href="/wiki/Radix_sorting" class="mw-redirect" title="Radix sorting">radix sorting</a> routine, as the trie structure reflects the execution of pattern of the top-down radix sort.<sup id="cite_ref-gonnet91_15-1" class="reference"><a href="#cite_note-gonnet91-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 135">: 135 </span></sup> </p> <table> <tbody><tr style="vertical-align:top"> <td> <pre>1 2 3 4 5 6 7 8 9 </pre> </td> <td> <pre>Trie-Insert(x, key, value) <b>for</b> 0 ≤ i < key.length <b>do</b> <b>if</b> x.Children[key[i]] = nil <b>then</b> x.Children[key[i]] := Node() <b>end if</b> x := x.Children[key[i]] <b>repeat</b> x.Value := value x.Is-Terminal := True </pre> </td></tr></tbody></table> <p>If a null link is encountered prior to reaching the last character of the string key, a new node is created (line 3).<sup id="cite_ref-robert11_14-5" class="reference"><a href="#cite_note-robert11-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 745">: 745 </span></sup> The value of the terminal node is assigned to the input value; therefore, if the former was non-null at the time of insertion, it is substituted with the new value. </p> <div class="mw-heading mw-heading3"><h3 id="Deletion">Deletion</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=6" title="Edit section: Deletion"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Deletion of a <a href="/wiki/Key%E2%80%93value_pair" class="mw-redirect" title="Key–value pair">key–value pair</a> from a trie involves finding the terminal node with the corresponding string key, marking the terminal indicator and value to <i>false</i> and null correspondingly.<sup id="cite_ref-robert11_14-6" class="reference"><a href="#cite_note-robert11-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 740">: 740 </span></sup> </p><p>The following is a <a href="/wiki/Recursion_(computer_science)" title="Recursion (computer science)">recursive</a> procedure for removing a string <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">key</span> from rooted trie (<link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">x</span>). </p> <table> <tbody><tr style="vertical-align:top"> <td style="text-align: right"> <pre>1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 </pre> </td> <td> <pre>Trie-Delete(x, key) <b>if</b> key = nil <b>then</b> <b>if</b> x.Is-Terminal = True <b>then</b> x.Is-Terminal := False x.Value := nil <b>end if</b> <b>for</b> 0 ≤ i < x.Children.length <b>if</b> x.Children[i] != nil <b>return</b> x <b>end if</b> <b>repeat</b> <b>return</b> nil <b>end if</b> x.Children[key[0]] := Trie-Delete(x.Children[key[0]], key[1:]) <b>return</b> x </pre> </td></tr></tbody></table> <p>The procedure begins by examining the <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">key</span>; null denotes the arrival of a terminal node or end of a string key. If the node is terminal it has no children, it is removed from the trie (line 14). However, an end of string key without the node being terminal indicates that the key does not exist, thus the procedure does not modify the trie. The recursion proceeds by incrementing <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">key</span>'s index. </p> <div class="mw-heading mw-heading2"><h2 id="Replacing_other_data_structures">Replacing other data structures</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=7" title="Edit section: Replacing other data structures"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Replacement_for_hash_tables">Replacement for hash tables</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=8" title="Edit section: Replacement for hash tables"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A trie can be used to replace a <a href="/wiki/Hash_table" title="Hash table">hash table</a>, over which it has the following advantages:<sup id="cite_ref-reema18_12-3" class="reference"><a href="#cite_note-reema18-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 358">: 358 </span></sup> </p> <ul><li>Searching for a node with an associated key of size <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>m</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle m}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}"></span> has the complexity of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(m)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a0ffd498cf521ce19814e6b7053f1f8ebb1d3c88" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.623ex; height:2.843ex;" alt="{\displaystyle O(m)}"></span>, whereas an imperfect hash function may have numerous colliding keys, and the worst-case lookup speed of such a table would be <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/78484c5c26cfc97bb3b915418caa09454421e80b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.646ex; height:2.843ex;" alt="{\displaystyle O(N)}"></span>, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> denotes the total number of nodes within the table.</li> <li>Tries do not need a hash function for the operation, unlike a hash table; there are also no <a href="/wiki/Hash_collision" title="Hash collision">collisions</a> of different keys in a trie.</li> <li>Buckets in a trie, which are analogous to hash table buckets that store key collisions, are necessary only if a single key is associated with more than one value.</li> <li>String keys within the trie can be sorted using a predetermined alphabetical ordering.</li></ul> <p>However, tries are less efficient than a hash table when the data is directly accessed on a <a href="/wiki/Computer_data_storage#Secondary_storage" title="Computer data storage">secondary storage device</a> such as a hard disk drive that has higher <a href="/wiki/Random_access" title="Random access">random access</a> time than the <a href="/wiki/Main_memory" class="mw-redirect" title="Main memory">main memory</a>.<sup id="cite_ref-triememory_6-1" class="reference"><a href="#cite_note-triememory-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> Tries are also disadvantageous when the key value cannot be easily represented as string, such as <a href="/wiki/Floating_point_numbers" class="mw-redirect" title="Floating point numbers">floating point numbers</a> where multiple representations are possible (e.g. 1 is equivalent to 1.0, +1.0, 1.00, etc.),<sup id="cite_ref-reema18_12-4" class="reference"><a href="#cite_note-reema18-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 359">: 359 </span></sup> however it can be unambiguously represented as a <a href="/wiki/Binary_number" title="Binary number">binary number</a> in <a href="/wiki/IEEE_754" title="IEEE 754">IEEE 754</a>, in comparison to <a href="/wiki/Two%27s_complement" title="Two's complement">two's complement</a> format.<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Implementation_strategies">Implementation strategies</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=9" title="Edit section: Implementation strategies"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Pointer_implementation_of_a_trie.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/5/5d/Pointer_implementation_of_a_trie.svg/220px-Pointer_implementation_of_a_trie.svg.png" decoding="async" width="220" height="232" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/5d/Pointer_implementation_of_a_trie.svg/330px-Pointer_implementation_of_a_trie.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/5d/Pointer_implementation_of_a_trie.svg/440px-Pointer_implementation_of_a_trie.svg.png 2x" data-file-width="393" data-file-height="415" /></a><figcaption>A trie implemented as a <a href="/wiki/Left-child_right-sibling_binary_tree" title="Left-child right-sibling binary tree">left-child right-sibling binary tree</a>: vertical arrows are <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">child</span> pointers, dotted horizontal arrows are <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">next</span> pointers. The set of strings stored in this trie is <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">{baby, bad, bank, box, dad, dance</span>}. The lists are sorted to allow traversal in lexicographic order.</figcaption></figure> <p>Tries can be represented in several ways, corresponding to different trade-offs between memory use and speed of the operations.<sup id="cite_ref-brass_5-2" class="reference"><a href="#cite_note-brass-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 341">: 341 </span></sup> Using a vector of pointers for representing a trie consumes enormous space; however, memory space can be reduced at the expense of running time if a <a href="/wiki/Singly_linked_list" class="mw-redirect" title="Singly linked list">singly linked list</a> is used for each node vector, as most entries of the vector contains <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{nil}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>nil</mtext> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{nil}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1bed082db02b6e83a9bc91a2059ba56ff20860ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.586ex; height:2.176ex;" alt="{\displaystyle {\text{nil}}}"></span>.<sup id="cite_ref-KnuthVol3_3-3" class="reference"><a href="#cite_note-KnuthVol3-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 495">: 495 </span></sup> </p><p>Techniques such as <i>alphabet reduction</i> may alleviate the high space complexity by reinterpreting the original string as a long string over a smaller alphabet i.e. a string of <span class="texhtml mvar" style="font-style:italic;">n</span> bytes can alternatively be regarded as a string of <span class="texhtml">2<i>n</i></span> <a href="/wiki/Nibble" title="Nibble">four-bit units</a> and stored in a trie with sixteen pointers per node. However, lookups need to visit twice as many nodes in the worst-case, although space requirements go down by a factor of eight.<sup id="cite_ref-brass_5-3" class="reference"><a href="#cite_note-brass-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 347–352">: 347–352 </span></sup> Other techniques include storing a vector of 256 ASCII pointers as a bitmap of 256 bits representing ASCII alphabet, which reduces the size of individual nodes dramatically.<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Bitwise_tries">Bitwise tries</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=10" title="Edit section: Bitwise tries"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/X-fast_trie" title="X-fast trie">x-fast trie</a> and <a href="/wiki/Bitwise_trie_with_bitmap" title="Bitwise trie with bitmap">Bitwise trie with bitmap</a></div> <p>Bitwise tries are used to address the enormous space requirement for the trie nodes in a naive simple pointer vector implementations. Each character in the string key set is represented via individual bits, which are used to traverse the trie over a string key. The implementations for these types of trie use <a href="/wiki/SIMD" class="mw-redirect" title="SIMD">vectorized</a> CPU instructions to <a href="/wiki/Find_first_set" title="Find first set">find the first set bit</a> in a fixed-length key input (e.g. <a href="/wiki/GNU_Compiler_Collection" title="GNU Compiler Collection">GCC</a>'s <code>__builtin_clz()</code> <a href="/wiki/Intrinsic_function" title="Intrinsic function">intrinsic function</a>). Accordingly, the set bit is used to index the first item, or child node, in the 32- or 64-entry based bitwise tree. Search then proceeds by testing each subsequent bit in the key.<sup id="cite_ref-willar83_19-0" class="reference"><a href="#cite_note-willar83-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> </p><p>This procedure is also <a href="/wiki/Locality_of_reference" title="Locality of reference">cache-local</a> and <a href="/wiki/Parallel_programming_model" title="Parallel programming model">highly parallelizable</a> due to <a href="/wiki/CPU_register" class="mw-redirect" title="CPU register">register</a> independency, and thus performant on <a href="/wiki/Out-of-order_execution" title="Out-of-order execution">out-of-order execution</a> CPUs.<sup id="cite_ref-willar83_19-1" class="reference"><a href="#cite_note-willar83-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Compressed_tries">Compressed tries</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=11" title="Edit section: Compressed tries"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Radix_tree" title="Radix tree">Radix tree</a></div> <p><a href="/wiki/Radix_tree" title="Radix tree">Radix tree</a>, also known as a <b>compressed trie</b>, is a space-optimized variant of a trie in which any node with only one child gets merged with its parent; elimination of branches of the nodes with a single child results in better metrics in both space and time.<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 452">: 452 </span></sup> This works best when the trie remains static and set of keys stored are very sparse within their representation space.<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 3–16">: 3–16 </span></sup> </p><p>One more approach is to "pack" the trie, in which a space-efficient implementation of a sparse packed trie applied to automatic <a href="/wiki/Hyphenation_algorithm" class="mw-redirect" title="Hyphenation algorithm">hyphenation</a>, in which the descendants of each node may be interleaved in memory.<sup id="cite_ref-Liang1983_8-3" class="reference"><a href="#cite_note-Liang1983-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading4"><h4 id="Patricia_trees">Patricia trees</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=12" title="Edit section: Patricia trees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1237032888/mw-parser-output/.tmulti">.mw-parser-output .tmulti .multiimageinner{display:flex;flex-direction:column}.mw-parser-output .tmulti .trow{display:flex;flex-direction:row;clear:left;flex-wrap:wrap;width:100%;box-sizing:border-box}.mw-parser-output .tmulti .tsingle{margin:1px;float:left}.mw-parser-output .tmulti .theader{clear:both;font-weight:bold;text-align:center;align-self:center;background-color:transparent;width:100%}.mw-parser-output .tmulti .thumbcaption{background-color:transparent}.mw-parser-output .tmulti .text-align-left{text-align:left}.mw-parser-output .tmulti .text-align-right{text-align:right}.mw-parser-output .tmulti .text-align-center{text-align:center}@media all and (max-width:720px){.mw-parser-output .tmulti .thumbinner{width:100%!important;box-sizing:border-box;max-width:none!important;align-items:center}.mw-parser-output .tmulti .trow{justify-content:center}.mw-parser-output .tmulti .tsingle{float:none!important;max-width:100%!important;box-sizing:border-box;text-align:center}.mw-parser-output .tmulti .tsingle .thumbcaption{text-align:left}.mw-parser-output .tmulti .trow>.thumbcaption{text-align:center}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .tmulti .multiimageinner img{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .tmulti .multiimageinner img{background-color:white}}</style><div class="thumb tmulti tright"><div class="thumbinner multiimageinner" style="width:404px;max-width:404px"><div class="trow"><div class="tsingle" style="width:402px;max-width:402px"><div class="thumbimage"><span typeof="mw:File"><a href="/wiki/File:Patricia_tree.png" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Patricia_tree.png/400px-Patricia_tree.png" decoding="async" width="400" height="139" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/c/cd/Patricia_tree.png 1.5x" data-file-width="587" data-file-height="204" /></a></span></div></div></div><div class="trow"><div class="tsingle" style="width:402px;max-width:402px"><div class="thumbimage"><span typeof="mw:File"><a href="/wiki/File:Patricia_tree_ASCII_to_binary.png" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Patricia_tree_ASCII_to_binary.png/400px-Patricia_tree_ASCII_to_binary.png" decoding="async" width="400" height="193" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Patricia_tree_ASCII_to_binary.png/600px-Patricia_tree_ASCII_to_binary.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Patricia_tree_ASCII_to_binary.png/800px-Patricia_tree_ASCII_to_binary.png 2x" data-file-width="819" data-file-height="395" /></a></span></div></div></div><div class="trow" style="display:flex"><div class="thumbcaption">Patricia tree representation of the string set <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r886049734"><span class="monospaced">{in, integer, interval, string, structure}</span>.</div></div></div></div> <p>Patricia trees are a particular implementation of the compressed binary trie that uses the <a href="/wiki/Binary_code" title="Binary code">binary encoding</a> of the string keys in its representation.<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-gonnet91_15-2" class="reference"><a href="#cite_note-gonnet91-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 140">: 140 </span></sup> Every node in a Patricia tree contains an index, known as a "skip number", that stores the node's branching index to avoid empty subtrees during traversal.<sup id="cite_ref-gonnet91_15-3" class="reference"><a href="#cite_note-gonnet91-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 140-141">: 140-141 </span></sup> A naive implementation of a trie consumes immense storage due to larger number of leaf-nodes caused by sparse distribution of keys; Patricia trees can be efficient for such cases.<sup id="cite_ref-gonnet91_15-4" class="reference"><a href="#cite_note-gonnet91-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 142">: 142 </span></sup><sup id="cite_ref-maxime09_24-0" class="reference"><a href="#cite_note-maxime09-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 3">: 3 </span></sup> </p><p>A representation of a Patricia tree is shown to the right. Each index value adjacent to the nodes represents the "skip number"—the index of the bit with which branching is to be decided.<sup id="cite_ref-maxime09_24-1" class="reference"><a href="#cite_note-maxime09-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 3">: 3 </span></sup> The skip number 1 at node 0 corresponds to the position 1 in the binary encoded ASCII where the leftmost bit differed in the key set <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>X</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle X}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}"></span>.<sup id="cite_ref-maxime09_24-2" class="reference"><a href="#cite_note-maxime09-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 3-4">: 3-4 </span></sup> The skip number is crucial for search, insertion, and deletion of nodes in the Patricia tree, and a <a href="/wiki/Bit_masking" class="mw-redirect" title="Bit masking">bit masking</a> operation is performed during every iteration.<sup id="cite_ref-gonnet91_15-5" class="reference"><a href="#cite_note-gonnet91-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 143">: 143 </span></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=13" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Trie data structures are commonly used in <a href="/wiki/Predictive_text" title="Predictive text">predictive text</a> or <a href="/wiki/Autocomplete" title="Autocomplete">autocomplete</a> dictionaries, and <a href="/wiki/Approximate_string_matching" title="Approximate string matching">approximate matching algorithms</a>.<sup id="cite_ref-aho75_11-1" class="reference"><a href="#cite_note-aho75-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> Tries enable faster searches, occupy less space, especially when the set contains large number of short strings, thus used in <a href="/wiki/Spell_checking" class="mw-redirect" title="Spell checking">spell checking</a>, hyphenation applications and <a href="/wiki/Longest_prefix_match" title="Longest prefix match">longest prefix match</a> algorithms.<sup id="cite_ref-Liang1983_8-4" class="reference"><a href="#cite_note-Liang1983-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-reema18_12-5" class="reference"><a href="#cite_note-reema18-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 358">: 358 </span></sup> However, if storing dictionary words is all that is required (i.e. there is no need to store metadata associated with each word), a minimal deterministic acyclic finite state automaton (DAFSA) or radix tree would use less storage space than a trie. This is because DAFSAs and radix trees can compress identical branches from the trie which correspond to the same suffixes (or parts) of different words being stored. String dictionaries are also utilized in <a href="/wiki/Natural_language_processing" title="Natural language processing">natural language processing</a>, such as finding <a href="/wiki/Lexicon" title="Lexicon">lexicon</a> of a <a href="/wiki/Text_corpus" title="Text corpus">text corpus</a>.<sup id="cite_ref-prieto16_25-0" class="reference"><a href="#cite_note-prieto16-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 73">: 73 </span></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Sorting">Sorting</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=14" title="Edit section: Sorting"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><a href="/wiki/Lexicographic_order" title="Lexicographic order">Lexicographic sorting</a> of a set of string keys can be implemented by building a trie for the given keys and traversing the tree in <a href="/wiki/Tree_traversal#Pre-order_implementation" title="Tree traversal">pre-order</a> fashion;<sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup> this is also a form of <a href="/wiki/Radix_sort" title="Radix sort">radix sort</a>.<sup id="cite_ref-27" class="reference"><a href="#cite_note-27"><span class="cite-bracket">[</span>27<span class="cite-bracket">]</span></a></sup> Tries are also fundamental data structures for <a href="/wiki/Burstsort" title="Burstsort">burstsort</a>, which is notable for being the fastest string sorting algorithm as of 2007,<sup id="cite_ref-cachestringsort_28-0" class="reference"><a href="#cite_note-cachestringsort-28"><span class="cite-bracket">[</span>28<span class="cite-bracket">]</span></a></sup> accomplished by its efficient use of CPU <a href="/wiki/Cache_(computing)" title="Cache (computing)">cache</a>.<sup id="cite_ref-stringradix_29-0" class="reference"><a href="#cite_note-stringradix-29"><span class="cite-bracket">[</span>29<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Full-text_search">Full-text search</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=15" title="Edit section: Full-text search"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A special kind of trie, called a <a href="/wiki/Suffix_tree" title="Suffix tree">suffix tree</a>, can be used to index all <a href="/wiki/Suffix" title="Suffix">suffixes</a> in a text to carry out fast full-text searches.<sup id="cite_ref-30" class="reference"><a href="#cite_note-30"><span class="cite-bracket">[</span>30<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Web_search_engines">Web search engines</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=16" title="Edit section: Web search engines"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A specialized kind of trie called a compressed trie, is used in <a href="/wiki/Web_search_engine" class="mw-redirect" title="Web search engine">web search engines</a> for storing the <a href="/wiki/Web_indexing" title="Web indexing">indexes</a> - a collection of all searchable words.<sup id="cite_ref-Xu12_31-0" class="reference"><a href="#cite_note-Xu12-31"><span class="cite-bracket">[</span>31<span class="cite-bracket">]</span></a></sup> Each terminal node is associated with a list of <a href="/wiki/URL" title="URL">URLs</a>—called occurrence list—to pages that match the keyword. The trie is stored in the main memory, whereas the occurrence is kept in an external storage, frequently in large <a href="/wiki/Computer_cluster" title="Computer cluster">clusters</a>, or the in-memory index points to documents stored in an external location.<sup id="cite_ref-32" class="reference"><a href="#cite_note-32"><span class="cite-bracket">[</span>32<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Bioinformatics">Bioinformatics</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=17" title="Edit section: Bioinformatics"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Tries are used in <a href="/wiki/Bioinformatics" title="Bioinformatics">Bioinformatics</a>, notably in <a href="/wiki/Sequence_alignment" title="Sequence alignment">sequence alignment</a> software applications such as <a href="/wiki/BLAST_(biotechnology)#Algorithm" title="BLAST (biotechnology)">BLAST</a>, which indexes all the different substring of length <i>k</i> (called <a href="/wiki/K-mer" title="K-mer">k-mers</a>) of a text by storing the positions of their occurrences in a compressed trie sequence databases.<sup id="cite_ref-prieto16_25-1" class="reference"><a href="#cite_note-prieto16-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 75">: 75 </span></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Internet_routing">Internet routing</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=18" title="Edit section: Internet routing"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Lule%C3%A5_algorithm" title="Luleå algorithm">Luleå algorithm</a></div> <p>Compressed variants of tries, such as databases for managing <a href="/wiki/Forwarding_information_base" title="Forwarding information base">Forwarding Information Base</a> (FIB), are used in storing <a href="/wiki/Subnetwork" class="mw-redirect" title="Subnetwork">IP address prefixes</a> within <a href="/wiki/Routing" title="Routing">routers</a> and <a href="/wiki/Network_bridge" title="Network bridge">bridges</a> for prefix-based lookup to resolve <a href="/wiki/Wildcard_mask" title="Wildcard mask">mask-based</a> operations in <a href="/wiki/IP_routing" title="IP routing">IP routing</a>.<sup id="cite_ref-prieto16_25-2" class="reference"><a href="#cite_note-prieto16-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup><sup class="reference nowrap"><span title="Page: 75">: 75 </span></sup> </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=19" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1184024115">.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}</style><div class="div-col" style="column-width: 22em;"> <ul><li><a href="/wiki/Suffix_tree" title="Suffix tree">Suffix tree</a></li> <li><a href="/wiki/Hash_trie" title="Hash trie">Hash trie</a></li> <li><a href="/wiki/Hash_array_mapped_trie" title="Hash array mapped trie">Hash array mapped trie</a></li> <li><a href="/wiki/Prefix_hash_tree" title="Prefix hash tree">Prefix hash tree</a></li> <li><a href="/wiki/Ctrie" title="Ctrie">Ctrie</a></li> <li><a href="/wiki/HAT-trie" title="HAT-trie">HAT-trie</a></li> <li><a href="/wiki/Aho%E2%80%93Corasick_algorithm" title="Aho–Corasick algorithm">Aho–Corasick algorithm</a></li></ul> </div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=20" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;"> <ol class="references"> <li id="cite_note-cvr14-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-cvr14_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-cvr14_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFMaabar2014" class="citation web cs1">Maabar, Maha (17 November 2014). <a rel="nofollow" class="external text" href="https://bioinformatics.cvr.ac.uk/trie-data-structure/">"Trie Data Structure"</a>. CVR, <a href="/wiki/University_of_Glasgow" title="University of Glasgow">University of Glasgow</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20210127130913/https://bioinformatics.cvr.ac.uk/trie-data-structure/">Archived</a> from the original on 27 January 2021<span class="reference-accessdate">. Retrieved <span class="nowrap">17 April</span> 2022</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Trie+Data+Structure&rft.pub=CVR%2C+University+of+Glasgow&rft.date=2014-11-17&rft.aulast=Maabar&rft.aufirst=Maha&rft_id=https%3A%2F%2Fbioinformatics.cvr.ac.uk%2Ftrie-data-structure%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-thue-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-thue_2-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFThue1912" class="citation journal cs1">Thue, Axel (1912). <a rel="nofollow" class="external text" href="https://archive.org/details/skrifterutgitavv121chri/page/n11/mode/2up">"Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen"</a>. <i>Skrifter Udgivne Af Videnskabs-Selskabet I Christiania</i>. <b>1912</b> (1): 1–67.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Skrifter+Udgivne+Af+Videnskabs-Selskabet+I+Christiania&rft.atitle=%C3%9Cber+die+gegenseitige+Lage+gleicher+Teile+gewisser+Zeichenreihen&rft.volume=1912&rft.issue=1&rft.pages=1-67&rft.date=1912&rft.aulast=Thue&rft.aufirst=Axel&rft_id=https%3A%2F%2Farchive.org%2Fdetails%2Fskrifterutgitavv121chri%2Fpage%2Fn11%2Fmode%2F2up&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span> Cited by Knuth.</span> </li> <li id="cite_note-KnuthVol3-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-KnuthVol3_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-KnuthVol3_3-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-KnuthVol3_3-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-KnuthVol3_3-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKnuth1997" class="citation book cs1"><a href="/wiki/Donald_Knuth" title="Donald Knuth">Knuth, Donald</a> (1997). "6.3: Digital Searching". <i><a href="/wiki/The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a> Volume 3: Sorting and Searching</i> (2nd ed.). Addison-Wesley. p. 492. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-201-89685-0" title="Special:BookSources/0-201-89685-0"><bdi>0-201-89685-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=6.3%3A+Digital+Searching&rft.btitle=The+Art+of+Computer+Programming+Volume+3%3A+Sorting+and+Searching&rft.pages=492&rft.edition=2nd&rft.pub=Addison-Wesley&rft.date=1997&rft.isbn=0-201-89685-0&rft.aulast=Knuth&rft.aufirst=Donald&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFde_la_Briandais1959" class="citation conference cs1">de la Briandais, René (1959). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20200211163605/https://pdfs.semanticscholar.org/3ce3/f4cc1c91d03850ed84ef96a08498e018d18f.pdf"><i>File searching using variable length keys</i></a> <span class="cs1-format">(PDF)</span>. Proc. Western J. Computer Conf. pp. 295–298. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1457838.1457895">10.1145/1457838.1457895</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10963780">10963780</a>. Archived from <a rel="nofollow" class="external text" href="https://pdfs.semanticscholar.org/3ce3/f4cc1c91d03850ed84ef96a08498e018d18f.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2020-02-11.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=File+searching+using+variable+length+keys&rft.pages=295-298&rft.date=1959&rft_id=info%3Adoi%2F10.1145%2F1457838.1457895&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A10963780%23id-name%3DS2CID&rft.aulast=de+la+Briandais&rft.aufirst=Ren%C3%A9&rft_id=https%3A%2F%2Fpdfs.semanticscholar.org%2F3ce3%2Ff4cc1c91d03850ed84ef96a08498e018d18f.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span> Cited by Brass and by Knuth.</span> </li> <li id="cite_note-brass-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-brass_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-brass_5-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-brass_5-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-brass_5-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrass2008" class="citation book cs1">Brass, Peter (8 September 2008). <a rel="nofollow" class="external text" href="https://www.cambridge.org/core/books/advanced-data-structures/D56E2269D7CEE969A3B8105AD5B9254C"><i>Advanced Data Structures</i></a>. <a href="/wiki/UK" class="mw-redirect" title="UK">UK</a>: <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9780511800191">10.1017/CBO9780511800191</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0521880374" title="Special:BookSources/978-0521880374"><bdi>978-0521880374</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Advanced+Data+Structures&rft.place=UK&rft.pub=Cambridge+University+Press&rft.date=2008-09-08&rft_id=info%3Adoi%2F10.1017%2FCBO9780511800191&rft.isbn=978-0521880374&rft.aulast=Brass&rft.aufirst=Peter&rft_id=https%3A%2F%2Fwww.cambridge.org%2Fcore%2Fbooks%2Fadvanced-data-structures%2FD56E2269D7CEE969A3B8105AD5B9254C&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-triememory-6"><span class="mw-cite-backlink">^ <a href="#cite_ref-triememory_6-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-triememory_6-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFEdward_Fredkin1960" class="citation journal cs1"><a href="/wiki/Edward_Fredkin" title="Edward Fredkin">Edward Fredkin</a> (1960). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F367390.367400">"Trie Memory"</a>. <i>Communications of the ACM</i>. <b>3</b> (9): 490–499. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F367390.367400">10.1145/367390.367400</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15384533">15384533</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Communications+of+the+ACM&rft.atitle=Trie+Memory&rft.volume=3&rft.issue=9&rft.pages=490-499&rft.date=1960&rft_id=info%3Adoi%2F10.1145%2F367390.367400&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A15384533%23id-name%3DS2CID&rft.au=Edward+Fredkin&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F367390.367400&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-DADS-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-DADS_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-DADS_7-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBlack2009" class="citation web cs1">Black, Paul E. (2009-11-16). <a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/trie.html">"trie"</a>. <i>Dictionary of Algorithms and Data Structures</i>. <a href="/wiki/National_Institute_of_Standards_and_Technology" title="National Institute of Standards and Technology">National Institute of Standards and Technology</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110429080033/http://xlinux.nist.gov/dads/HTML/trie.html">Archived</a> from the original on 2011-04-29.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Dictionary+of+Algorithms+and+Data+Structures&rft.atitle=trie&rft.date=2009-11-16&rft.aulast=Black&rft.aufirst=Paul+E.&rft_id=https%3A%2F%2Fxlinux.nist.gov%2Fdads%2FHTML%2Ftrie.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-Liang1983-8"><span class="mw-cite-backlink">^ <a href="#cite_ref-Liang1983_8-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Liang1983_8-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Liang1983_8-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-Liang1983_8-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-Liang1983_8-4"><sup><i><b>e</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFranklin_Mark_Liang1983" class="citation thesis cs1">Franklin Mark Liang (1983). <a rel="nofollow" class="external text" href="http://www.tug.org/docs/liang/liang-thesis.pdf"><i>Word Hy-phen-a-tion By Com-put-er</i></a> <span class="cs1-format">(PDF)</span> (Doctor of Philosophy thesis). Stanford University. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20051111105124/http://www.tug.org/docs/liang/liang-thesis.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2005-11-11<span class="reference-accessdate">. Retrieved <span class="nowrap">2010-03-28</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adissertation&rft.title=Word+Hy-phen-a-tion+By+Com-put-er&rft.degree=Doctor+of+Philosophy&rft.inst=Stanford+University&rft.date=1983&rft.au=Franklin+Mark+Liang&rft_id=http%3A%2F%2Fwww.tug.org%2Fdocs%2Fliang%2Fliang-thesis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://ds.cs.rutgers.edu/assignment-trie/">"Trie"</a>. School of Arts and Science, <a href="/wiki/Rutgers_University" title="Rutgers University">Rutgers University</a>. 2022. <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20220417170426/https://ds.cs.rutgers.edu/assignment-trie/">Archived</a> from the original on 17 April 2022<span class="reference-accessdate">. Retrieved <span class="nowrap">17 April</span> 2022</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Trie&rft.pub=School+of+Arts+and+Science%2C+Rutgers+University&rft.date=2022&rft_id=https%3A%2F%2Fds.cs.rutgers.edu%2Fassignment-trie%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFConnellyMorris1993" class="citation journal cs1">Connelly, Richard H.; Morris, F. Lockwood (1993). <a rel="nofollow" class="external text" href="https://surface.syr.edu/eecs_techreports/162/">"A generalization of the trie data structure"</a>. <i>Mathematical Structures in Computer Science</i>. <b>5</b> (3). <a href="/wiki/Syracuse_University" title="Syracuse University">Syracuse University</a>: 381–418. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FS0960129500000803">10.1017/S0960129500000803</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18747244">18747244</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematical+Structures+in+Computer+Science&rft.atitle=A+generalization+of+the+trie+data+structure&rft.volume=5&rft.issue=3&rft.pages=381-418&rft.date=1993&rft_id=info%3Adoi%2F10.1017%2FS0960129500000803&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A18747244%23id-name%3DS2CID&rft.aulast=Connelly&rft.aufirst=Richard+H.&rft.au=Morris%2C+F.+Lockwood&rft_id=https%3A%2F%2Fsurface.syr.edu%2Feecs_techreports%2F162%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-aho75-11"><span class="mw-cite-backlink">^ <a href="#cite_ref-aho75_11-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-aho75_11-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAhoCorasick1975" class="citation journal cs1">Aho, Alfred V.; Corasick, Margaret J. (Jun 1975). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F360825.360855">"Efficient String Matching: An Aid to Bibliographic Search"</a>. <i><a href="/wiki/Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a></i>. <b>18</b> (6): 333–340. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F360825.360855">10.1145/360825.360855</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207735784">207735784</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Communications+of+the+ACM&rft.atitle=Efficient+String+Matching%3A+An+Aid+to+Bibliographic+Search&rft.volume=18&rft.issue=6&rft.pages=333-340&rft.date=1975-06&rft_id=info%3Adoi%2F10.1145%2F360825.360855&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A207735784%23id-name%3DS2CID&rft.aulast=Aho&rft.aufirst=Alfred+V.&rft.au=Corasick%2C+Margaret+J.&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F360825.360855&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-reema18-12"><span class="mw-cite-backlink">^ <a href="#cite_ref-reema18_12-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-reema18_12-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-reema18_12-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-reema18_12-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-reema18_12-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-reema18_12-5"><sup><i><b>f</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFThareja2018" class="citation book cs1">Thareja, Reema (13 October 2018). "Hashing and Collision". <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://global.oup.com/academic/product/data-structures-using-c-9780198099307"><i>Data Structures Using C</i></a></span> (2 ed.). <a href="/wiki/Oxford_University_Press" title="Oxford University Press">Oxford University Press</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780198099307" title="Special:BookSources/9780198099307"><bdi>9780198099307</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Hashing+and+Collision&rft.btitle=Data+Structures+Using+C&rft.edition=2&rft.pub=Oxford+University+Press&rft.date=2018-10-13&rft.isbn=9780198099307&rft.aulast=Thareja&rft.aufirst=Reema&rft_id=https%3A%2F%2Fglobal.oup.com%2Facademic%2Fproduct%2Fdata-structures-using-c-9780198099307&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDaciuk2003" class="citation conference cs1">Daciuk, Jan (24 June 2003). <a rel="nofollow" class="external text" href="https://link.springer.com/chapter/10.1007/3-540-44977-9_26"><i>Comparison of Construction Algorithms for Minimal, Acyclic, Deterministic, Finite-State Automata from Sets of Strings</i></a>. International Conference on Implementation and Application of Automata. <a href="/wiki/Springer_Publishing" title="Springer Publishing">Springer Publishing</a>. pp. 255–261. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-44977-9_26">10.1007/3-540-44977-9_26</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-40391-3" title="Special:BookSources/978-3-540-40391-3"><bdi>978-3-540-40391-3</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=Comparison+of+Construction+Algorithms+for+Minimal%2C+Acyclic%2C+Deterministic%2C+Finite-State+Automata+from+Sets+of+Strings&rft.pages=255-261&rft.pub=Springer+Publishing&rft.date=2003-06-24&rft_id=info%3Adoi%2F10.1007%2F3-540-44977-9_26&rft.isbn=978-3-540-40391-3&rft.aulast=Daciuk&rft.aufirst=Jan&rft_id=https%3A%2F%2Flink.springer.com%2Fchapter%2F10.1007%2F3-540-44977-9_26&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-robert11-14"><span class="mw-cite-backlink">^ <a href="#cite_ref-robert11_14-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-robert11_14-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-robert11_14-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-robert11_14-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-robert11_14-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-robert11_14-5"><sup><i><b>f</b></i></sup></a> <a href="#cite_ref-robert11_14-6"><sup><i><b>g</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSedgewickWayne2011" class="citation book cs1"><a href="/wiki/Robert_Sedgewick_(computer_scientist)" title="Robert Sedgewick (computer scientist)">Sedgewick, Robert</a>; Wayne, Kevin (3 April 2011). <a rel="nofollow" class="external text" href="https://algs4.cs.princeton.edu/home/"><i>Algorithms</i></a> (4 ed.). <a href="/wiki/Addison-Wesley" title="Addison-Wesley">Addison-Wesley</a>, <a href="/wiki/Princeton_University" title="Princeton University">Princeton University</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0321573513" title="Special:BookSources/978-0321573513"><bdi>978-0321573513</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithms&rft.edition=4&rft.pub=Addison-Wesley%2C+Princeton+University&rft.date=2011-04-03&rft.isbn=978-0321573513&rft.aulast=Sedgewick&rft.aufirst=Robert&rft.au=Wayne%2C+Kevin&rft_id=https%3A%2F%2Falgs4.cs.princeton.edu%2Fhome%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-gonnet91-15"><span class="mw-cite-backlink">^ <a href="#cite_ref-gonnet91_15-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-gonnet91_15-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-gonnet91_15-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-gonnet91_15-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-gonnet91_15-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-gonnet91_15-5"><sup><i><b>f</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGonnetYates1991" class="citation book cs1">Gonnet, G. H.; Yates, R. Baeza (January 1991). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/book/10.5555/103324"><i>Handbook of algorithms and data structures: in Pascal and C</i></a> (2 ed.). <a href="/wiki/Boston" title="Boston">Boston</a>, <a href="/wiki/United_States" title="United States">United States</a>: <a href="/wiki/Addison-Wesley" title="Addison-Wesley">Addison-Wesley</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-201-41607-7" title="Special:BookSources/978-0-201-41607-7"><bdi>978-0-201-41607-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Handbook+of+algorithms+and+data+structures%3A+in+Pascal+and+C&rft.place=Boston%2C+United+States&rft.edition=2&rft.pub=Addison-Wesley&rft.date=1991-01&rft.isbn=978-0-201-41607-7&rft.aulast=Gonnet&rft.aufirst=G.+H.&rft.au=Yates%2C+R.+Baeza&rft_id=https%3A%2F%2Fdl.acm.org%2Fdoi%2Fbook%2F10.5555%2F103324&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-patil_12-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-patil_12_16-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPatil2012" class="citation book cs1">Patil, Varsha H. (10 May 2012). <a rel="nofollow" class="external text" href="https://global.oup.com/academic/product/data-structures-using-c-9780198066231"><i>Data Structures using C++</i></a>. <a href="/wiki/Oxford_University_Press" title="Oxford University Press">Oxford University Press</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780198066231" title="Special:BookSources/9780198066231"><bdi>9780198066231</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Data+Structures+using+C%2B%2B&rft.pub=Oxford+University+Press&rft.date=2012-05-10&rft.isbn=9780198066231&rft.aulast=Patil&rft.aufirst=Varsha+H.&rft_id=https%3A%2F%2Fglobal.oup.com%2Facademic%2Fproduct%2Fdata-structures-using-c-9780198066231&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFS._OrleyJ._Mathews" class="citation web cs1">S. Orley; J. Mathews. <a rel="nofollow" class="external text" href="http://mathcenter.oxford.emory.edu/site/cs170/ieee754/">"The IEEE 754 Format"</a>. Department of Mathematics and Computer Science, <a href="/wiki/Emory_University" title="Emory University">Emory University</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220328093853/http://mathcenter.oxford.emory.edu/site/cs170/ieee754/">Archived</a> from the original on 28 March 2022<span class="reference-accessdate">. Retrieved <span class="nowrap">17 April</span> 2022</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=The+IEEE+754+Format&rft.pub=Department+of+Mathematics+and+Computer+Science%2C+Emory+University&rft.au=S.+Orley&rft.au=J.+Mathews&rft_id=http%3A%2F%2Fmathcenter.oxford.emory.edu%2Fsite%2Fcs170%2Fieee754%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBellekens2014" class="citation book cs1">Bellekens, Xavier (2014). "A Highly-Efficient Memory-Compression Scheme for GPU-Accelerated Intrusion Detection Systems". <i>Proceedings of the 7th International Conference on Security of Information and Networks - SIN '14</i>. Glasgow, Scotland, UK: ACM. pp. 302:302–302:309. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1704.02272">1704.02272</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2659651.2659723">10.1145/2659651.2659723</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-3033-6" title="Special:BookSources/978-1-4503-3033-6"><bdi>978-1-4503-3033-6</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:12943246">12943246</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=A+Highly-Efficient+Memory-Compression+Scheme+for+GPU-Accelerated+Intrusion+Detection+Systems&rft.btitle=Proceedings+of+the+7th+International+Conference+on+Security+of+Information+and+Networks+-+SIN+%2714&rft.place=Glasgow%2C+Scotland%2C+UK&rft.pages=302%3A302-302%3A309&rft.pub=ACM&rft.date=2014&rft_id=info%3Aarxiv%2F1704.02272&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A12943246%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F2659651.2659723&rft.isbn=978-1-4503-3033-6&rft.aulast=Bellekens&rft.aufirst=Xavier&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-willar83-19"><span class="mw-cite-backlink">^ <a href="#cite_ref-willar83_19-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-willar83_19-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWillar1983" class="citation journal cs1">Willar, Dan E. (27 January 1983). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/abs/pii/0020019083900753">"Log-logarithmic worst-case range queries are possible in space O(n)"</a>. <i>Information Processing Letters</i>. <b>17</b> (2): 81–84. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2883%2990075-3">10.1016/0020-0190(83)90075-3</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+Processing+Letters&rft.atitle=Log-logarithmic+worst-case+range+queries+are+possible+in+space+O%28n%29&rft.volume=17&rft.issue=2&rft.pages=81-84&rft.date=1983-01-27&rft_id=info%3Adoi%2F10.1016%2F0020-0190%2883%2990075-3&rft.aulast=Willar&rft.aufirst=Dan+E.&rft_id=https%3A%2F%2Fwww.sciencedirect.com%2Fscience%2Farticle%2Fabs%2Fpii%2F0020019083900753&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSartaj_Sahni2004" class="citation web cs1">Sartaj Sahni (2004). <a rel="nofollow" class="external text" href="https://www.cise.ufl.edu/~sahni/dsaac/enrich/c16/tries.htm">"Data Structures, Algorithms, & Applications in C++: Tries"</a>. <a href="/wiki/University_of_Florida" title="University of Florida">University of Florida</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160703161316/http://www.cise.ufl.edu/~sahni/dsaac/enrich/c16/tries.htm">Archived</a> from the original on 3 July 2016<span class="reference-accessdate">. Retrieved <span class="nowrap">17 April</span> 2022</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Data+Structures%2C+Algorithms%2C+%26+Applications+in+C%2B%2B%3A+Tries&rft.pub=University+of+Florida&rft.date=2004&rft.au=Sartaj+Sahni&rft_id=https%3A%2F%2Fwww.cise.ufl.edu%2F~sahni%2Fdsaac%2Fenrich%2Fc16%2Ftries.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMehtaSahni2018" class="citation book cs1">Mehta, Dinesh P.; Sahni, Sartaj (7 March 2018). "Tries". <a rel="nofollow" class="external text" href="https://www.routledge.com/Handbook-of-Data-Structures-and-Applications/Mehta-Sahni/p/book/9780367572006"><i>Handbook of Data Structures and Applications</i></a> (2 ed.). <a href="/wiki/Chapman_%26_Hall" title="Chapman & Hall">Chapman & Hall</a>, <a href="/wiki/University_of_Florida" title="University of Florida">University of Florida</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1498701853" title="Special:BookSources/978-1498701853"><bdi>978-1498701853</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Tries&rft.btitle=Handbook+of+Data+Structures+and+Applications&rft.edition=2&rft.pub=Chapman+%26+Hall%2C+University+of+Florida&rft.date=2018-03-07&rft.isbn=978-1498701853&rft.aulast=Mehta&rft.aufirst=Dinesh+P.&rft.au=Sahni%2C+Sartaj&rft_id=https%3A%2F%2Fwww.routledge.com%2FHandbook-of-Data-Structures-and-Applications%2FMehta-Sahni%2Fp%2Fbook%2F9780367572006&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJan_DaciukStoyan_MihovBruce_W._WatsonRichard_E._Watson2000" class="citation journal cs1">Jan Daciuk; Stoyan Mihov; Bruce W. Watson; Richard E. Watson (1 March 2000). <a rel="nofollow" class="external text" href="https://direct.mit.edu/coli/article/26/1/3/1628/Incremental-Construction-of-Minimal-Acyclic-Finite">"Incremental Construction of Minimal Acyclic Finite-State Automata"</a>. <i><a href="/wiki/Computational_Linguistics_(journal)" title="Computational Linguistics (journal)">Computational Linguistics</a></i>. <b>26</b> (1). <a href="/wiki/MIT_Press" title="MIT Press">MIT Press</a>: 3–16. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0007009">cs/0007009</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2000cs........7009D">2000cs........7009D</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1162%2F089120100561601">10.1162/089120100561601</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Computational+Linguistics&rft.atitle=Incremental+Construction+of+Minimal+Acyclic+Finite-State+Automata&rft.volume=26&rft.issue=1&rft.pages=3-16&rft.date=2000-03-01&rft_id=info%3Aarxiv%2Fcs%2F0007009&rft_id=info%3Adoi%2F10.1162%2F089120100561601&rft_id=info%3Abibcode%2F2000cs........7009D&rft.au=Jan+Daciuk&rft.au=Stoyan+Mihov&rft.au=Bruce+W.+Watson&rft.au=Richard+E.+Watson&rft_id=https%3A%2F%2Fdirect.mit.edu%2Fcoli%2Farticle%2F26%2F1%2F3%2F1628%2FIncremental-Construction-of-Minimal-Acyclic-Finite&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/patriciatree.html">"Patricia tree"</a>. <a href="/wiki/National_Institute_of_Standards_and_Technology" title="National Institute of Standards and Technology">National Institute of Standards and Technology</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220214182428/https://xlinux.nist.gov/dads/HTML/patriciatree.html">Archived</a> from the original on 14 February 2022<span class="reference-accessdate">. Retrieved <span class="nowrap">17 April</span> 2022</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Patricia+tree&rft.pub=National+Institute+of+Standards+and+Technology&rft_id=https%3A%2F%2Fxlinux.nist.gov%2Fdads%2FHTML%2Fpatriciatree.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-maxime09-24"><span class="mw-cite-backlink">^ <a href="#cite_ref-maxime09_24-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-maxime09_24-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-maxime09_24-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCrochemoreLecroq2009" class="citation book cs1">Crochemore, Maxime; Lecroq, Thierry (2009). "Trie". <a rel="nofollow" class="external text" href="https://link.springer.com/referencework/10.1007/978-0-387-39940-9"><i>Encyclopedia of Database Systems</i></a>. <a href="/wiki/Boston" title="Boston">Boston</a>, <a href="/wiki/United_States" title="United States">United States</a>: <a href="/wiki/Springer_Publishing" title="Springer Publishing">Springer Publishing</a>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009eds..book.....L">2009eds..book.....L</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-0-387-39940-9">10.1007/978-0-387-39940-9</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-387-49616-0" title="Special:BookSources/978-0-387-49616-0"><bdi>978-0-387-49616-0</bdi></a> – via <a href="/wiki/HAL_(open_archive)" title="HAL (open archive)">HAL (open archive)</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Trie&rft.btitle=Encyclopedia+of+Database+Systems&rft.place=Boston%2C+United+States&rft.pub=Springer+Publishing&rft.date=2009&rft_id=info%3Adoi%2F10.1007%2F978-0-387-39940-9&rft_id=info%3Abibcode%2F2009eds..book.....L&rft.isbn=978-0-387-49616-0&rft.aulast=Crochemore&rft.aufirst=Maxime&rft.au=Lecroq%2C+Thierry&rft_id=https%3A%2F%2Flink.springer.com%2Freferencework%2F10.1007%2F978-0-387-39940-9&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-prieto16-25"><span class="mw-cite-backlink">^ <a href="#cite_ref-prieto16_25-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-prieto16_25-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-prieto16_25-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMartinez-PrietoBrisaboaCanovasClaude2016" class="citation journal cs1">Martinez-Prieto, Miguel A.; Brisaboa, Nieves; Canovas, Rodrigo; Claude, Francisco; Navarro, Gonzalo (March 2016). <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/abs/pii/S0306437915001672">"Practical compressed string dictionaries"</a>. <i><a href="/wiki/Information_Systems_(journal)" title="Information Systems (journal)">Information Systems</a></i>. <b>56</b>. <a href="/wiki/Elsevier" title="Elsevier">Elsevier</a>: 73–108. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.is.2015.08.008">10.1016/j.is.2015.08.008</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0306-4379">0306-4379</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+Systems&rft.atitle=Practical+compressed+string+dictionaries&rft.volume=56&rft.pages=73-108&rft.date=2016-03&rft_id=info%3Adoi%2F10.1016%2Fj.is.2015.08.008&rft.issn=0306-4379&rft.aulast=Martinez-Prieto&rft.aufirst=Miguel+A.&rft.au=Brisaboa%2C+Nieves&rft.au=Canovas%2C+Rodrigo&rft.au=Claude%2C+Francisco&rft.au=Navarro%2C+Gonzalo&rft_id=https%3A%2F%2Fwww.sciencedirect.com%2Fscience%2Farticle%2Fabs%2Fpii%2FS0306437915001672&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-26">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKärkkäinen" class="citation web cs1">Kärkkäinen, Juha. <a rel="nofollow" class="external text" href="https://www.cs.helsinki.fi/u/tpkarkka/opetus/12s/spa/lecture02.pdf">"Lecture 2"</a> <span class="cs1-format">(PDF)</span>. <a href="/wiki/University_of_Helsinki" title="University of Helsinki">University of Helsinki</a>. <q>The preorder of the nodes in a trie is the same as the lexicographical order of the strings they represent assuming the children of a node are ordered by the edge labels.</q></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Lecture+2&rft.pub=University+of+Helsinki&rft.aulast=K%C3%A4rkk%C3%A4inen&rft.aufirst=Juha&rft_id=https%3A%2F%2Fwww.cs.helsinki.fi%2Fu%2Ftpkarkka%2Fopetus%2F12s%2Fspa%2Flecture02.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-27"><span class="mw-cite-backlink"><b><a href="#cite_ref-27">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKallis2018" class="citation web cs1">Kallis, Rafael (2018). <a rel="nofollow" class="external text" href="https://www.ifi.uzh.ch/dam/jcr:27d15f69-2a44-40f9-8b41-6d11b5926c67/ReportKallisMScBasis.pdf">"The Adaptive Radix Tree (Report #14-708-887)"</a> <span class="cs1-format">(PDF)</span>. <i>University of Zurich: Department of Informatics, Research Publications</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=University+of+Zurich%3A+Department+of+Informatics%2C+Research+Publications&rft.atitle=The+Adaptive+Radix+Tree+%28Report+%2314-708-887%29&rft.date=2018&rft.aulast=Kallis&rft.aufirst=Rafael&rft_id=https%3A%2F%2Fwww.ifi.uzh.ch%2Fdam%2Fjcr%3A27d15f69-2a44-40f9-8b41-6d11b5926c67%2FReportKallisMScBasis.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-cachestringsort-28"><span class="mw-cite-backlink"><b><a href="#cite_ref-cachestringsort_28-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRanjan_Sinha_and_Justin_Zobel_and_David_Ring2006" class="citation journal cs1">Ranjan Sinha and Justin Zobel and David Ring (Feb 2006). <a rel="nofollow" class="external text" href="https://people.eng.unimelb.edu.au/jzobel/fulltext/acmjea06.pdf">"Cache-Efficient String Sorting Using Copying"</a> <span class="cs1-format">(PDF)</span>. <i>ACM Journal of Experimental Algorithmics</i>. <b>11</b>: 1–32. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1187436.1187439">10.1145/1187436.1187439</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3184411">3184411</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Journal+of+Experimental+Algorithmics&rft.atitle=Cache-Efficient+String+Sorting+Using+Copying&rft.volume=11&rft.pages=1-32&rft.date=2006-02&rft_id=info%3Adoi%2F10.1145%2F1187436.1187439&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A3184411%23id-name%3DS2CID&rft.au=Ranjan+Sinha+and+Justin+Zobel+and+David+Ring&rft_id=https%3A%2F%2Fpeople.eng.unimelb.edu.au%2Fjzobel%2Ffulltext%2Facmjea06.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-stringradix-29"><span class="mw-cite-backlink"><b><a href="#cite_ref-stringradix_29-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJ._Kärkkäinen_and_T._Rantala2008" class="citation book cs1">J. Kärkkäinen and T. Rantala (2008). "Engineering Radix Sort for Strings". In A. Amir and A. Turpin and A. Moffat (ed.). <i>String Processing and Information Retrieval, Proc. SPIRE</i>. Lecture Notes in Computer Science. Vol. 5280. Springer. pp. 3–14. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-89097-3_3">10.1007/978-3-540-89097-3_3</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-89096-6" title="Special:BookSources/978-3-540-89096-6"><bdi>978-3-540-89096-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Engineering+Radix+Sort+for+Strings&rft.btitle=String+Processing+and+Information+Retrieval%2C+Proc.+SPIRE&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=3-14&rft.pub=Springer&rft.date=2008&rft_id=info%3Adoi%2F10.1007%2F978-3-540-89097-3_3&rft.isbn=978-3-540-89096-6&rft.au=J.+K%C3%A4rkk%C3%A4inen+and+T.+Rantala&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-30"><span class="mw-cite-backlink"><b><a href="#cite_ref-30">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGiancarlo1992" class="citation journal cs1">Giancarlo, Raffaele (28 May 1992). <a rel="nofollow" class="external text" href="https://epubs.siam.org/doi/abs/10.1137/S0097539792231982">"A Generalization of the Suffix Tree to Square Matrices, with Applications"</a>. <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>. <b>24</b> (3). <a href="/wiki/Society_for_Industrial_and_Applied_Mathematics" title="Society for Industrial and Applied Mathematics">Society for Industrial and Applied Mathematics</a>: 520–562. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539792231982">10.1137/S0097539792231982</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=A+Generalization+of+the+Suffix+Tree+to+Square+Matrices%2C+with+Applications&rft.volume=24&rft.issue=3&rft.pages=520-562&rft.date=1992-05-28&rft_id=info%3Adoi%2F10.1137%2FS0097539792231982&rft.issn=0097-5397&rft.aulast=Giancarlo&rft.aufirst=Raffaele&rft_id=https%3A%2F%2Fepubs.siam.org%2Fdoi%2Fabs%2F10.1137%2FS0097539792231982&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-Xu12-31"><span class="mw-cite-backlink"><b><a href="#cite_ref-Xu12_31-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFYangXuShi2012" class="citation journal cs1">Yang, Lai; Xu, Lida; Shi, Zhongzhi (23 March 2012). "An enhanced dynamic hash TRIE algorithm for lexicon search". <i>Enterprise Information Systems</i>. <b>6</b> (4): 419–432. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2012EntIS...6..419Y">2012EntIS...6..419Y</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F17517575.2012.665483">10.1080/17517575.2012.665483</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:37884057">37884057</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Enterprise+Information+Systems&rft.atitle=An+enhanced+dynamic+hash+TRIE+algorithm+for+lexicon+search&rft.volume=6&rft.issue=4&rft.pages=419-432&rft.date=2012-03-23&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A37884057%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1080%2F17517575.2012.665483&rft_id=info%3Abibcode%2F2012EntIS...6..419Y&rft.aulast=Yang&rft.aufirst=Lai&rft.au=Xu%2C+Lida&rft.au=Shi%2C+Zhongzhi&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> <li id="cite_note-32"><span class="mw-cite-backlink"><b><a href="#cite_ref-32">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTransierSanders2010" class="citation journal cs1">Transier, Frederik; Sanders, Peter (December 2010). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/1877766.1877768">"Engineering basic algorithms of an in-memory text search engine"</a>. <i>ACM Transactions on Information Systems</i>. <b>29</b> (1). <a href="/wiki/Association_for_Computing_Machinery" title="Association for Computing Machinery">Association for Computing Machinery</a>: 1–37. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1877766.1877768">10.1145/1877766.1877768</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:932749">932749</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Transactions+on+Information+Systems&rft.atitle=Engineering+basic+algorithms+of+an+in-memory+text+search+engine&rft.volume=29&rft.issue=1&rft.pages=1-37&rft.date=2010-12&rft_id=info%3Adoi%2F10.1145%2F1877766.1877768&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A932749%23id-name%3DS2CID&rft.aulast=Transier&rft.aufirst=Frederik&rft.au=Sanders%2C+Peter&rft_id=https%3A%2F%2Fdl.acm.org%2Fdoi%2F10.1145%2F1877766.1877768&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATrie" class="Z3988"></span></span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trie&action=edit&section=21" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1235681985">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><style data-mw-deduplicate="TemplateStyles:r1237033735">@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}</style><div class="side-box side-box-right plainlinks sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png" decoding="async" width="30" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/45px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/59px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></span></span></div> <div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Trie" class="extiw" title="commons:Category:Trie">Trie</a></span>.</div></div> </div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1235681985"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1237033735"><div class="side-box side-box-right plainlinks sistersitebox"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1126788409"> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/40px-Wiktionary-logo-en-v2.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/60px-Wiktionary-logo-en-v2.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/99/Wiktionary-logo-en-v2.svg/80px-Wiktionary-logo-en-v2.svg.png 2x" data-file-width="512" data-file-height="512" /></span></span></div> <div class="side-box-text plainlist">Look up <i><b><a href="https://en.wiktionary.org/wiki/Special:Search/trie" class="extiw" title="wiktionary:Special:Search/trie">trie</a></b></i> in Wiktionary, the free dictionary.</div></div> </div> <ul><li><a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/trie.html">NIST's Dictionary of Algorithms and Data Structures: Trie</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Tree_data_structures" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:CS_trees" title="Template:CS trees"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:CS_trees" title="Template talk:CS trees"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:CS_trees" title="Special:EditPage/Template:CS trees"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Tree_data_structures" style="font-size:114%;margin:0 4em"><a href="/wiki/Tree_(abstract_data_type)" title="Tree (abstract data type)">Tree data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Search_tree" title="Search tree">Search trees</a><br />(<a href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">dynamic sets</a>/<a href="/wiki/Associative_array" title="Associative array">associative arrays</a>)</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/2%E2%80%933_tree" title="2–3 tree">2–3</a></li> <li><a href="/wiki/2%E2%80%933%E2%80%934_tree" title="2–3–4 tree">2–3–4</a></li> <li><a href="/wiki/AA_tree" title="AA tree">AA</a></li> <li><a href="/wiki/(a,b)-tree" class="mw-redirect" title="(a,b)-tree">(a,b)</a></li> <li><a href="/wiki/AVL_tree" title="AVL tree">AVL</a></li> <li><a href="/wiki/B-tree" title="B-tree">B</a></li> <li><a href="/wiki/B%2B_tree" title="B+ tree">B+</a></li> <li><a href="/wiki/B*-tree" class="mw-redirect" title="B*-tree">B*</a></li> <li><a href="/wiki/Bx-tree" title="Bx-tree">B<sup>x</sup></a></li> <li>(<a href="/wiki/Optimal_binary_search_tree" title="Optimal binary search tree">Optimal</a>) <a href="/wiki/Binary_search_tree" title="Binary search tree">Binary search</a></li> <li><a href="/wiki/Dancing_tree" title="Dancing tree">Dancing</a></li> <li><a href="/wiki/HTree" title="HTree">HTree</a></li> <li><a href="/wiki/Interval_tree" title="Interval tree">Interval</a></li> <li><a href="/wiki/Order_statistic_tree" title="Order statistic tree">Order statistic</a></li> <li><a href="/wiki/Palindrome_tree" title="Palindrome tree">Palindrome</a></li> <li>(<a href="/wiki/Left-leaning_red%E2%80%93black_tree" title="Left-leaning red–black tree">Left-leaning</a>) <a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black</a></li> <li><a href="/wiki/Scapegoat_tree" title="Scapegoat tree">Scapegoat</a></li> <li><a href="/wiki/Splay_tree" title="Splay tree">Splay</a></li> <li><a href="/wiki/T-tree" title="T-tree">T</a></li> <li><a href="/wiki/Treap" title="Treap">Treap</a></li> <li><a href="/wiki/UB-tree" title="UB-tree">UB</a></li> <li><a href="/wiki/Weight-balanced_tree" title="Weight-balanced tree">Weight-balanced</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heaps</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary</a></li> <li><a href="/wiki/Binomial_heap" title="Binomial heap">Binomial</a></li> <li><a href="/wiki/Brodal_queue" title="Brodal queue">Brodal</a></li> <li><a href="/wiki/D-ary_heap" title="D-ary heap"><i>d</i>-ary</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci</a></li> <li><a href="/wiki/Leftist_tree" title="Leftist tree">Leftist</a></li> <li><a href="/wiki/Pairing_heap" title="Pairing heap">Pairing</a></li> <li><a href="/wiki/Skew_binomial_heap" title="Skew binomial heap">Skew binomial</a></li> <li><a href="/wiki/Skew_heap" title="Skew heap">Skew</a></li> <li><a href="/wiki/Van_Emde_Boas_tree" title="Van Emde Boas tree">van Emde Boas</a></li> <li><a href="/wiki/Weak_heap" title="Weak heap">Weak</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a class="mw-selflink selflink">Tries</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Ctrie" title="Ctrie">Ctrie</a></li> <li><a href="/wiki/C-trie" title="C-trie">C-trie (compressed ADT)</a></li> <li><a href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash</a></li> <li><a href="/wiki/Radix_tree" title="Radix tree">Radix</a></li> <li><a href="/wiki/Suffix_tree" title="Suffix tree">Suffix</a></li> <li><a href="/wiki/Ternary_search_tree" title="Ternary search tree">Ternary search</a></li> <li><a href="/wiki/X-fast_trie" title="X-fast trie">X-fast</a></li> <li><a href="/wiki/Y-fast_trie" title="Y-fast trie">Y-fast</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Spatial_index" class="mw-redirect" title="Spatial index">Spatial</a> data partitioning trees</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Ball_tree" title="Ball tree">Ball</a></li> <li><a href="/wiki/BK-tree" title="BK-tree">BK</a></li> <li><a href="/wiki/BSP_tree" class="mw-redirect" title="BSP tree">BSP</a></li> <li><a href="/wiki/Cartesian_tree" title="Cartesian tree">Cartesian</a></li> <li><a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R</a></li> <li><a href="/wiki/K-d_tree" title="K-d tree"><i>k</i>-d</a> (<a href="/wiki/Implicit_k-d_tree" title="Implicit k-d tree">implicit <i>k</i>-d</a>)</li> <li><a href="/wiki/M-tree" title="M-tree">M</a></li> <li><a href="/wiki/Metric_tree" title="Metric tree">Metric</a></li> <li><a href="/wiki/MVP_tree" class="mw-redirect" title="MVP tree">MVP</a></li> <li><a href="/wiki/Octree" title="Octree">Octree</a></li> <li><a href="/wiki/PH-tree" title="PH-tree">PH</a></li> <li><a href="/wiki/Priority_R-tree" title="Priority R-tree">Priority R</a></li> <li><a href="/wiki/Quadtree" title="Quadtree">Quad</a></li> <li><a href="/wiki/R-tree" title="R-tree">R</a></li> <li><a href="/wiki/R%2B_tree" title="R+ tree">R+</a></li> <li><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R*</a></li> <li><a href="/wiki/Segment_tree" title="Segment tree">Segment</a></li> <li><a href="/wiki/Vantage-point_tree" title="Vantage-point tree">VP</a></li> <li><a href="/wiki/X-tree" title="X-tree">X</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other trees</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cover_tree" title="Cover tree">Cover</a></li> <li><a href="/wiki/Exponential_tree" title="Exponential tree">Exponential</a></li> <li><a href="/wiki/Fenwick_tree" title="Fenwick tree">Fenwick</a></li> <li><a href="/wiki/Finger_tree" title="Finger tree">Finger</a></li> <li><a href="/wiki/Fractal_tree_index" title="Fractal tree index">Fractal tree index</a></li> <li><a href="/wiki/Fusion_tree" title="Fusion tree">Fusion</a></li> <li><a href="/wiki/Hash_calendar" title="Hash calendar">Hash calendar</a></li> <li><a href="/wiki/IDistance" title="IDistance">iDistance</a></li> <li><a href="/wiki/K-ary_tree" class="mw-redirect" title="K-ary tree">K-ary</a></li> <li><a href="/wiki/Left-child_right-sibling_binary_tree" title="Left-child right-sibling binary tree">Left-child right-sibling</a></li> <li><a href="/wiki/Link/cut_tree" title="Link/cut tree">Link/cut</a></li> <li><a href="/wiki/Log-structured_merge-tree" title="Log-structured merge-tree">Log-structured merge</a></li> <li><a href="/wiki/Merkle_tree" title="Merkle tree">Merkle</a></li> <li><a href="/wiki/PQ_tree" title="PQ tree">PQ</a></li> <li><a href="/wiki/Range_tree" title="Range tree">Range</a></li> <li><a href="/wiki/SPQR_tree" title="SPQR tree">SPQR</a></li> <li><a href="/wiki/Top_tree" title="Top tree">Top</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Data_structures" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Data_structures" title="Template:Data structures"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Data_structures" title="Template talk:Data structures"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Data_structures" title="Special:EditPage/Template:Data structures"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Data_structures" style="font-size:114%;margin:0 4em"><a href="/wiki/Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li> <li><a href="/wiki/Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Associative_array" title="Associative array">Associative array</a> <ul><li><a href="/wiki/Multimap" title="Multimap">Multimap</a></li> <li><a href="/wiki/Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li> <li><a href="/wiki/List_(abstract_data_type)" title="List (abstract data type)">List</a></li> <li><a href="/wiki/Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li> <li><a href="/wiki/Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a> <ul><li><a href="/wiki/Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li> <li><a href="/wiki/Priority_queue" title="Priority queue">Priority queue</a> <ul><li><a href="/wiki/Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li> <li><a href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">Set</a> <ul><li><a href="/wiki/Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li> <li><a href="/wiki/Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit_array" title="Bit array">Bit array</a></li> <li><a href="/wiki/Circular_buffer" title="Circular buffer">Circular buffer</a></li> <li><a href="/wiki/Dynamic_array" title="Dynamic array">Dynamic array</a></li> <li><a href="/wiki/Hash_table" title="Hash table">Hash table</a></li> <li><a href="/wiki/Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li> <li><a href="/wiki/Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Association_list" title="Association list">Association list</a></li> <li><a href="/wiki/Linked_list" title="Linked list">Linked list</a></li> <li><a href="/wiki/Skip_list" title="Skip list">Skip list</a></li> <li><a href="/wiki/Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li> <li><a href="/wiki/XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/B-tree" title="B-tree">B-tree</a></li> <li><a href="/wiki/Binary_search_tree" title="Binary search tree">Binary search tree</a> <ul><li><a href="/wiki/AA_tree" title="AA tree">AA tree</a></li> <li><a href="/wiki/AVL_tree" title="AVL tree">AVL tree</a></li> <li><a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li> <li><a href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li> <li><a href="/wiki/Splay_tree" title="Splay tree">Splay tree</a></li></ul></li> <li><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heap</a> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary heap</a></li> <li><a href="/wiki/Binomial_heap" title="Binomial heap">Binomial heap</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li> <li><a href="/wiki/R-tree" title="R-tree">R-tree</a> <ul><li><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R* tree</a></li> <li><a href="/wiki/R%2B_tree" title="R+ tree">R+ tree</a></li> <li><a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li> <li><a class="mw-selflink selflink">Trie</a> <ul><li><a href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash tree</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li> <li><a href="/wiki/Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li> <li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><a href="/wiki/List_of_data_structures" title="List of data structures">List of data structures</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Strings" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Strings" title="Template:Strings"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Strings" title="Template talk:Strings"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Strings" title="Special:EditPage/Template:Strings"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Strings" style="font-size:114%;margin:0 4em"><a href="/wiki/String_(computer_science)" title="String (computer science)">Strings</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/String_metric" title="String metric">String metric</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Approximate_string_matching" title="Approximate string matching">Approximate string matching</a></li> <li><a href="/wiki/Bitap_algorithm" title="Bitap algorithm">Bitap algorithm</a></li> <li><a href="/wiki/Damerau%E2%80%93Levenshtein_distance" title="Damerau–Levenshtein distance">Damerau–Levenshtein distance</a></li> <li><a href="/wiki/Edit_distance" title="Edit distance">Edit distance</a></li> <li><a href="/wiki/Gestalt_pattern_matching" title="Gestalt pattern matching">Gestalt pattern matching</a></li> <li><a href="/wiki/Hamming_distance" title="Hamming distance">Hamming distance</a></li> <li><a href="/wiki/Jaro%E2%80%93Winkler_distance" title="Jaro–Winkler distance">Jaro–Winkler distance</a></li> <li><a href="/wiki/Lee_distance" title="Lee distance">Lee distance</a></li> <li><a href="/wiki/Levenshtein_automaton" title="Levenshtein automaton">Levenshtein automaton</a></li> <li><a href="/wiki/Levenshtein_distance" title="Levenshtein distance">Levenshtein distance</a></li> <li><a href="/wiki/Wagner%E2%80%93Fischer_algorithm" title="Wagner–Fischer algorithm">Wagner–Fischer algorithm </a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/String-searching_algorithm" title="String-searching algorithm">String-searching algorithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Apostolico%E2%80%93Giancarlo_algorithm" title="Apostolico–Giancarlo algorithm">Apostolico–Giancarlo algorithm</a></li> <li><a href="/wiki/Boyer%E2%80%93Moore_string-search_algorithm" title="Boyer–Moore string-search algorithm">Boyer–Moore string-search algorithm</a></li> <li><a href="/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm" title="Boyer–Moore–Horspool algorithm">Boyer–Moore–Horspool algorithm</a></li> <li><a href="/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" title="Knuth–Morris–Pratt algorithm">Knuth–Morris–Pratt algorithm</a></li> <li><a href="/wiki/Rabin%E2%80%93Karp_algorithm" title="Rabin–Karp algorithm">Rabin–Karp algorithm</a></li> <li><a href="/wiki/Raita_algorithm" title="Raita algorithm">Raita algorithm</a></li> <li><a href="/wiki/Trigram_search" title="Trigram search">Trigram search</a></li> <li><a href="/wiki/Two-way_string-matching_algorithm" title="Two-way string-matching algorithm">Two-way string-matching algorithm</a></li> <li><a href="/wiki/Zhu%E2%80%93Takaoka_string_matching_algorithm" title="Zhu–Takaoka string matching algorithm">Zhu–Takaoka string matching algorithm</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Multiple string searching</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Aho%E2%80%93Corasick_algorithm" title="Aho–Corasick algorithm">Aho–Corasick</a></li> <li><a href="/wiki/Commentz-Walter_algorithm" title="Commentz-Walter algorithm">Commentz-Walter algorithm</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Regular_expression" title="Regular expression">Regular expression</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Comparison_of_regular-expression_engines" class="mw-redirect" title="Comparison of regular-expression engines">Comparison of regular-expression engines</a></li> <li><a href="/wiki/Regular_grammar" title="Regular grammar">Regular grammar</a></li> <li><a href="/wiki/Thompson%27s_construction" title="Thompson's construction">Thompson's construction</a></li> <li><a href="/wiki/Nondeterministic_finite_automaton" title="Nondeterministic finite automaton">Nondeterministic finite automaton</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Sequence_alignment" title="Sequence alignment">Sequence alignment</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/BLAST_(biotechnology)" title="BLAST (biotechnology)">BLAST</a></li> <li><a href="/wiki/Hirschberg%27s_algorithm" title="Hirschberg's algorithm">Hirschberg's algorithm</a></li> <li><a href="/wiki/Needleman%E2%80%93Wunsch_algorithm" title="Needleman–Wunsch algorithm">Needleman–Wunsch algorithm</a></li> <li><a href="/wiki/Smith%E2%80%93Waterman_algorithm" title="Smith–Waterman algorithm">Smith–Waterman algorithm</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Data_structure" title="Data structure">Data structure</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">DAFSA</a></li> <li><a href="/wiki/Suffix_array" title="Suffix array">Suffix array</a></li> <li><a href="/wiki/Suffix_automaton" title="Suffix automaton">Suffix automaton</a></li> <li><a href="/wiki/Suffix_tree" title="Suffix tree">Suffix tree</a></li> <li><a href="/wiki/Generalized_suffix_tree" title="Generalized suffix tree">Generalized suffix tree</a></li> <li><a href="/wiki/Rope_(data_structure)" title="Rope (data structure)">Rope</a></li> <li><a href="/wiki/Ternary_search_tree" title="Ternary search tree">Ternary search tree</a></li> <li><a class="mw-selflink selflink">Trie</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Parsing" title="Parsing">Parsing</a></li> <li><a href="/wiki/Pattern_matching" title="Pattern matching">Pattern matching</a></li> <li><a href="/wiki/Compressed_pattern_matching" title="Compressed pattern matching">Compressed pattern matching</a></li> <li><a href="/wiki/Longest_common_subsequence" title="Longest common subsequence">Longest common subsequence</a></li> <li><a href="/wiki/Longest_common_substring" title="Longest common substring">Longest common substring</a></li> <li><a href="/wiki/Sequential_pattern_mining" title="Sequential pattern mining">Sequential pattern mining</a></li> <li><a href="/wiki/Category:String_sorting_algorithms" title="Category:String sorting algorithms">Sorting</a></li> <li><a href="/wiki/Semi-Thue_system" title="Semi-Thue system">String rewriting systems</a></li> <li><a href="/wiki/String_operations" title="String operations">String operations</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Trie&oldid=1250000773">https://en.wikipedia.org/w/index.php?title=Trie&oldid=1250000773</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Trees_(data_structures)" title="Category:Trees (data structures)">Trees (data structures)</a></li><li><a href="/wiki/Category:Finite_automata" title="Category:Finite automata">Finite automata</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Good_articles" title="Category:Good articles">Good articles</a></li><li><a href="/wiki/Category:Commons_category_link_from_Wikidata" title="Category:Commons category link from Wikidata">Commons category link from Wikidata</a></li><li><a href="/wiki/Category:Articles_with_example_Python_(programming_language)_code" title="Category:Articles with example Python (programming language) code">Articles with example Python (programming language) code</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 7 October 2024, at 23:13<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Trie&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-5857dfdcd6-b59kd","wgBackendResponseTime":143,"wgPageParseReport":{"limitreport":{"cputime":"1.014","walltime":"1.231","ppvisitednodes":{"value":15708,"limit":1000000},"postexpandincludesize":{"value":148105,"limit":2097152},"templateargumentsize":{"value":5113,"limit":2097152},"expansiondepth":{"value":15,"limit":100},"expensivefunctioncount":{"value":7,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":164900,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 1002.425 1 -total"," 26.99% 270.592 1 Template:Reflist"," 20.38% 204.304 24 Template:R"," 19.57% 196.148 34 Template:R/superscript"," 19.37% 194.148 24 Template:R/ref"," 10.92% 109.449 8 Template:Cite_web"," 9.29% 93.114 1 Template:Short_description"," 8.91% 89.331 102 Template:R/where"," 7.64% 76.538 10 Template:Rp"," 6.96% 69.767 3 Template:Navbox"]},"scribunto":{"limitreport-timeusage":{"value":"0.487","limit":"10.000"},"limitreport-memusage":{"value":7559745,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.canary-757b8f897d-vxcwp","timestamp":"20241203065222","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Trie","url":"https:\/\/en.wikipedia.org\/wiki\/Trie","sameAs":"http:\/\/www.wikidata.org\/entity\/Q387015","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q387015","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-12-10T01:35:44Z","dateModified":"2024-10-07T23:13:47Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/b\/be\/Trie_example.svg","headline":"ordered tree data structure that organizes nodes by common key prefixes"}</script> </body> </html>