CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-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-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Treap - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-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-sticky-header-enabled 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":"1cbe2793-3b7a-440f-a2d9-e5b2b5283e82","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Treap","wgTitle":"Treap","wgCurRevisionId":1284025014,"wgRevisionId":1284025014,"wgArticleId":249855,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1 maint: DOI inactive as of November 2024","All articles with dead external links","Articles with dead external links from March 2018","Articles with permanently dead external links","CS1 errors: missing periodical","Articles with short description","Short description is different from Wikidata","All articles lacking reliable references","Articles lacking reliable references from December 2021","Commons category link from Wikidata","Heaps (data structures)","Binary trees","Probabilistic data structures","Search trees"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Treap","wgRelevantArticleId":249855,"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":20000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1757700","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":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","ext.pygments":"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"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","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.quicksurveys.init","ext.growthExperiments.SuggestedEditSession"];</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.pygments%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%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.23"> <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/e/e4/Treap.svg/1200px-Treap.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="978"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/e/e4/Treap.svg/800px-Treap.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="652"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/e/e4/Treap.svg/640px-Treap.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="521"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Treap - 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/Treap"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Treap&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/Treap"> <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="auth.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-Treap rootpage-Treap 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" title="Main menu" > <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><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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=Treap" 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=Treap" 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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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=Treap" 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=Treap" 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-Description" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Description"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Description</span> </div> </a> <ul id="toc-Description-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">2</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-Basic_operations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Basic_operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Basic operations</span> </div> </a> <ul id="toc-Basic_operations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Building_a_treap" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Building_a_treap"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Building a treap</span> </div> </a> <ul id="toc-Building_a_treap-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bulk_operations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bulk_operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Bulk operations</span> </div> </a> <ul id="toc-Bulk_operations-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Randomized_binary_search_tree" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Randomized_binary_search_tree"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Randomized binary search tree</span> </div> </a> <button aria-controls="toc-Randomized_binary_search_tree-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 Randomized binary search tree subsection</span> </button> <ul id="toc-Randomized_binary_search_tree-sublist" class="vector-toc-list"> <li id="toc-Comparison" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Comparison"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Comparison</span> </div> </a> <ul id="toc-Comparison-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Implicit_treap" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Implicit_treap"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Implicit treap</span> </div> </a> <button aria-controls="toc-Implicit_treap-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 Implicit treap subsection</span> </button> <ul id="toc-Implicit_treap-sublist" class="vector-toc-list"> <li id="toc-Operations_2" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Operations_2"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Operations</span> </div> </a> <ul id="toc-Operations_2-sublist" class="vector-toc-list"> <li id="toc-Insert_element" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Insert_element"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.1</span> <span>Insert element</span> </div> </a> <ul id="toc-Insert_element-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Delete_element" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Delete_element"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.2</span> <span>Delete element</span> </div> </a> <ul id="toc-Delete_element-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Find_sum,_minimum_or_maximum_in_a_given_range" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Find_sum,_minimum_or_maximum_in_a_given_range"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.3</span> <span>Find sum, minimum or maximum in a given range</span> </div> </a> <ul id="toc-Find_sum,_minimum_or_maximum_in_a_given_range-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Addition/painting_in_a_given_range" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Addition/painting_in_a_given_range"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.4</span> <span>Addition/painting in a given range</span> </div> </a> <ul id="toc-Addition/painting_in_a_given_range-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Reverse_in_a_given_range" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Reverse_in_a_given_range"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1.5</span> <span>Reverse in a given range</span> </div> </a> <ul id="toc-Reverse_in_a_given_range-sublist" class="vector-toc-list"> </ul> </li> </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">5</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">6</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">7</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" title="Table of Contents" > <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">Treap</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 13 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-13" 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">13 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Treap" title="Treap – German" lang="de" hreflang="de" data-title="Treap" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Treap" title="Treap – Spanish" lang="es" hreflang="es" data-title="Treap" 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%AA%D8%B1%DB%8C%D9%BE" 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/Treap" title="Treap – French" lang="fr" hreflang="fr" data-title="Treap" 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-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Treap" title="Treap – Italian" lang="it" hreflang="it" data-title="Treap" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/Treap" title="Treap – Japanese" lang="ja" hreflang="ja" data-title="Treap" 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/Drzewiec_(informatyka)" title="Drzewiec (informatyka) – Polish" lang="pl" hreflang="pl" data-title="Drzewiec (informatyka)" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%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-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Dekartovo_drvo" title="Dekartovo drvo – Serbian" lang="sr" hreflang="sr" data-title="Dekartovo drvo" 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%B5%E0%B8%9E" 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-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/Treap" title="Treap – Turkish" lang="tr" hreflang="tr" data-title="Treap" data-language-autonym="Türkçe" data-language-local-name="Turkish" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/Treap" title="Treap – Vietnamese" lang="vi" hreflang="vi" data-title="Treap" 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/%E6%A0%91%E5%A0%86" title="树堆 – Chinese" lang="zh" hreflang="zh" data-title="树堆" 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/Q1757700#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/Treap" 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:Treap" 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/Treap"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Treap&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=Treap&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/Treap"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Treap&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=Treap&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/Treap" 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/Treap" 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="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Treap&oldid=1284025014" 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=Treap&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=Treap&id=1284025014&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%2FTreap"><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%2FTreap"><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=Treap&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=Treap&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:Treap" 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/Q1757700" 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> <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">Random search tree data structure</div> <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">Treap</th></tr><tr><td colspan="2" class="infobox-image"><span class="mw-default-size" typeof="mw:File/Frameless"><a href="/wiki/File:Treap.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/e/e4/Treap.svg/250px-Treap.svg.png" decoding="async" width="220" height="179" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/e4/Treap.svg/330px-Treap.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/e4/Treap.svg/440px-Treap.svg.png 2x" data-file-width="286" data-file-height="233" /></a></span></td></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">Randomized <a href="/wiki/Binary_search_tree" title="Binary search tree">binary search tree</a></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"> <i>O</i>(log <i>n</i>)</td><td class="infobox-data infobox-data-b"> <i>O</i>(<i>n</i>)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Insert</th><td class="infobox-data infobox-data-a"> <i>O</i>(log <i>n</i>)</td><td class="infobox-data infobox-data-b"> <i>O</i>(<i>n</i>)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Delete</th><td class="infobox-data infobox-data-a"> <i>O</i>(log <i>n</i>)</td><td class="infobox-data infobox-data-b"> <i>O</i>(<i>n</i>)</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"> <i>O</i>(<i>n</i>)</td><td class="infobox-data infobox-data-b"> <i>O</i>(<i>n</i>)</td></tr></tbody></table></td></tr></tbody></table> <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:r1246091330">.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}</style><table class="sidebar nomobile nowraplinks"><tbody><tr><td class="sidebar-pretitle">Part of <a href="/wiki/Category:Probabilistic_data_structures" title="Category:Probabilistic data structures">a series</a> on</td></tr><tr><th class="sidebar-title-with-pretitle" style="background:#ccccff;"><a href="/wiki/Randomized_algorithm" title="Randomized algorithm">Probabilistic</a><br /><a href="/wiki/Data_structure" title="Data structure">data structures</a></th></tr><tr><td class="sidebar-content hlist"> <ul><li><a href="/wiki/Bloom_filter" title="Bloom filter">Bloom filter</a></li> <li><a href="/wiki/Count_sketch" title="Count sketch">Count sketch</a></li> <li><a href="/wiki/Count%E2%80%93min_sketch" title="Count–min sketch">Count–min sketch</a></li> <li><a href="/wiki/Quotient_filter" title="Quotient filter">Quotient filter</a></li> <li><a href="/wiki/Skip_list" title="Skip list">Skip list</a></li></ul></td> </tr><tr><th class="sidebar-heading" style="background:#ddddff;"> <a href="/wiki/Random_tree" title="Random tree">Random trees</a></th></tr><tr><td class="sidebar-content hlist"> <ul><li><a href="/wiki/Random_binary_tree" title="Random binary tree">Random binary tree</a></li> <li><a class="mw-selflink selflink">Treap</a></li> <li><a href="/wiki/Rapidly_exploring_random_tree" title="Rapidly exploring random tree">Rapidly exploring random tree</a></li></ul></td> </tr><tr><th class="sidebar-heading" style="background:#ddddff;"> Related</th></tr><tr><td class="sidebar-content hlist"> <ul><li><a href="/wiki/Randomized_algorithm" title="Randomized algorithm">Randomized algorithm</a></li> <li><a href="/wiki/HyperLogLog" title="HyperLogLog">HyperLogLog</a></li></ul></td> </tr><tr><td class="sidebar-navbar"><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:Probabilistic" title="Template:Probabilistic"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Probabilistic" title="Template talk:Probabilistic"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Probabilistic" title="Special:EditPage/Template:Probabilistic"><abbr title="Edit this template">e</abbr></a></li></ul></div></td></tr></tbody></table> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, the <b>treap</b> and the <b>randomized binary search tree</b> are two closely related forms of binary search tree <a href="/wiki/Data_structure" title="Data structure">data structures</a> that maintain a dynamic set of ordered keys and allow <a href="/wiki/Binary_search" title="Binary search">binary searches</a> among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, <a href="/wiki/With_high_probability" title="With high probability">with high probability</a> its height is proportional to the <a href="/wiki/Logarithm" title="Logarithm">logarithm</a> of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Description">Description</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=1" title="Edit section: Description"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size mw-halign-left" typeof="mw:File/Thumb"><a href="/wiki/File:TreapAlphaKey.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4b/TreapAlphaKey.svg/220px-TreapAlphaKey.svg.png" decoding="async" width="220" height="270" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4b/TreapAlphaKey.svg/330px-TreapAlphaKey.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4b/TreapAlphaKey.svg/440px-TreapAlphaKey.svg.png 2x" data-file-width="199" data-file-height="244" /></a><figcaption>A treap with alphabetic key and numeric max heap order</figcaption></figure> <p>The treap was first described by <a href="/wiki/Raimund_Seidel" title="Raimund Seidel">Raimund Seidel</a> and <a href="/wiki/Cecilia_R._Aragon" title="Cecilia R. Aragon">Cecilia R. Aragon</a> in 1989;<sup id="cite_ref-paper89_1-0" class="reference"><a href="#cite_note-paper89-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-paper96_2-0" class="reference"><a href="#cite_note-paper96-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> its name is a <a href="/wiki/Portmanteau_word" class="mw-redirect" title="Portmanteau word">portmanteau</a> of <a href="/wiki/Tree_data_structure" class="mw-redirect" title="Tree data structure">tree</a> and <a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">heap</a>. It is a <a href="/wiki/Cartesian_tree" title="Cartesian tree">Cartesian tree</a> in which each key is given a (randomly chosen) numeric priority. As with any binary search tree, the <a href="/wiki/Inorder_traversal" class="mw-redirect" title="Inorder traversal">inorder traversal</a> order of the nodes is the same as the sorted order of the keys. The structure of the tree is determined by the requirement that it be heap-ordered: that is, the priority number for any non-leaf node must be greater than or equal to the priority of its children. Thus, as with Cartesian trees more generally, the root node is the maximum-priority node, and its left and right subtrees are formed in the same manner from the subsequences of the sorted order to the left and right of that node. </p><p>An equivalent way of describing the treap is that it could be formed by inserting the nodes highest priority-first into a binary search tree without doing any rebalancing. Therefore, if the priorities are independent random numbers (from a distribution over a large enough space of possible priorities to ensure that two nodes are very unlikely to have the same priority) then the shape of a treap has the same probability distribution as the shape of a <a href="/wiki/Random_binary_search_tree" class="mw-redirect" title="Random binary search tree">random binary search tree</a>, a search tree formed by inserting the nodes without rebalancing in a randomly chosen insertion order. Because random binary search trees are known to have logarithmic height with high probability, the same is true for treaps. This mirrors the <a href="/wiki/Quicksort#Using_a_binary_search_tree" title="Quicksort">binary search tree argument</a> that <a href="/wiki/Quicksort" title="Quicksort">quicksort</a> runs in expected <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\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" /></span> time. If binary search trees are solutions to the <a href="/wiki/Dynamic_problem_(algorithms)" title="Dynamic problem (algorithms)">dynamic problem</a> version of sorting, then Treaps correspond specifically to dynamic quicksort where priorities guide pivot choices. </p><p>Aragon and Seidel also suggest assigning higher priorities to frequently accessed nodes, for instance by a process that, on each access, chooses a random number and replaces the priority of the node with that number if it is higher than the previous priority. This modification would cause the tree to lose its random shape; instead, frequently accessed nodes would be more likely to be near the root of the tree, causing searches for them to be faster. </p><p>Naor and Nissim<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> describe an application in maintaining <a href="/wiki/Public_key_certificate" title="Public key certificate">authorization certificates</a> in <a href="/wiki/Public-key_cryptography" title="Public-key cryptography">public-key cryptosystems</a>. </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=Treap&action=edit&section=2" title="Edit section: Operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Basic_operations">Basic operations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=3" title="Edit section: Basic operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Treaps support the following basic operations: </p> <ul><li>To search for a given key value, apply a standard <a href="/wiki/Binary_search_algorithm" class="mw-redirect" title="Binary search algorithm">binary search algorithm</a> in a binary search tree, ignoring the priorities.</li> <li>To insert a new key <i>x</i> into the treap, generate a random priority <i>y</i> for <i>x</i>. Binary search for <i>x</i> in the tree, and create a new node at the leaf position where the binary search determines a node for <i>x</i> should exist. Then, as long as <i>x</i> is not the root of the tree and has a larger priority number than its parent <i>z</i>, perform a <a href="/wiki/Tree_rotation" title="Tree rotation">tree rotation</a> that reverses the parent-child relation between <i>x</i> and <i>z</i>.</li> <li>To delete a node <i>x</i> from the treap, if <i>x</i> is a leaf of the tree, simply remove it. If <i>x</i> has a single child <i>z</i>, remove <i>x</i> from the tree and make <i>z</i> be the child of the parent of <i>x</i> (or make <i>z</i> the root of the tree if <i>x</i> had no parent). Finally, if <i>x</i> has two children, swap its position in the tree with the position of its immediate successor <i>z</i> in the sorted order, resulting in one of the previous cases. In this final case, the swap may violate the heap-ordering property for <i>z</i>, so additional rotations may need to be performed to restore this property.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Building_a_treap">Building a treap</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=4" title="Edit section: Building a treap"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>To build a treap we can simply insert n values in the treap where each 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(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" /></span> time. Therefore a treap can be built in <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\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d2320768fb54880ca4356e61f60eb02a3f9d9f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.118ex; height:2.843ex;" alt="{\displaystyle O(n\log n)}" /></span> time from a list values.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Bulk_operations">Bulk operations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=5" title="Edit section: Bulk operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In addition to the single-element insert, delete and lookup operations, several fast "bulk" operations have been defined on treaps: <a href="/wiki/Union_(set_theory)" title="Union (set theory)">union</a>, <a href="/wiki/Intersection_(set_theory)" title="Intersection (set theory)">intersection</a> and <a href="/wiki/Set_difference" class="mw-redirect" title="Set difference">set difference</a>. These rely on two helper operations, <i>split</i> and <i>join</i>. </p> <ul><li>To split a treap into two smaller treaps, those smaller than key <i>x</i>, and those larger than key <i>x</i>, insert <i>x</i> into the treap with maximum priority—larger than the priority of any node in the treap. After this insertion, <i>x</i> will be the root node of the treap, all values less than <i>x</i> will be found in the left subtreap, and all values greater than <i>x</i> will be found in the right subtreap. This costs as much as a single insertion into the treap.</li> <li>Joining two treaps that are the product of a former split, one can safely assume that the greatest value in the first treap is less than the smallest value in the second treap. Create a new node with value <i>x</i>, such that <i>x</i> is larger than this max-value in the first treap and smaller than the min-value in the second treap, assign it the minimum priority, then set its left child to the first heap and its right child to the second heap. Rotate as necessary to fix the heap order. After that, it will be a leaf node, and can easily be deleted. The result is one treap merged from the two original treaps. This is effectively "undoing" a split, and costs the same. More generally, the join operation can work on two treaps and a key with arbitrary priority (i.e., not necessary to be the highest).</li></ul> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Treap_merge.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Treap_merge.svg/250px-Treap_merge.svg.png" decoding="async" width="220" height="76" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Treap_merge.svg/330px-Treap_merge.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Treap_merge.svg/440px-Treap_merge.svg.png 2x" data-file-width="328" data-file-height="113" /></a><figcaption>Join performed on treaps <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 T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}" /></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 T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}" /></span>. Right child 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 T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}" /></span> after the join is defined as a join of its former right child 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 T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}" /></span>.</figcaption></figure> <p>The join algorithm is as follows: </p> <pre><b>function</b> join(L, k, R) <b>if</b> prior(k, k(L)) and prior(k, k(R)) <b>return</b> Node(L, k, R) <b>if</b> prior(k(L), k(R)) <b>return</b> Node(left(L), k(L), join(right(L), k, R)) <b>return</b> Node(join(L, k, left(R)), k(R), right(R)) </pre> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Treap_split.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/69/Treap_split.svg/220px-Treap_split.svg.png" decoding="async" width="220" height="84" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/69/Treap_split.svg/330px-Treap_split.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/69/Treap_split.svg/440px-Treap_split.svg.png 2x" data-file-width="222" data-file-height="85" /></a><figcaption>To split <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 T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" /></span> by <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/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" /></span>, recursive split call is done to either left or right child 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 T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" /></span>.</figcaption></figure> <p>The split algorithm is as follows: </p> <pre><b>function</b> split(T, k) <b>if</b> (T = nil) <b>return</b> (nil, false, nil) (L, (m, c), R) = expose(T) <b>if</b> (k = m) <b>return</b> (L, true, R) <b>if</b> (k < m) (L', b, R') = split(L, k) <b>return</b> (L', b, join(R', m, R)) <b>if</b> (k > m) (L', b, R') = split(R, k) <b>return</b> (join(L, m, L'), b, R')) </pre> <p>The union of two treaps <span class="texhtml"><i>t</i><sub>1</sub></span> and <span class="texhtml"><i>t</i><sub>2</sub></span>, representing sets <span class="texhtml mvar" style="font-style:italic;">A</span> and <span class="texhtml mvar" style="font-style:italic;">B</span> is a treap <span class="texhtml mvar" style="font-style:italic;"><i>t</i></span> that represents <span class="texhtml"><i>A</i> ∪ <i>B</i></span>. The following recursive algorithm computes the union: </p> <pre><b>function</b> union(t<sub>1</sub>, t<sub>2</sub>): <b>if</b> t<sub>1</sub> = nil: <b>return</b> t<sub>2</sub> <b>if</b> t<sub>2</sub> = nil: <b>return</b> t<sub>1</sub> <b>if</b> priority(t<sub>1</sub>) < priority(t<sub>2</sub>): <b>swap</b> t<sub>1</sub> and t<sub>2</sub> t<sub><</sub>, t<sub>></sub> ← split t<sub>2</sub> on key(t<sub>1</sub>) <b>return</b> join(union(left(t<sub>1</sub>), t<sub><</sub>), key(t<sub>1</sub>), union(right(t<sub>1</sub>), t<sub>></sub>)) </pre> <p>Here, <i>split</i> is presumed to return two trees: one holding the keys less than its input key, one holding the greater keys. (The algorithm is <a href="/wiki/Persistent_data_structure" title="Persistent data structure">non-destructive</a>, but an in-place destructive version exists as well.) </p><p>The algorithm for intersection is similar, but requires the <i>join</i> helper routine. The complexity of each of union, intersection and difference is <span class="texhtml"><i>O</i>(<i>m</i> log <style data-mw-deduplicate="TemplateStyles:r1214402035">.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}</style><span class="sfrac">⁠<span class="tion"><span class="num"><i>n</i></span><span class="sr-only">/</span><span class="den"><i>m</i></span></span>⁠</span>)</span> for treaps of sizes <span class="texhtml mvar" style="font-style:italic;">m</span> and <span class="texhtml mvar" style="font-style:italic;">n</span>, with <span class="texhtml"><i>m</i> ≤ <i>n</i></span>. Moreover, since the recursive calls to union are independent of each other, they can be executed <a href="/wiki/Parallel_programming" class="mw-redirect" title="Parallel programming">in parallel</a>.<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> </p><p>Split and Union call Join but do not deal with the balancing criteria of treaps directly, such an implementation is usually called the <a href="/wiki/Join-based_tree_algorithms" title="Join-based tree algorithms">"join-based" implementation</a>. </p><p>Note that if hash values of keys are used as priorities and structurally equal nodes are merged already at construction, then each merged node will be a unique representation of a set of keys. Provided that there can only be one simultaneous root node representing a given set of keys, two sets can be tested for equality by pointer comparison, which is constant in time. </p><p>This technique can be used to enhance the merge algorithms to perform fast also when the difference between two sets is small. If input sets are equal, the union and intersection functions could break immediately returning one of the input sets as result, while the difference function should return the empty set. </p><p>Let <span class="texhtml mvar" style="font-style:italic;">d</span> be the size of the symmetric difference. The modified merge algorithms will then also be bounded by <span class="texhtml"><i>O</i>(<i>d</i> log <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1214402035" /><span class="sfrac">⁠<span class="tion"><span class="num"><i>n</i></span><span class="sr-only">/</span><span class="den"><i>d</i></span></span>⁠</span>)</span>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Confluent_Sets_and_Maps_6-0" class="reference"><a href="#cite_note-Confluent_Sets_and_Maps-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Randomized_binary_search_tree">Randomized binary search tree</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=6" title="Edit section: Randomized binary search tree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The randomized binary search tree, introduced by Martínez and Roura subsequently to the work of Aragon and Seidel on treaps,<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> stores the same nodes with the same random distribution of tree shape, but maintains different information within the nodes of the tree in order to maintain its randomized structure. </p><p>Rather than storing random priorities on each node, the randomized binary search tree stores a small integer at each node, the number of its descendants (counting itself as one); these numbers may be maintained during tree rotation operations at only a constant additional amount of time per rotation. When a key <i>x</i> is to be inserted into a tree that already has <i>n</i> nodes, the insertion algorithm chooses with probability 1/(<i>n</i> + 1) to place <i>x</i> as the new root of the tree, and otherwise, it calls the insertion procedure recursively to insert <i>x</i> within the left or right subtree (depending on whether its key is less than or greater than the root). The numbers of descendants are used by the algorithm to calculate the necessary probabilities for the random choices at each step. Placing <i>x</i> at the root of a subtree may be performed either as in the treap by inserting it at a leaf and then rotating it upwards, or by an alternative algorithm described by Martínez and Roura that splits the subtree into two pieces to be used as the left and right children of the new node. </p><p>The deletion procedure for a randomized binary search tree uses the same information per node as the insertion procedure, but unlike the insertion procedure, it only needs on average O(1) random decisions to join the two subtrees descending from the left and right children of the deleted node into a single tree. That is because the subtrees to be joined are on average at depth Θ(log n); joining two trees of size n and m needs Θ(log(n+m)) random choices on average. If the left or right subtree of the node to be deleted is empty, the join operation is trivial; otherwise, the left or right child of the deleted node is selected as the new subtree root with probability proportional to its number of descendants, and the join proceeds recursively. </p> <div class="mw-heading mw-heading3"><h3 id="Comparison">Comparison</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=7" title="Edit section: Comparison"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The information stored per node in the randomized binary tree is simpler than in a treap (a small integer rather than a high-precision random number), but it makes a greater number of calls to the random number generator (O(log <i>n</i>) calls per insertion or deletion rather than one call per insertion) and the insertion procedure is slightly more complicated due to the need to update the numbers of descendants per node. A minor technical difference is that, in a treap, there is a small probability of a collision (two keys getting the same priority), and in both cases, there will be statistical differences between a true random number generator and the <a href="/wiki/Pseudorandom_number_generator" title="Pseudorandom number generator">pseudo-random number generator</a> typically used on digital computers. However, in any case, the differences between the theoretical model of perfect random choices used to design the algorithm and the capabilities of actual random number generators are vanishingly small. </p><p>Although the treap and the randomized binary search tree both have the same random distribution of tree shapes after each update, the history of modifications to the trees performed by these two data structures over a sequence of insertion and deletion operations may be different. For instance, in a treap, if the three numbers 1, 2, and 3 are inserted in the order 1, 3, 2, and then the number 2 is deleted, the remaining two nodes will have the same parent-child relationship that they did prior to the insertion of the middle number. In a randomized binary search tree, the tree after the deletion is equally likely to be either of the two possible trees on its two nodes, independently of what the tree looked like prior to the insertion of the middle number. </p> <div class="mw-heading mw-heading2"><h2 id="Implicit_treap">Implicit treap</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=8" title="Edit section: Implicit treap"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>An implicit treap <sup id="cite_ref-:0_8-0" class="reference"><a href="#cite_note-:0-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup class="noprint Inline-Template" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Reliable_sources" title="Wikipedia:Reliable sources"><span title="The material near this tag may rely on an unreliable source. (December 2021)">unreliable source?</span></a></i>]</sup> is a simple variation of an ordinary treap which can be viewed as a dynamic array that supports the following operations in <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(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}" /></span>: </p> <ul><li>Inserting an element in any position</li> <li>Removing an element from any position</li> <li>Finding sum, minimum or maximum element in a given range.</li> <li>Addition, painting in a given range</li> <li>Reversing elements in a given range</li></ul> <p>The idea behind an implicit treap is to use the array index as a key, but to not store it explicitly. Otherwise, an update (insertion/deletion) would result in changes of the keys in <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/34109fe397fdcff370079185bfdb65826cb5565a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.977ex; height:2.843ex;" alt="{\displaystyle O(n)}" /></span> nodes of the tree. </p><p>The key value (<b>implicit key)</b> of a node T is the number of nodes less than that node plus one. Note that such nodes can be present not only in its left subtree but also in left subtrees of its ancestors P, if T is in the right subtree of P. </p><p>Therefore we can quickly calculate the implicit key of the current node as we perform an operation by accumulating the sum of all nodes as we descend the tree. Note that this sum does not change when we visit the left subtree but it will increase by <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 cnt(T\rightarrow L)+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>c</mi> <mi>n</mi> <mi>t</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">→</mo> <mi>L</mi> <mo stretchy="false">)</mo> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle cnt(T\rightarrow L)+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1ac469de00351eecb8649a1f4f5be6443148a7c8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.887ex; height:2.843ex;" alt="{\displaystyle cnt(T\rightarrow L)+1}" /></span> when we visit the right subtree. </p><p> The join algorithm for an implicit treap is as follows:</p><div class="mw-highlight mw-highlight-lang-c mw-content-ltr mw-highlight-lines" dir="ltr"><pre><span></span><span class="linenos" data-line="1"></span><span class="kt">void</span><span class="w"> </span><span class="nf">join</span><span class="w"> </span><span class="p">(</span><span class="n">pitem</span><span class="w"> </span><span class="o">&</span><span class="w"> </span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">pitem</span><span class="w"> </span><span class="n">l</span><span class="p">,</span><span class="w"> </span><span class="n">pitem</span><span class="w"> </span><span class="n">r</span><span class="p">)</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="2"></span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="o">!</span><span class="n">l</span><span class="w"> </span><span class="o">||</span><span class="w"> </span><span class="o">!</span><span class="n">r</span><span class="p">)</span> <span class="linenos" data-line="3"></span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">l</span><span class="w"> </span><span class="o">?</span><span class="w"> </span><span class="n">l</span><span class="w"> </span><span class="o">:</span><span class="w"> </span><span class="n">r</span><span class="p">;</span> <span class="linenos" data-line="4"></span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">l</span><span class="o">-></span><span class="n">prior</span><span class="w"> </span><span class="o">></span><span class="w"> </span><span class="n">r</span><span class="o">-></span><span class="n">prior</span><span class="p">)</span> <span class="linenos" data-line="5"></span><span class="w"> </span><span class="n">join</span><span class="w"> </span><span class="p">(</span><span class="n">l</span><span class="o">-></span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">l</span><span class="o">-></span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="p">),</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">l</span><span class="p">;</span> <span class="linenos" data-line="6"></span><span class="w"> </span><span class="k">else</span> <span class="linenos" data-line="7"></span><span class="w"> </span><span class="n">join</span><span class="w"> </span><span class="p">(</span><span class="n">r</span><span class="o">-></span><span class="n">l</span><span class="p">,</span><span class="w"> </span><span class="n">l</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="o">-></span><span class="n">l</span><span class="p">),</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">r</span><span class="p">;</span> <span class="linenos" data-line="8"></span><span class="w"> </span><span class="n">upd_cnt</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="p">);</span> <span class="linenos" data-line="9"></span><span class="p">}</span> </pre></div><p><sup id="cite_ref-:0_8-1" class="reference"><a href="#cite_note-:0-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> The split algorithm for an implicit treap is as follows:</p><div class="mw-highlight mw-highlight-lang-c mw-content-ltr mw-highlight-lines" dir="ltr"><pre><span></span><span class="linenos" data-line="1"></span><span class="kt">void</span><span class="w"> </span><span class="nf">split</span><span class="w"> </span><span class="p">(</span><span class="n">pitem</span><span class="w"> </span><span class="n">t</span><span class="p">,</span><span class="w"> </span><span class="n">pitem</span><span class="w"> </span><span class="o">&</span><span class="w"> </span><span class="n">l</span><span class="p">,</span><span class="w"> </span><span class="n">pitem</span><span class="w"> </span><span class="o">&</span><span class="w"> </span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">key</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">add</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">)</span><span class="w"> </span><span class="p">{</span> <span class="linenos" data-line="2"></span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="o">!</span><span class="n">t</span><span class="p">)</span> <span class="linenos" data-line="3"></span><span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="kt">void</span><span class="p">(</span><span class="w"> </span><span class="n">l</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="p">);</span> <span class="linenos" data-line="4"></span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">cur_key</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">add</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">cnt</span><span class="p">(</span><span class="n">t</span><span class="o">-></span><span class="n">l</span><span class="p">);</span><span class="w"> </span><span class="c1">//implicit key</span> <span class="linenos" data-line="5"></span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">key</span><span class="w"> </span><span class="o"><=</span><span class="w"> </span><span class="n">cur_key</span><span class="p">)</span> <span class="linenos" data-line="6"></span><span class="w"> </span><span class="n">split</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="o">-></span><span class="n">l</span><span class="p">,</span><span class="w"> </span><span class="n">l</span><span class="p">,</span><span class="w"> </span><span class="n">t</span><span class="o">-></span><span class="n">l</span><span class="p">,</span><span class="w"> </span><span class="n">key</span><span class="p">,</span><span class="w"> </span><span class="n">add</span><span class="p">),</span><span class="w"> </span><span class="n">r</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">t</span><span class="p">;</span> <span class="linenos" data-line="7"></span><span class="w"> </span><span class="k">else</span> <span class="linenos" data-line="8"></span><span class="w"> </span><span class="n">split</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="o">-></span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">t</span><span class="o">-></span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">r</span><span class="p">,</span><span class="w"> </span><span class="n">key</span><span class="p">,</span><span class="w"> </span><span class="n">add</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">1</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">cnt</span><span class="p">(</span><span class="n">t</span><span class="o">-></span><span class="n">l</span><span class="p">)),</span><span class="w"> </span><span class="n">l</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">t</span><span class="p">;</span> <span class="linenos" data-line="9"></span><span class="w"> </span><span class="n">upd_cnt</span><span class="w"> </span><span class="p">(</span><span class="n">t</span><span class="p">);</span> <span class="linenos" data-line="10"></span><span class="p">}</span> </pre></div><p><sup id="cite_ref-:0_8-2" class="reference"><a href="#cite_note-:0-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p><div class="mw-heading mw-heading3"><h3 id="Operations_2">Operations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=9" title="Edit section: Operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading4"><h4 id="Insert_element">Insert element</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=10" title="Edit section: Insert element"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To insert an element at position <i>pos</i> we divide the array into two subsections <i>[0...pos-1]</i> and <i>[pos..sz]</i> by calling the <i><b>split</b></i> function and we get two trees <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 T1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/94f4fd16a519756f5b03cf0222c305c9a6ddc8f0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.799ex; height:2.176ex;" alt="{\displaystyle T1}" /></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 T2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1635c7fd497b7dc6e33f845aa9dd0525430ecc48" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.799ex; height:2.176ex;" alt="{\displaystyle T2}" /></span> . Then we merge <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 T1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/94f4fd16a519756f5b03cf0222c305c9a6ddc8f0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.799ex; height:2.176ex;" alt="{\displaystyle T1}" /></span> with the new node by calling the <i><b>join</b></i> function. Finally we call the join function to merge <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 T1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/94f4fd16a519756f5b03cf0222c305c9a6ddc8f0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.799ex; height:2.176ex;" alt="{\displaystyle T1}" /></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 T2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1635c7fd497b7dc6e33f845aa9dd0525430ecc48" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.799ex; height:2.176ex;" alt="{\displaystyle T2}" /></span>. </p> <div class="mw-heading mw-heading4"><h4 id="Delete_element">Delete element</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=11" title="Edit section: Delete element"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>We find the element to be deleted and perform a join on its children L and R. We then replace the element to be deleted with the tree that resulted from the join operation. </p> <div class="mw-heading mw-heading4"><h4 id="Find_sum,_minimum_or_maximum_in_a_given_range"><span id="Find_sum.2C_minimum_or_maximum_in_a_given_range"></span>Find sum, minimum or maximum in a given range</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=12" title="Edit section: Find sum, minimum or maximum in a given range"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To perform this calculation we will proceed as follows: </p> <ul><li>First we will create an additional field F to store the value of the target function for the range represented by that node. we will create a function that calculates the value F based on the values of the L and R children of the node. We will call this target function at the end of all functions that modify the tree, <i>i.e.</i>, split and join.</li> <li>Second we need to process a query for a given range [A..B]: We will call the <b>s<i>plit</i></b> function twice and split the treap into <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 T1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/94f4fd16a519756f5b03cf0222c305c9a6ddc8f0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.799ex; height:2.176ex;" alt="{\displaystyle T1}" /></span> which 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 \{1..A-1\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mn>1..</mn> <mi>A</mi> <mo>−</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{1..A-1\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9afd65ec48b1fce512e29f42004ac88403e68c50" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.527ex; height:2.843ex;" alt="{\displaystyle \{1..A-1\}}" /></span>, <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 T2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1635c7fd497b7dc6e33f845aa9dd0525430ecc48" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.799ex; height:2.176ex;" alt="{\displaystyle T2}" /></span> which 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 \{A..B\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mi>A</mi> <mo>.</mo> <mo>.</mo> <mi>B</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{A..B\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a3603f5fcfcd8d7f1eb8a876bdacf6bce6e39445" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.9ex; height:2.843ex;" alt="{\displaystyle \{A..B\}}" /></span>, and <i><b><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 T3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2bd33f8a66ad38a4c7ae885b620805551a53dbda" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.799ex; height:2.176ex;" alt="{\displaystyle T3}" /></span></b></i> which 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 \{B+1..n\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <mi>B</mi> <mo>+</mo> <mn>1..</mn> <mi>n</mi> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{B+1..n\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e2c3f9eb82ae10d90df7efb02b50fd75df8fdc40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.78ex; height:2.843ex;" alt="{\displaystyle \{B+1..n\}}" /></span>. After the query is answered we will call the <i><b>join</b></i> function twice to restore the original treap.</li></ul> <div class="mw-heading mw-heading4"><h4 id="Addition/painting_in_a_given_range"><span id="Addition.2Fpainting_in_a_given_range"></span>Addition/painting in a given range</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=13" title="Edit section: Addition/painting in a given range"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To perform this operation we will proceed as follows: </p> <ul><li>We will create an extra field D which will contain the added value for the subtree. We will create a function <i><b>push</b></i> which will be used to propagate this change from a node to its children. We will call this function at the beginning of all functions which modify the tree, <i>i.e.</i>, split and join so that after any changes made to the tree the information will not be lost.</li></ul> <div class="mw-heading mw-heading4"><h4 id="Reverse_in_a_given_range">Reverse in a given range</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Treap&action=edit&section=14" title="Edit section: Reverse in a given range"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To show that the subtree of a given node needs to be reversed for each node we will create an extra boolean field R and set its value to true. To propagate this change we will swap the children of the node and set R to true for all of them. </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=Treap&action=edit&section=15" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Finger_search" title="Finger search">Finger search</a></li> <li><a href="/wiki/TreapDB" title="TreapDB">TreapDB</a></li></ul> <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=Treap&action=edit&section=16" 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"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-paper89-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-paper89_1-0">^</a></b></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="CITEREFAragonSeidel1989" class="citation cs2">Aragon, Cecilia R.; Seidel, Raimund (1989), <a rel="nofollow" class="external text" href="http://faculty.washington.edu/aragon/pubs/rst89.pdf">"Randomized Search Trees"</a> <span class="cs1-format">(PDF)</span>, <a href="/wiki/Symposium_on_Foundations_of_Computer_Science" title="Symposium on Foundations of Computer Science"><i>30th Annual Symposium on Foundations of Computer Science</i></a>, Washington, D.C.: IEEE Computer Society Press, pp. <span class="nowrap">540–</span>545, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1989.63531">10.1109/SFCS.1989.63531</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-8186-1982-1" title="Special:BookSources/0-8186-1982-1"><bdi>0-8186-1982-1</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Randomized+Search+Trees&rft.btitle=30th+Annual+Symposium+on+Foundations+of+Computer+Science&rft.place=Washington%2C+D.C.&rft.pages=%3Cspan+class%3D%22nowrap%22%3E540-%3C%2Fspan%3E545&rft.pub=IEEE+Computer+Society+Press&rft.date=1989&rft_id=info%3Adoi%2F10.1109%2FSFCS.1989.63531&rft.isbn=0-8186-1982-1&rft.aulast=Aragon&rft.aufirst=Cecilia+R.&rft.au=Seidel%2C+Raimund&rft_id=http%3A%2F%2Ffaculty.washington.edu%2Faragon%2Fpubs%2Frst89.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATreap" class="Z3988"></span></span> </li> <li id="cite_note-paper96-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-paper96_2-0">^</a></b></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSeidelAragon1996" class="citation cs2">Seidel, Raimund; Aragon, Cecilia R. (1996), <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8602">"Randomized Search Trees"</a>, <i>Algorithmica</i>, <b>16</b> (4/5): <span class="nowrap">464–</span>497, <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%2Fs004539900061">10.1007/s004539900061</a> (inactive 1 November 2024)</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Algorithmica&rft.atitle=Randomized+Search+Trees&rft.volume=16&rft.issue=4%2F5&rft.pages=%3Cspan+class%3D%22nowrap%22%3E464-%3C%2Fspan%3E497&rft.date=1996&rft_id=info%3Adoi%2F10.1007%2Fs004539900061&rft.aulast=Seidel&rft.aufirst=Raimund&rft.au=Aragon%2C+Cecilia+R.&rft_id=http%3A%2F%2Fciteseer.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.30.8602&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATreap" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Citation" title="Template:Citation">citation</a>}}</code>: CS1 maint: DOI inactive as of November 2024 (<a href="/wiki/Category:CS1_maint:_DOI_inactive_as_of_November_2024" title="Category:CS1 maint: DOI inactive as of November 2024">link</a>)</span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFNaorNissim2000" class="citation cs2"><a href="/wiki/Moni_Naor" title="Moni Naor">Naor, M.</a>; Nissim, K. (April 2000), <a rel="nofollow" class="external text" href="http://eprints.kfupm.edu.sa/29443/1/29443.pdf">"Certificate revocation and certificate update"</a> <span class="cs1-format">(PDF)</span>, <i>IEEE Journal on Selected Areas in Communications</i>, <b>18</b> (4): <span class="nowrap">561–</span>570, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F49.839932">10.1109/49.839932</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:13833836">13833836</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Journal+on+Selected+Areas+in+Communications&rft.atitle=Certificate+revocation+and+certificate+update&rft.volume=18&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E561-%3C%2Fspan%3E570&rft.date=2000-04&rft_id=info%3Adoi%2F10.1109%2F49.839932&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A13833836%23id-name%3DS2CID&rft.aulast=Naor&rft.aufirst=M.&rft.au=Nissim%2C+K.&rft_id=http%3A%2F%2Feprints.kfupm.edu.sa%2F29443%2F1%2F29443.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATreap" class="Z3988"></span><sup class="noprint Inline-Template"><span style="white-space: nowrap;">[<i><a href="/wiki/Wikipedia:Link_rot" title="Wikipedia:Link rot"><span title=" Dead link tagged March 2018">permanent dead link</span></a></i><span style="visibility:hidden; color:transparent; padding-left:2px">‍</span>]</span></sup>.</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="CITEREFBlellochReid-Miller1998" class="citation cs2">Blelloch, Guy E.; Reid-Miller, Margaret (1998), "Fast set operations using treaps", <a href="/wiki/Symposium_on_Parallel_Algorithms_and_Architectures" class="mw-redirect" title="Symposium on Parallel Algorithms and Architectures"><i>Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures - SPAA '98</i></a>, New York, NY, USA: ACM, pp. <span class="nowrap">16–</span>26, <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%2F277651.277660">10.1145/277651.277660</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-89791-989-0" title="Special:BookSources/0-89791-989-0"><bdi>0-89791-989-0</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:7342709">7342709</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Fast+set+operations+using+treaps&rft.btitle=Proceedings+of+the+tenth+annual+ACM+symposium+on+Parallel+algorithms+and+architectures+-+SPAA+%2798&rft.place=New+York%2C+NY%2C+USA&rft.pages=%3Cspan+class%3D%22nowrap%22%3E16-%3C%2Fspan%3E26&rft.pub=ACM&rft.date=1998&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A7342709%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F277651.277660&rft.isbn=0-89791-989-0&rft.aulast=Blelloch&rft.aufirst=Guy+E.&rft.au=Reid-Miller%2C+Margaret&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATreap" class="Z3988"></span>.</span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFLiljenzin2013" class="citation journal cs1">Liljenzin, Olle (2013). "Confluently Persistent Sets and Maps". <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/1301.3388">1301.3388</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/2013arXiv1301.3388L">2013arXiv1301.3388L</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Confluently+Persistent+Sets+and+Maps&rft.date=2013&rft_id=info%3Aarxiv%2F1301.3388&rft_id=info%3Abibcode%2F2013arXiv1301.3388L&rft.aulast=Liljenzin&rft.aufirst=Olle&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATreap" class="Z3988"></span> <span class="cs1-visible-error citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_journal" title="Template:Cite journal">cite journal</a>}}</code>: </span><span class="cs1-visible-error citation-comment">Cite journal requires <code class="cs1-code">|journal=</code> (<a href="/wiki/Help:CS1_errors#missing_periodical" title="Help:CS1 errors">help</a>)</span></span> </li> <li id="cite_note-Confluent_Sets_and_Maps-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Confluent_Sets_and_Maps_6-0">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://github.com/liljenzin/confluent">Confluent Sets and Maps on GitHub</a></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFMartínezRoura1997" class="citation cs2">Martínez, Conrado; Roura, Salvador (1997), <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.243">"Randomized binary search trees"</a>, <i>Journal of the ACM</i>, <b>45</b> (2): <span class="nowrap">288–</span>323, <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%2F274787.274812">10.1145/274787.274812</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:714621">714621</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Randomized+binary+search+trees&rft.volume=45&rft.issue=2&rft.pages=%3Cspan+class%3D%22nowrap%22%3E288-%3C%2Fspan%3E323&rft.date=1997&rft_id=info%3Adoi%2F10.1145%2F274787.274812&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A714621%23id-name%3DS2CID&rft.aulast=Mart%C3%ADnez&rft.aufirst=Conrado&rft.au=Roura%2C+Salvador&rft_id=http%3A%2F%2Fciteseer.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.17.243&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATreap" class="Z3988"></span></span> </li> <li id="cite_note-:0-8"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_8-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_8-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:0_8-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 class="citation web cs1"><a rel="nofollow" class="external text" href="https://cp-algorithms.com/data_structures/treap.html#toc-tgt-1">"Treap - Competitive Programming Algorithms"</a>. <i>cp-algorithms.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-11-21</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=cp-algorithms.com&rft.atitle=Treap+-+Competitive+Programming+Algorithms&rft_id=https%3A%2F%2Fcp-algorithms.com%2Fdata_structures%2Ftreap.html%23toc-tgt-1&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATreap" class="Z3988"></span></span> </li> </ol></div></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=Treap&action=edit&section=17" 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"><a href="/wiki/File:Commons-logo.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/40px-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/60px-Commons-logo.svg.png 1.5x" data-file-width="1024" data-file-height="1376" /></a></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:Treap" class="extiw" title="commons:Category:Treap">Treap</a></span>.</div></div> </div> <ul><li><a rel="nofollow" class="external text" href="http://faculty.washington.edu/aragon/treaps.html">Collection of treap references and info</a> by Cecilia Aragon</li> <li><a rel="nofollow" class="external text" href="http://opendatastructures.org/versions/edition-0.1e/ods-java/7_2_Treap_Randomized_Binary.html">Open Data Structures - Section 7.2 - Treap: A Randomized Binary Search Tree</a>, <a href="/wiki/Pat_Morin" title="Pat Morin">Pat Morin</a></li> <li><a rel="nofollow" class="external text" href="http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applets/BST/Treap-Example.html">Animated treap</a></li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20110605030306/http://www.cs.uiuc.edu/class/sp09/cs473/notes/08-treaps.pdf">Randomized binary search trees</a>. Lecture notes from a course by Jeff Erickson at UIUC. Despite the title, this is primarily about treaps and <a href="/wiki/Skip_list" title="Skip list">skip lists</a>; randomized binary search trees are mentioned only briefly.</li> <li><a rel="nofollow" class="external text" href="https://code.google.com/p/treapdb/">A high-performance key-value store based on treap</a> by Junyi Sun</li> <li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20100127041439/http://www.fernando-rodriguez.com/a-high-performance-alternative-to-dictionary">VB6 implementation of treaps</a>. Visual basic 6 implementation of treaps as a COM object.</li> <li><a rel="nofollow" class="external text" href="https://code.google.com/p/as3-commons/source/browse/trunk/as3-commons-collections/src/main/actionscript/org/as3commons/collections/Treap.as">ActionScript3 implementation of a treap</a></li> <li><a rel="nofollow" class="external text" href="https://pypi.python.org/pypi/treap/">Pure Python and Cython in-memory treap and duptreap</a></li> <li><a rel="nofollow" class="external text" href="http://www.codeproject.com/Articles/8184/Treaps-in-C">Treaps in C#</a>. By Roy Clemmons</li> <li><a rel="nofollow" class="external text" href="https://github.com/steveyen/gtreap">Pure Go in-memory, immutable treaps</a></li> <li><a rel="nofollow" class="external text" href="https://github.com/steveyen/gkvlite">Pure Go persistent treap key-value storage library</a></li></ul> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374" /><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_structures237" 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: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_structures237" 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 class="mw-selflink selflink">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 href="/wiki/Trie" title="Trie">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><noscript><img src="https://auth.wikimedia.org/loginwiki/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=1" 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=Treap&oldid=1284025014">https://en.wikipedia.org/w/index.php?title=Treap&oldid=1284025014</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:Heaps_(data_structures)" title="Category:Heaps (data structures)">Heaps (data structures)</a></li><li><a href="/wiki/Category:Binary_trees" title="Category:Binary trees">Binary trees</a></li><li><a href="/wiki/Category:Probabilistic_data_structures" title="Category:Probabilistic data structures">Probabilistic data structures</a></li><li><a href="/wiki/Category:Search_trees" title="Category:Search trees">Search trees</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:CS1_maint:_DOI_inactive_as_of_November_2024" title="Category:CS1 maint: DOI inactive as of November 2024">CS1 maint: DOI inactive as of November 2024</a></li><li><a href="/wiki/Category:All_articles_with_dead_external_links" title="Category:All articles with dead external links">All articles with dead external links</a></li><li><a href="/wiki/Category:Articles_with_dead_external_links_from_March_2018" title="Category:Articles with dead external links from March 2018">Articles with dead external links from March 2018</a></li><li><a href="/wiki/Category:Articles_with_permanently_dead_external_links" title="Category:Articles with permanently dead external links">Articles with permanently dead external links</a></li><li><a href="/wiki/Category:CS1_errors:_missing_periodical" title="Category:CS1 errors: missing periodical">CS1 errors: missing periodical</a></li><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:All_articles_lacking_reliable_references" title="Category:All articles lacking reliable references">All articles lacking reliable references</a></li><li><a href="/wiki/Category:Articles_lacking_reliable_references_from_December_2021" title="Category:Articles lacking reliable references from December 2021">Articles lacking reliable references from December 2021</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></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 5 April 2025, at 03:42<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=Treap&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://www.wikimedia.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></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"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" lang="en" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div 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"> <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> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-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-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Treap</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>13 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="mw-portlet mw-portlet-dock-bottom emptyPortlet" id="p-dock-bottom"> <ul> </ul> </div> <script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-7dbbdd594f-dqs5c","wgBackendResponseTime":142,"wgPageParseReport":{"limitreport":{"cputime":"0.410","walltime":"0.705","ppvisitednodes":{"value":2045,"limit":1000000},"postexpandincludesize":{"value":52176,"limit":2097152},"templateargumentsize":{"value":3211,"limit":2097152},"expansiondepth":{"value":17,"limit":100},"expensivefunctioncount":{"value":5,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":60879,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 545.784 1 -total"," 21.36% 116.563 1 Template:Reflist"," 15.54% 84.823 5 Template:Citation"," 12.70% 69.341 1 Template:Probabilistic"," 12.16% 66.344 1 Template:Sidebar"," 11.96% 65.265 1 Template:Short_description"," 7.85% 42.846 1 Template:Infobox_data_structure"," 6.91% 37.722 1 Template:Infobox"," 6.58% 35.886 1 Template:Commonscat"," 6.38% 34.830 1 Template:CS-Trees"]},"scribunto":{"limitreport-timeusage":{"value":"0.236","limit":"10.000"},"limitreport-memusage":{"value":6574123,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-7dbbdd594f-rx9zz","timestamp":"20250405034311","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Treap","url":"https:\/\/en.wikipedia.org\/wiki\/Treap","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1757700","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1757700","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":"2003-06-20T01:31:22Z","dateModified":"2025-04-05T03:42:02Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/e\/e4\/Treap.svg","headline":"binary search tree in which the nodes are heap-ordered by random priorities"}</script> </body> </html>