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>k-d tree - 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":"fc48ee1e-13a7-42bc-9380-d2c9015e32eb","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"K-d_tree","wgTitle":"K-d tree","wgCurRevisionId":1251096500,"wgRevisionId":1251096500,"wgArticleId":1676725,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description matches Wikidata","Commons category link is locally defined","Articles to be expanded from November 2008","All articles to be expanded","Articles to be expanded from February 2011","Articles with example Python (programming language) code","Computer graphics data structures","Trees (data structures)","Geometric data structures","Database index techniques","Data types","Rectangular subdivisions"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"K-d_tree","wgRelevantArticleId":1676725,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q309949","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false}; RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.math.styles":"ready","ext.cite.styles":"ready","ext.tmh.player.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","ext.tmh.player","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</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.tmh.player.styles%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.20"> <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/b/b6/3dtree.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1141"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/b/b6/3dtree.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="761"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="608"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="k-d tree - 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/K-d_tree"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=K-d_tree&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/K-d_tree"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-K-d_tree rootpage-K-d_tree 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=K-d+tree" 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=K-d+tree" 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=K-d+tree" 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=K-d+tree" 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_on_k-d_trees" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Operations_on_k-d_trees"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Operations on <i>k</i>-d trees</span> </div> </a> <button aria-controls="toc-Operations_on_k-d_trees-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 on <i>k</i>-d trees subsection</span> </button> <ul id="toc-Operations_on_k-d_trees-sublist" class="vector-toc-list"> <li id="toc-Construction" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Construction"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Construction</span> </div> </a> <ul id="toc-Construction-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Adding_elements" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Adding_elements"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Adding elements</span> </div> </a> <ul id="toc-Adding_elements-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Removing_elements" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Removing_elements"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Removing elements</span> </div> </a> <ul id="toc-Removing_elements-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Balancing" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Balancing"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>Balancing</span> </div> </a> <ul id="toc-Balancing-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Nearest_neighbour_search" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Nearest_neighbour_search"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.5</span> <span>Nearest neighbour search</span> </div> </a> <ul id="toc-Nearest_neighbour_search-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Range_search" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Range_search"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.6</span> <span>Range search</span> </div> </a> <ul id="toc-Range_search-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Degradation_in_performance_with_high-dimensional_data" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Degradation_in_performance_with_high-dimensional_data"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Degradation in performance with high-dimensional data</span> </div> </a> <ul id="toc-Degradation_in_performance_with_high-dimensional_data-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Degradation_in_performance_when_the_query_point_is_far_from_points_in_the_k-d_tree" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Degradation_in_performance_when_the_query_point_is_far_from_points_in_the_k-d_tree"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Degradation in performance when the query point is far from points in the <i>k</i>-d tree</span> </div> </a> <ul id="toc-Degradation_in_performance_when_the_query_point_is_far_from_points_in_the_k-d_tree-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Complexity" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Complexity</span> </div> </a> <ul id="toc-Complexity-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Variations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Variations"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Variations</span> </div> </a> <button aria-controls="toc-Variations-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 Variations subsection</span> </button> <ul id="toc-Variations-sublist" class="vector-toc-list"> <li id="toc-Volumetric_objects" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Volumetric_objects"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.1</span> <span>Volumetric objects</span> </div> </a> <ul id="toc-Volumetric_objects-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Points_only_in_leaves" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Points_only_in_leaves"> <div class="vector-toc-text"> <span class="vector-toc-numb">6.2</span> <span>Points only in leaves</span> </div> </a> <ul id="toc-Points_only_in_leaves-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Open_source_implementations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Open_source_implementations"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>Open source implementations</span> </div> </a> <ul id="toc-Open_source_implementations-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">9</span> <span>References</span> </div> </a> <ul id="toc-References-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"><i>k</i>-d tree</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 14 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-14" 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">14 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/K-d-Baum" title="K-d-Baum – German" lang="de" hreflang="de" data-title="K-d-Baum" 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/%C3%81rbol_kd" title="Árbol kd – Spanish" lang="es" hreflang="es" data-title="Árbol kd" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%DA%A9%DB%8C%E2%80%8C%D8%AF%DB%8C" title="درخت کی‌دی – Persian" lang="fa" hreflang="fa" data-title="درخت کی‌دی" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Arbre_kd" title="Arbre kd – French" lang="fr" hreflang="fr" data-title="Arbre kd" 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-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/K-d_%ED%8A%B8%EB%A6%AC" title="K-d 트리 – Korean" lang="ko" hreflang="ko" data-title="K-d 트리" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A2%D7%A5_kd" title="עץ kd – Hebrew" lang="he" hreflang="he" data-title="עץ kd" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/Kd%E6%9C%A8" title="Kd木 – Japanese" lang="ja" hreflang="ja" data-title="Kd木" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Drzewo_kd" title="Drzewo kd – Polish" lang="pl" hreflang="pl" data-title="Drzewo kd" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/%C3%81rvore_k-d" title="Árvore k-d – Portuguese" lang="pt" hreflang="pt" data-title="Árvore k-d" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/K-d-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="K-d-дерево – Russian" lang="ru" hreflang="ru" data-title="K-d-дерево" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sl mw-list-item"><a href="https://sl.wikipedia.org/wiki/KD_drevo" title="KD drevo – Slovenian" lang="sl" hreflang="sl" data-title="KD drevo" data-language-autonym="Slovenščina" data-language-local-name="Slovenian" class="interlanguage-link-target"><span>Slovenščina</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/K-D_stablo" title="K-D stablo – Serbian" lang="sr" hreflang="sr" data-title="K-D stablo" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/K-%D0%B2%D0%B8%D0%BC%D1%96%D1%80%D0%BD%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE" title="K-вимірне дерево – Ukrainian" lang="uk" hreflang="uk" data-title="K-вимірне дерево" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/K-d%E6%A0%91" title="K-d树 – Chinese" lang="zh" hreflang="zh" data-title="K-d树" 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/Q309949#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/K-d_tree" 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:K-d_tree" 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/K-d_tree"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=K-d_tree&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=K-d_tree&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/K-d_tree"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=K-d_tree&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=K-d_tree&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/K-d_tree" 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/K-d_tree" 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=K-d_tree&oldid=1251096500" 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=K-d_tree&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=K-d_tree&id=1251096500&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%2FK-d_tree"><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%2FK-d_tree"><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=K-d_tree&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=K-d_tree&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:K-d_trees" 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/Q309949" 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">Multidimensional search tree for points in k dimensional space</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"><i>k</i>-d tree</th></tr><tr><td colspan="2" class="infobox-image"><span class="mw-default-size" typeof="mw:File/Frameless"><a href="/wiki/File:3dtree.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/b/b6/3dtree.png/220px-3dtree.png" decoding="async" width="220" height="209" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/b6/3dtree.png/330px-3dtree.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/b6/3dtree.png/440px-3dtree.png 2x" data-file-width="548" data-file-height="521" /></a></span><div class="infobox-caption">A 3-dimensional <i>k</i>-d tree. The first split (the red vertical plane) cuts the root cell (white) into two subcells, each of which is then split (by the green horizontal planes) into two subcells. Finally, four cells are split (by the four blue vertical planes) into two subcells. Since there is no more splitting, the final eight are called leaf cells.</div></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">Multidimensional <a href="/wiki/Binary_Search_Tree" class="mw-redirect" title="Binary Search Tree">BST</a></td></tr><tr><th scope="row" class="infobox-label">Invented</th><td class="infobox-data">1975</td></tr><tr><th scope="row" class="infobox-label">Invented by</th><td class="infobox-data"><a href="/wiki/Jon_Bentley_(computer_scientist)" title="Jon Bentley (computer scientist)">Jon Louis Bentley</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"> <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></td><td class="infobox-data infobox-data-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 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></td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Insert</th><td class="infobox-data infobox-data-a"> <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></td><td class="infobox-data infobox-data-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 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></td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Delete</th><td class="infobox-data infobox-data-a"> <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></td><td class="infobox-data infobox-data-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 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></td></tr><tr><th colspan="4" class="infobox-header"><a href="/wiki/Space_complexity" title="Space complexity">Space complexity</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Space</th><td class="infobox-data infobox-data-a"> <span class="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></td><td class="infobox-data infobox-data-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 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></td></tr></tbody></table></td></tr></tbody></table> <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:k-d_trees" class="extiw" title="commons:Category:k-d trees">k-d trees</a></span>.</div></div> </div> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, a <b><i>k</i>-d tree</b> (short for <i>k-dimensional <a href="/wiki/Tree_data_structure" class="mw-redirect" title="Tree data structure">tree</a></i>) is a <a href="/wiki/Space_partitioning" title="Space partitioning">space-partitioning</a> <a href="/wiki/Data_structure" title="Data structure">data structure</a> for organizing <a href="/wiki/Point_(geometry)" title="Point (geometry)">points</a> in a <i>k</i>-dimensional <a href="/wiki/Euclidean_space" title="Euclidean space">space</a>. K-dimensional is that which concerns exactly k orthogonal axes or a space of any number of <a href="/wiki/Dimension" title="Dimension">dimensions</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> <i>k</i>-d trees are a useful data structure for several applications, such as: </p> <ul><li>Searches involving a multidimensional search key (e.g. <a href="/wiki/Range_search" class="mw-redirect" title="Range search">range searches</a> and <a href="/wiki/Nearest_neighbor_search" title="Nearest neighbor search">nearest neighbor searches</a>) &</li> <li>Creating <a href="/wiki/Point_cloud" title="Point cloud">point clouds</a>.</li></ul> <p><i>k</i>-d trees are a special case of <a href="/wiki/Binary_space_partitioning" title="Binary space partitioning">binary space partitioning</a> trees. </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=K-d_tree&action=edit&section=1" title="Edit section: Description"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <i>k</i>-d tree is a <a href="/wiki/Binary_tree" title="Binary tree">binary tree</a> in which <i>every</i> node is a <i>k</i>-dimensional point.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Every non-leaf node can be thought of as implicitly generating a splitting <a href="/wiki/Hyperplane" title="Hyperplane">hyperplane</a> that divides the space into two parts, known as <a href="/wiki/Half-space_(geometry)" title="Half-space (geometry)">half-spaces</a>. Points to the left of this hyperplane are represented by the left subtree of that node and points to the right of the <a href="/wiki/Hyperplane" title="Hyperplane">hyperplane</a> are represented by the right subtree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the <i>k</i> dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with a larger "x" value will be in the right subtree. In such a case, the hyperplane would be set by the x value of the point, and its <a href="/wiki/Surface_normal" class="mw-redirect" title="Surface normal">normal</a> would be the unit x-axis.<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> </p> <figure class="mw-halign-none" typeof="mw:File/Thumb"><a href="/wiki/File:Kd-tree-example-with_records_as_leaf_nodes.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Kd-tree-example-with_records_as_leaf_nodes.png/1193px-Kd-tree-example-with_records_as_leaf_nodes.png" decoding="async" width="1193" height="321" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Kd-tree-example-with_records_as_leaf_nodes.png/1790px-Kd-tree-example-with_records_as_leaf_nodes.png 1.5x, //upload.wikimedia.org/wikipedia/commons/4/4f/Kd-tree-example-with_records_as_leaf_nodes.png 2x" data-file-width="1904" data-file-height="512" /></a><figcaption>Example of a 3 dimensional k-d tree</figcaption></figure> <div class="mw-heading mw-heading2"><h2 id="Operations_on_k-d_trees">Operations on <i>k</i>-d trees</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=2" title="Edit section: Operations on k-d trees"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Construction">Construction</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=3" title="Edit section: Construction"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Since there are many possible ways to choose axis-aligned splitting planes, there are many different ways to construct <i>k</i>-d trees. The canonical method of <i>k</i>-d tree construction has the following constraints:<sup id="cite_ref-compgeom_4-0" class="reference"><a href="#cite_note-compgeom-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <ul><li>As one moves down the tree, one cycles through the axes used to select the splitting planes. (For example, in a 3-dimensional tree, the root would have an <i>x</i>-aligned plane, the root's children would both have <i>y</i>-aligned planes, the root's grandchildren would all have <i>z</i>-aligned planes, the root's great-grandchildren would all have <i>x</i>-aligned planes, the root's great-great-grandchildren would all have <i>y</i>-aligned planes, and so on.)</li> <li>Points are inserted by selecting the <a href="/wiki/Median" title="Median">median</a> of the points being put into the <a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">subtree</a>, with respect to their coordinates in the axis being used to create the splitting plane. (Note the assumption that we feed the entire set of <i>n</i> points into the algorithm up-front.)</li></ul> <p>This method leads to a <a href="/wiki/Balanced_tree" class="mw-redirect" title="Balanced tree">balanced</a> <i>k</i>-d tree, in which each leaf node is approximately the same distance from the root. However, <a href="/wiki/Balanced_trees" class="mw-redirect" title="Balanced trees">balanced trees</a> are not necessarily optimal for all applications. </p><p>Note that it is not <i>required</i> to select the median point. In the case where median points are not selected, there is no guarantee that the tree will be balanced. To avoid coding a complex <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> <a href="/wiki/Selection_algorithm" title="Selection algorithm">median-finding</a> <a href="/wiki/Algorithm" title="Algorithm">algorithm</a><sup id="cite_ref-blum_5-0" class="reference"><a href="#cite_note-blum-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-cormen_6-0" class="reference"><a href="#cite_note-cormen-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> or using an <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> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <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/85994022c28e938772bd858cd8281328643e8b3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.54ex; height:2.843ex;" alt="{\displaystyle O(n\log(n))}" /></span> sort such as <a href="/wiki/Heapsort" title="Heapsort">heapsort</a> or <a href="/wiki/Mergesort" class="mw-redirect" title="Mergesort">mergesort</a> to sort all <i>n</i> points, a popular practice is to sort a <i>fixed</i> number of <i>randomly</i> <i>selected</i> points, and use the median of those points to serve as the splitting plane. In practice, this technique often results in nicely balanced trees. </p><p>Given a list of <i>n</i> points, the following algorithm uses a median-finding sort to construct a balanced <i>k</i>-d tree containing those points. </p> <pre><b>function</b> kdtree (<i>list of points</i> pointList, <i>int</i> depth) { <i>// Select axis based on depth so that axis cycles through all valid values</i> <b>var</b> <i>int</i> axis := depth <b>mod</b> k; <i>// Sort point list and choose median as pivot element</i> <b><a href="/wiki/Selection_algorithm" title="Selection algorithm">select</a></b> median <b>by</b> axis <b>from</b> pointList; <i>// Create node and construct subtree</i> node.location := median; node.leftChild := kdtree(points <b>in</b> pointList <b>before</b> median, depth+1); node.rightChild := kdtree(points <b>in</b> pointList <b>after</b> median, depth+1); <b>return</b> node; } </pre> <p>It is common that points "after" the median include only the ones that are strictly greater than the median in the current dimension. For points that lie on the median in the current dimension, it is possible to define a function that compares them in all dimensions. In some cases, it is acceptable to let points equal to the median lie on one side of the median, for example, by splitting the points into a "lesser than" subset and a "greater than or equal to" subset. </p><p>This algorithm creates the <a href="/wiki/Invariant_(computer_science)" class="mw-redirect" title="Invariant (computer science)">invariant</a> that for any node, all the nodes in the left <a href="/wiki/Subtree" class="mw-redirect" title="Subtree">subtree</a> are on one side of a splitting <a href="/wiki/Plane_(mathematics)" title="Plane (mathematics)">plane</a>, and all the nodes in the right subtree are on the other side. Points that lie on the splitting plane may appear on either side. The splitting plane of a node goes through the point associated with that node (referred to in the code as <i>node.location</i>). </p><p>Alternative algorithms for building a balanced <span class="nowrap"><i>k</i>-d tree</span> presort the data prior to building the tree. Then, they maintain the order of the presort during tree construction and hence eliminate the costly step of finding the median at each level of subdivision. Two such algorithms build a balanced <span class="nowrap"><i>k</i>-d tree</span> to sort triangles in order to improve the execution time of <a href="/wiki/Ray_tracing_(graphics)" title="Ray tracing (graphics)">ray tracing</a> for three-dimensional <a href="/wiki/Computer_graphics" title="Computer graphics">computer graphics</a>. These algorithms presort <i>n</i> triangles prior to building the <span class="nowrap"><i>k</i>-d tree</span>, then build the tree 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 in the best case.<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><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> An algorithm that builds a balanced <span class="nowrap"><i>k</i>-d tree</span> to sort points has a worst-case complexity of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(kn\log(n))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(kn\log(n))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9761d4101c6d72e544d56d60f255f837293ebb02" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.751ex; height:2.843ex;" alt="{\displaystyle O(kn\log(n))}" /></span>.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-knlogn_10-0" class="reference"><a href="#cite_note-knlogn-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> This algorithm presorts <i>n</i> points in each of <i>k</i> dimensions using an <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> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <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/85994022c28e938772bd858cd8281328643e8b3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.54ex; height:2.843ex;" alt="{\displaystyle O(n\log(n))}" /></span> sort such as <a href="/wiki/Heapsort" title="Heapsort">Heapsort</a> or <a href="/wiki/Mergesort" class="mw-redirect" title="Mergesort">Mergesort</a> prior to building the tree. It then maintains the order of these <i>k</i> presorts during tree construction and thereby avoids finding the median at each level of subdivision. </p> <div class="mw-heading mw-heading3"><h3 id="Adding_elements">Adding elements</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=4" title="Edit section: Adding elements"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-Expand_section plainlinks metadata ambox mbox-small-left ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><span typeof="mw:File"><a href="/wiki/File:Wiki_letter_w_cropped.svg" class="mw-file-description"><img alt="[icon]" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png" decoding="async" width="20" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/30px-Wiki_letter_w_cropped.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/40px-Wiki_letter_w_cropped.svg.png 2x" data-file-width="44" data-file-height="31" /></a></span></td><td class="mbox-text"><div class="mbox-text-span">This section <b>needs expansion</b>. You can help by <a class="external text" href="https://en.wikipedia.org/w/index.php?title=K-d_tree&action=edit&section=">adding to it</a>. <span class="date-container"><i>(<span class="date">November 2008</span>)</i></span></div></td></tr></tbody></table> <p>One adds a new point to a <i>k</i>-d tree in the same way as one adds an element to any other <a href="/wiki/Binary_search_tree" title="Binary search tree">search tree</a>. First, traverse the tree, starting from the root and moving to either the left or the right child depending on whether the point to be inserted is on the "left" or "right" side of the splitting plane. Once you get to the node under which the child should be located, add the new point as either the left or right child of the leaf node, again depending on which side of the node's splitting plane contains the new node. </p><p>Adding points in this manner can cause the tree to become unbalanced, leading to decreased tree performance. The rate of tree performance degradation is dependent upon the spatial distribution of tree points being added, and the number of points added in relation to the tree size. If a tree becomes too unbalanced, it may need to be re-balanced to restore the performance of queries that rely on the tree balancing, such as nearest neighbour searching. </p> <div class="mw-heading mw-heading3"><h3 id="Removing_elements">Removing elements</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=5" title="Edit section: Removing elements"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444" /><table class="box-Expand_section plainlinks metadata ambox mbox-small-left ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><span typeof="mw:File"><a href="/wiki/File:Wiki_letter_w_cropped.svg" class="mw-file-description"><img alt="[icon]" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png" decoding="async" width="20" height="14" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/30px-Wiki_letter_w_cropped.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/40px-Wiki_letter_w_cropped.svg.png 2x" data-file-width="44" data-file-height="31" /></a></span></td><td class="mbox-text"><div class="mbox-text-span">This section <b>needs expansion</b>. You can help by <a class="external text" href="https://en.wikipedia.org/w/index.php?title=K-d_tree&action=edit&section=">adding to it</a>. <span class="date-container"><i>(<span class="date">February 2011</span>)</i></span></div></td></tr></tbody></table> <p>To remove a point from an existing <i>k</i>-d tree without breaking the invariant, the easiest way is to form the set of all nodes and leaves from the children of the target node and recreate that part of the tree.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p><p>Another approach is to find a replacement for the point removed.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> First, find the node <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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" /></span> that contains the point to be removed. For the base case, where R is a leaf node, no replacement is required. For the general case, find a replacement point, say <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 p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" /></span>, from the subtree rooted at <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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" /></span>. Replace the point stored at <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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" /></span> with <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 p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" /></span>. Then, recursively remove <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 p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" /></span>. </p><p>For finding a replacement point, if <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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" /></span> discriminates on <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> (say) 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 R}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>R</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b0bfb3769bf24d80e15374dc37b0441e2616e33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" /></span> has a right child, find the point with the minimum <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> value from the subtree rooted at the right child. Otherwise, find the point with the maximum <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> value from the subtree rooted at the left child. </p> <div class="mw-heading mw-heading3"><h3 id="Balancing">Balancing</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=6" title="Edit section: Balancing"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Balancing a <i>k</i>-d tree requires care because <i>k</i>-d trees are sorted in multiple dimensions, so the <a href="/wiki/Tree_rotation" title="Tree rotation">tree-rotation</a> technique cannot be used to balance them as this may break the invariant. </p><p>Several variants of balanced <i>k</i>-d trees exist. They include divided <i>k</i>-d tree, pseudo <i>k</i>-d tree, <a href="/wiki/K-D-B-tree" title="K-D-B-tree">K-D-B-tree</a>, hB-tree and <a href="/wiki/K-D-B-tree#BKD_tree" title="K-D-B-tree">Bkd-tree</a>. Many of these variants are <a href="/wiki/Adaptive_k-d_tree" title="Adaptive k-d tree">adaptive k-d trees</a>. </p> <div class="mw-heading mw-heading3"><h3 id="Nearest_neighbour_search">Nearest neighbour search</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=7" title="Edit section: Nearest neighbour search"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><span><video id="mwe_player_0" poster="//upload.wikimedia.org/wikipedia/commons/thumb/4/48/Kdtreeogg.ogv/436px--Kdtreeogg.ogv.jpg" controls="" preload="none" data-mw-tmh="" class="mw-file-element" width="436" height="245" data-durationhint="134" data-mwtitle="Kdtreeogg.ogv" data-mwprovider="wikimediacommons" resource="/wiki/File:Kdtreeogg.ogv"><source src="//upload.wikimedia.org/wikipedia/commons/transcoded/4/48/Kdtreeogg.ogv/Kdtreeogg.ogv.480p.vp9.webm" type="video/webm; codecs="vp9, opus"" data-transcodekey="480p.vp9.webm" data-width="854" data-height="480" /><source src="//upload.wikimedia.org/wikipedia/commons/4/48/Kdtreeogg.ogv" type="video/ogg; codecs="theora"" data-width="1920" data-height="1080" /><source src="//upload.wikimedia.org/wikipedia/commons/transcoded/4/48/Kdtreeogg.ogv/Kdtreeogg.ogv.144p.mjpeg.mov" type="video/quicktime" data-transcodekey="144p.mjpeg.mov" data-width="256" data-height="144" /><source src="//upload.wikimedia.org/wikipedia/commons/transcoded/4/48/Kdtreeogg.ogv/Kdtreeogg.ogv.240p.vp9.webm" type="video/webm; codecs="vp9, opus"" data-transcodekey="240p.vp9.webm" data-width="426" data-height="240" /><source src="//upload.wikimedia.org/wikipedia/commons/transcoded/4/48/Kdtreeogg.ogv/Kdtreeogg.ogv.360p.webm" type="video/webm; codecs="vp8, vorbis"" data-transcodekey="360p.webm" data-width="640" data-height="360" /><source src="//upload.wikimedia.org/wikipedia/commons/transcoded/4/48/Kdtreeogg.ogv/Kdtreeogg.ogv.360p.vp9.webm" type="video/webm; codecs="vp9, opus"" data-transcodekey="360p.vp9.webm" data-width="640" data-height="360" /></video></span><figcaption>Example of a nearest neighbor search in a 2-d tree. Here, the tree is already built, each node corresponds to a rectangle, each rectangle is split in two equal subrectangles, and leaves correspond to rectangles containing a single point</figcaption></figure> <p>The <a href="/wiki/Nearest_neighbour_search" class="mw-redirect" title="Nearest neighbour search">nearest neighbour search</a> (NN) algorithm aims to find the point in the tree that is nearest to a given input point. This search can be done efficiently by using the tree properties to quickly eliminate large portions of the search space. </p><p>Searching for a nearest neighbour in a <i>k</i>-d tree proceeds as follows: </p> <ol><li>Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes left or right depending on whether the point is lesser than or greater than the current node in the split dimension).</li> <li>Once the algorithm reaches a leaf node, it checks the node point and if the distance is better than the "current best", that node point is saved as the "current best".</li> <li>The algorithm unwinds the recursion of the tree, performing the following steps at each node: <ol><li>If the current node is closer than the current best, then it becomes the current best.</li> <li>The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting <a href="/wiki/Hyperplane" title="Hyperplane">hyperplane</a> with a <a href="/wiki/Hypersphere" class="mw-redirect" title="Hypersphere">hypersphere</a> around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the distance between the splitting coordinate of the search point and current node is less than the distance (overall coordinates) from the search point to the current best. <ol><li>If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search.</li> <li>If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.</li></ol></li></ol></li> <li>When the algorithm finishes this process for the root node, then the search is complete.</li></ol> <p>Generally the algorithm uses squared distances for comparison to avoid computing square roots. Additionally, it can save computation by holding the squared current best distance in a variable for comparison. </p><p>The algorithm can be extended in several ways by simple modifications. It can provide the <i>k</i> nearest neighbours to a point by maintaining <i>k</i> current bests instead of just one. A branch is only eliminated when <i>k</i> points have been found and the branch cannot have points closer than any of the <i>k</i> current bests. </p><p>It can also be converted to an approximation algorithm to run faster. For example, approximate nearest neighbour searching can be achieved by simply setting an upper bound on the number of points to examine in the tree or by interrupting the search process based upon a real time clock (which may be more appropriate in hardware implementations). The nearest neighbour for points that are already in the tree can be achieved by not updating the refinement for nodes that give zero distance. As a result, this has the downside of discarding points that are not unique but are co-located with the original search point. </p><p>Approximate nearest neighbour is useful in real-time applications such as robotics due to the significant speed increase gained by not searching for the best point exhaustively. One of its implementations is <a href="/wiki/Best-bin-first_search" class="mw-redirect" title="Best-bin-first search">best-bin-first search</a>. </p> <div class="mw-heading mw-heading3"><h3 id="Range_search">Range search</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=8" title="Edit section: Range search"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Range_searching" title="Range searching">Range searching</a></div> <p>A range search searches for ranges of parameters. For example, if a tree is storing values corresponding to income and age, then a range search might be something like looking for all members of the tree which have an age between 20 and 50 years and an income between 50,000 and 80,000. Since k-d trees divide the range of a domain in half at each level of the tree, they are useful for performing range searches. </p><p>Analyses of binary search trees has found that the worst case time for range search in a <i>k</i>-dimensional <i>k</i>-d tree containing <i>n</i> nodes is given by the following equation.<sup id="cite_ref-Lee1977_13-0" class="reference"><a href="#cite_note-Lee1977-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <dl><dd><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_{\text{worst}}=O\left(k\cdot n^{1-{\frac {1}{k}}}\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>t</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>worst</mtext> </mrow> </msub> <mo>=</mo> <mi>O</mi> <mrow> <mo>(</mo> <mrow> <mi>k</mi> <mo>⋅</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mi>k</mi> </mfrac> </mrow> </mrow> </msup> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle t_{\text{worst}}=O\left(k\cdot n^{1-{\frac {1}{k}}}\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5cb5366f8bde88429fef45e5d88f4ceda1eaecda" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:21.842ex; height:6.176ex;" alt="{\displaystyle t_{\text{worst}}=O\left(k\cdot n^{1-{\frac {1}{k}}}\right)}" /></span></dd></dl> <div class="mw-heading mw-heading2"><h2 id="Degradation_in_performance_with_high-dimensional_data">Degradation in performance with high-dimensional data</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=9" title="Edit section: Degradation in performance with high-dimensional data"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Finding the nearest point is an <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> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> <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/7d3f404959a75e486669fd7618e00046eb00bb24" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.758ex; height:2.843ex;" alt="{\displaystyle O(\log(n))}" /></span> operation on average, in the case of randomly distributed points, although analysis in general is tricky.<sup id="cite_ref-Friedman:1977:AFB:355744.355745_14-0" class="reference"><a href="#cite_note-Friedman:1977:AFB:355744.355745-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> </p><p>In high-dimensional spaces, the <a href="/wiki/Curse_of_dimensionality" title="Curse of dimensionality">curse of dimensionality</a> causes the algorithm to need to visit many more branches than in lower-dimensional spaces. In particular, when the number of points is only slightly higher than the number of dimensions, the algorithm is only slightly better than a linear search of all of the points. As a general rule, if the dimensionality is <i>k</i>, the number of points in the data, <i>n</i>, should be <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\gg 2^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>≫</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\gg 2^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1e652c94520f07b638d2fb69e8ab01be2921bc5e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.26ex; height:2.676ex;" alt="{\displaystyle n\gg 2^{k}}" /></span>. Otherwise, when <i>k</i>-d trees are used with high-dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than exhaustive search,<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> and, if a good-enough fast answer is required, approximate nearest-neighbour methods should be used instead. </p> <div class="mw-heading mw-heading2"><h2 id="Degradation_in_performance_when_the_query_point_is_far_from_points_in_the_k-d_tree">Degradation in performance when the query point is far from points in the <i>k</i>-d tree</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=10" title="Edit section: Degradation in performance when the query point is far from points in the k-d tree"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Additionally, even in low-dimensional space, if the average pairwise distance between the <i>k</i> nearest neighbors of the query point is significantly less than the average distance between the query point and each of the <i>k</i> nearest neighbors, the performance of nearest neighbor search degrades towards linear, since the distances from the query point to each nearest neighbor are of similar magnitude. (In the worst case, consider a cloud of points distributed on the surface of a sphere centered at the origin. Every point is equidistant from the origin, so a search for the nearest neighbor from the origin would have to iterate through all points on the surface of the sphere to identify the nearest neighbor – which in this case is not even unique.) </p><p>To mitigate the potentially significant performance degradation of a <i>k</i>-d tree search in the worst case, a maximum distance parameter can be provided to the <a href="/wiki/Tree_search_algorithm" class="mw-redirect" title="Tree search algorithm">tree search algorithm</a>, and the recursive search can be pruned whenever the closest point in a given branch of the tree cannot be closer than this maximum distance. This may result in a nearest neighbor search failing to return a nearest neighbor, which means no points are within this maximum distance from the query point. </p> <div class="mw-heading mw-heading2"><h2 id="Complexity">Complexity</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=11" title="Edit section: Complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Building a static <i>k</i>-d tree from <i>n</i> points has the following worst-case complexity: <ul><li><a href="/wiki/Big_O_notation" title="Big O notation">O</a>(<i>n</i> log<sup>2</sup> <i>n</i>) if an <span class="nowrap"> <a href="/wiki/Big_O_notation" title="Big O notation">O</a>(<i>n</i> log <i>n</i>)</span> sort such as <a href="/wiki/Heapsort" title="Heapsort">Heapsort</a> or <a href="/wiki/Mergesort" class="mw-redirect" title="Mergesort">Mergesort</a> is used to find the median at each level of the nascent tree;</li> <li><a href="/wiki/Big_O_notation" title="Big O notation">O</a>(<i>n</i> log <i>n</i>) if an <span class="nowrap"> <a href="/wiki/Big_O_notation" title="Big O notation">O</a>(<i>n</i>)</span> <a href="/wiki/Median_of_medians" title="Median of medians">median of medians</a> algorithm<sup id="cite_ref-blum_5-1" class="reference"><a href="#cite_note-blum-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-cormen_6-1" class="reference"><a href="#cite_note-cormen-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> is used to select the median at each level of the nascent tree;</li> <li><a href="/wiki/Big_O_notation" title="Big O notation">O</a>(<i>kn</i> log <i>n</i>) if <i>n</i> points are presorted in each of <i>k</i> dimensions using an <span class="nowrap"> <a href="/wiki/Big_O_notation" title="Big O notation">O</a>(<i>n</i> log <i>n</i>)</span> sort such as <a href="/wiki/Heapsort" title="Heapsort">Heapsort</a> or <a href="/wiki/Mergesort" class="mw-redirect" title="Mergesort">Mergesort</a> prior to building the <span class="nowrap"><i>k</i>-d tree</span>.<sup id="cite_ref-knlogn_10-1" class="reference"><a href="#cite_note-knlogn-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup></li></ul></li> <li>Inserting a new point into a balanced <i>k</i>-d tree takes <span class="nowrap"> <a href="/wiki/Big_O_notation" title="Big O notation">O</a>(log <i>n</i>)</span> time.</li> <li>Removing a point from a balanced <i>k</i>-d tree takes <span class="nowrap"> <a href="/wiki/Big_O_notation" title="Big O notation">O</a>(log <i>n</i>)</span> time.</li> <li>Querying an axis-parallel range in a balanced <i>k</i>-d tree takes <span class="nowrap"> <a href="/wiki/Big_O_notation" title="Big O notation">O</a>(<i>n</i><sup>1−1/k</sup> +<i>m</i>)</span> time, where <i>m</i> is the number of the reported points, and <i>k</i> the dimension of the <i>k</i>-d tree.</li> <li>Finding 1 nearest neighbour in a balanced <i>k</i>-d tree with randomly distributed points takes <span class="nowrap"> <a href="/wiki/Big_O_notation" title="Big O notation">O</a>(log <i>n</i>)</span> time on average.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Variations">Variations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=12" title="Edit section: Variations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Volumetric_objects">Volumetric objects</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=13" title="Edit section: Volumetric objects"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Instead of points, a <i>k</i>-d tree can also contain <a href="/wiki/Rectangle" title="Rectangle">rectangles</a> or <a href="/wiki/Hyperrectangle" title="Hyperrectangle">hyperrectangles</a>.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> Thus range search becomes the problem of returning all rectangles intersecting the search rectangle. The tree is constructed the usual way with all the rectangles at the leaves. In an <a href="/wiki/Orthogonal_range_searching" class="mw-redirect" title="Orthogonal range searching">orthogonal range search</a>, the <i>opposite</i> coordinate is used when comparing against the median. For example, if the current level is split along x<sub>high</sub>, we check the x<sub>low</sub> coordinate of the search rectangle. If the median is less than the x<sub>low</sub> coordinate of the search rectangle, then no rectangle in the left branch can ever intersect with the search rectangle and so can be pruned. Otherwise both branches should be traversed. See also <a href="/wiki/Interval_tree" title="Interval tree">interval tree</a>, which is a 1-dimensional special case. </p> <div class="mw-heading mw-heading3"><h3 id="Points_only_in_leaves">Points only in leaves</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=14" title="Edit section: Points only in leaves"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>It is also possible to define a <i>k</i>-d tree with points stored solely in leaves.<sup id="cite_ref-compgeom_4-1" class="reference"><a href="#cite_note-compgeom-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> This form of <i>k</i>-d tree allows a variety of split mechanics other than the standard median split. The midpoint splitting rule<sup id="cite_ref-midpointsplit_18-0" class="reference"><a href="#cite_note-midpointsplit-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> selects on the middle of the longest axis of the space being searched, regardless of the distribution of points. This guarantees that the aspect ratio will be at most 2:1, but the depth is dependent on the distribution of points. A variation, called sliding-midpoint, only splits on the middle if there are points on both sides of the split. Otherwise, it splits on point nearest to the middle. Maneewongvatana and Mount show that this offers "good enough" performance on common data sets. </p><p>Using sliding-midpoint, an <a href="/wiki/Nearest_neighbour_search#Approximate_nearest_neighbour" class="mw-redirect" title="Nearest neighbour search">approximate nearest neighbour</a> query can be answered 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\left({\tfrac {1}{{\epsilon \ }^{d}}}\log n\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <msup> <mrow class="MJX-TeXAtom-ORD"> <mi>ϵ</mi> <mtext> </mtext> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> </msup> </mfrac> </mstyle> </mrow> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O\left({\tfrac {1}{{\epsilon \ }^{d}}}\log n\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/698954e46c80b94963996d5fd72079f512b072b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:13.023ex; height:4.843ex;" alt="{\displaystyle O\left({\tfrac {1}{{\epsilon \ }^{d}}}\log n\right)}" /></span>. Approximate range counting can be answered 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\left(\log n+{\left({\tfrac {1}{\epsilon \ }}\right)}^{d}\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mrow> <mo>(</mo> <mrow> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo>+</mo> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>1</mn> <mrow> <mi>ϵ</mi> <mtext> </mtext> </mrow> </mfrac> </mstyle> </mrow> <mo>)</mo> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>d</mi> </mrow> </msup> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O\left(\log n+{\left({\tfrac {1}{\epsilon \ }}\right)}^{d}\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2a5f6a94286199e291bccf319fdbe61fbdca0cb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:17.836ex; height:4.843ex;" alt="{\displaystyle O\left(\log n+{\left({\tfrac {1}{\epsilon \ }}\right)}^{d}\right)}" /></span> with this method. </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=K-d_tree&action=edit&section=15" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Close variations: </p> <ul><li><a href="/wiki/Implicit_kd-tree" class="mw-redirect" title="Implicit kd-tree">implicit <i>k</i>-d tree</a>, a <i>k</i>-d tree defined by an implicit splitting function rather than an explicitly-stored set of splits</li> <li><a href="/wiki/Min/max_kd-tree" title="Min/max kd-tree">min/max <i>k</i>-d tree</a>, a <i>k</i>-d tree that associates a minimum and maximum value with each of its nodes</li> <li><a href="/wiki/Relaxed_k-d_tree" title="Relaxed k-d tree">Relaxed <i>k</i>-d tree</a>, a <i>k</i>-d tree such that the discriminants in each node are arbitrary</li></ul> <p>Related variations: </p> <ul><li><a href="/wiki/Quadtree" title="Quadtree">Quadtree</a>, a space-partitioning structure that splits in two dimensions simultaneously, so that each node has 4 children</li> <li><a href="/wiki/Octree" title="Octree">Octree</a>, a space-partitioning structure that splits in three dimensions simultaneously, so that each node has 8 children</li> <li><a href="/wiki/Ball_tree" title="Ball tree">Ball tree</a>, a multi-dimensional space partitioning useful for nearest neighbor search</li> <li><a href="/wiki/R-tree" title="R-tree">R-tree</a> and <a href="/wiki/Bounding_interval_hierarchy" title="Bounding interval hierarchy">bounding interval hierarchy</a>, structure for partitioning objects rather than points, with overlapping regions</li> <li><a href="/wiki/Vantage-point_tree" title="Vantage-point tree">Vantage-point tree</a>, a variant of a <i>k</i>-d tree that uses hyperspheres instead of hyperplanes to partition the data</li></ul> <p>Problems that can be addressed with <i>k</i>-d trees: </p> <ul><li><a href="/wiki/Recursive_partitioning" title="Recursive partitioning">Recursive partitioning</a>, a technique for constructing statistical decision trees that are similar to <i>k</i>-d trees</li> <li><a href="/wiki/Klee%27s_measure_problem" title="Klee's measure problem">Klee's measure problem</a>, a problem of computing the area of a union of rectangles, solvable using <i>k</i>-d trees</li> <li><a href="/wiki/Guillotine_problem" class="mw-redirect" title="Guillotine problem">Guillotine problem</a>, a problem of finding a <i>k</i>-d tree whose cells are large enough to contain a given set of rectangles</li></ul> <div class="mw-heading mw-heading2"><h2 id="Open_source_implementations">Open source implementations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=K-d_tree&action=edit&section=16" title="Edit section: Open source implementations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/ALGLIB" title="ALGLIB">ALGLIB</a> has <a href="/wiki/C_Sharp_(programming_language)" title="C Sharp (programming language)">C#</a> and <a href="/wiki/C%2B%2B" title="C++">C++</a> implementations of <i>k</i>-d tree based nearest neighbor and approximate nearest neighbor algorithms</li> <li><a href="/wiki/CGAL" title="CGAL">CGAL</a> the Computational Algorithms Library, has an implementations of <i>k</i>-d tree based nearest neighbor, approximate nearest neighbor as well as range search algorithms.</li> <li><a href="/wiki/SciPy" title="SciPy">SciPy</a>, a <a href="/wiki/Python_(programming_language)" title="Python (programming language)">Python</a> library for scientific computing, contains implementations of <i>k</i>-d tree based nearest neighbor lookup algorithms.</li> <li><a href="/wiki/Scikit-learn" title="Scikit-learn">scikit-learn</a>, a Python library for machine learning, contains implementations of <i>k</i>-d trees to back nearest neighbor and radius neighbors searches.</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=K-d_tree&action=edit&section=17" 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 mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</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 class="citation web cs1"><a rel="nofollow" class="external text" href="https://xlinux.nist.gov/dads/HTML/kdimensional.html#:~:text=Definition:%20(1)%20Dealing%20with,-dimensional,%20three-dimensional.">"k-dimensional"</a>. <i>xlinux.nist.gov</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2023-09-17</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=xlinux.nist.gov&rft.atitle=k-dimensional&rft_id=https%3A%2F%2Fxlinux.nist.gov%2Fdads%2FHTML%2Fkdimensional.html%23%3A~%3Atext%3DDefinition%3A%2520%281%29%2520Dealing%2520with%2C-dimensional%2C%2520three-dimensional.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHristov2023" class="citation web cs1">Hristov, Hristo (March 29, 2023). <a rel="nofollow" class="external text" href="https://www.baeldung.com/cs/k-d-trees">"Introduction to K-D Trees"</a>. <i>Baeldung</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Baeldung&rft.atitle=Introduction+to+K-D+Trees&rft.date=2023-03-29&rft.aulast=Hristov&rft.aufirst=Hristo&rft_id=https%3A%2F%2Fwww.baeldung.com%2Fcs%2Fk-d-trees&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></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="CITEREFBentley1975" class="citation journal cs1"><a href="/wiki/Jon_Bentley_(computer_scientist)" title="Jon Bentley (computer scientist)">Bentley, J. L.</a> (1975). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F361002.361007">"Multidimensional binary search trees used for associative searching"</a>. <i><a href="/wiki/Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a></i>. <b>18</b> (9): <span class="nowrap">509–</span>517. <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%2F361002.361007">10.1145/361002.361007</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:13091446">13091446</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Communications+of+the+ACM&rft.atitle=Multidimensional+binary+search+trees+used+for+associative+searching&rft.volume=18&rft.issue=9&rft.pages=%3Cspan+class%3D%22nowrap%22%3E509-%3C%2Fspan%3E517&rft.date=1975&rft_id=info%3Adoi%2F10.1145%2F361002.361007&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A13091446%23id-name%3DS2CID&rft.aulast=Bentley&rft.aufirst=J.+L.&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F361002.361007&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-compgeom-4"><span class="mw-cite-backlink">^ <a href="#cite_ref-compgeom_4-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-compgeom_4-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBergCheongKreveldOvermars2008" class="citation book cs1">Berg, Mark de; Cheong, Otfried; Kreveld, Marc van; Overmars, Mark (2008). "Orthogonal Range Searching". <i>Computational Geometry</i>. pp. <span class="nowrap">95–</span>120. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-77974-2_5">10.1007/978-3-540-77974-2_5</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-77973-5" title="Special:BookSources/978-3-540-77973-5"><bdi>978-3-540-77973-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Orthogonal+Range+Searching&rft.btitle=Computational+Geometry&rft.pages=%3Cspan+class%3D%22nowrap%22%3E95-%3C%2Fspan%3E120&rft.date=2008&rft_id=info%3Adoi%2F10.1007%2F978-3-540-77974-2_5&rft.isbn=978-3-540-77973-5&rft.aulast=Berg&rft.aufirst=Mark+de&rft.au=Cheong%2C+Otfried&rft.au=Kreveld%2C+Marc+van&rft.au=Overmars%2C+Mark&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-blum-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-blum_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-blum_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBlumFloydPrattRivest1973" class="citation journal cs1"><a href="/wiki/Manuel_Blum" title="Manuel Blum">Blum, M.</a>; <a href="/wiki/Robert_W._Floyd" title="Robert W. Floyd">Floyd, R. W.</a>; <a href="/wiki/Vaughan_Pratt" title="Vaughan Pratt">Pratt, V. R.</a>; <a href="/wiki/Ron_Rivest" title="Ron Rivest">Rivest, R. L.</a>; <a href="/wiki/Robert_Tarjan" title="Robert Tarjan">Tarjan, R. E.</a> (August 1973). <a rel="nofollow" class="external text" href="http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf">"Time bounds for selection"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of Computer and System Sciences</i>. <b>7</b> (4): <span class="nowrap">448–</span>461. <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.1016%2FS0022-0000%2873%2980033-9">10.1016/S0022-0000(73)80033-9</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=Time+bounds+for+selection&rft.volume=7&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E448-%3C%2Fspan%3E461&rft.date=1973-08&rft_id=info%3Adoi%2F10.1016%2FS0022-0000%2873%2980033-9&rft.aulast=Blum&rft.aufirst=M.&rft.au=Floyd%2C+R.+W.&rft.au=Pratt%2C+V.+R.&rft.au=Rivest%2C+R.+L.&rft.au=Tarjan%2C+R.+E.&rft_id=http%3A%2F%2Fpeople.csail.mit.edu%2Frivest%2Fpubs%2FBFPRT73.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-cormen-6"><span class="mw-cite-backlink">^ <a href="#cite_ref-cormen_6-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-cormen_6-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFCormenLeisersonRivest" class="citation book cs1"><a href="/wiki/Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="/wiki/Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a> <a href="/wiki/Introduction_to_Algorithms" title="Introduction to Algorithms"><i>Introduction to Algorithms</i></a>. MIT Press and McGraw-Hill.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Algorithms&rft.pub=MIT+Press+and+McGraw-Hill&rft.aulast=Cormen&rft.aufirst=Thomas+H.&rft.au=Leiserson%2C+Charles+E.&rft.au=Rivest%2C+Ronald+L.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span> Chapter 10.</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="CITEREFWald_I,_Havran_V2006" class="citation book cs1">Wald I, Havran V (September 2006). <a rel="nofollow" class="external text" href="http://dcgi.felk.cvut.cz/home/havran/ARTICLES/ingo06rtKdtree.pdf">"On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)"</a> <span class="cs1-format">(PDF)</span>. <i>2006 IEEE Symposium on Interactive Ray Tracing</i>. pp. <span class="nowrap">61–</span>69. <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%2FRT.2006.280216">10.1109/RT.2006.280216</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/1-4244-0693-5" title="Special:BookSources/1-4244-0693-5"><bdi>1-4244-0693-5</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:1603250">1603250</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=On+building+fast+kd-Trees+for+Ray+Tracing%2C+and+on+doing+that+in+O%28N+log+N%29&rft.btitle=2006+IEEE+Symposium+on+Interactive+Ray+Tracing&rft.pages=%3Cspan+class%3D%22nowrap%22%3E61-%3C%2Fspan%3E69&rft.date=2006-09&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A1603250%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FRT.2006.280216&rft.isbn=1-4244-0693-5&rft.au=Wald+I%2C+Havran+V&rft_id=http%3A%2F%2Fdcgi.felk.cvut.cz%2Fhome%2Fhavran%2FARTICLES%2Fingo06rtKdtree.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHavran_V,_Bittner_J2002" class="citation journal cs1">Havran V, Bittner J (2002). <a rel="nofollow" class="external text" href="http://dcgi.felk.cvut.cz/home/bittner/publications/wscg02.pdf">"On improving k-d trees for ray shooting"</a> <span class="cs1-format">(PDF)</span>. <i>In: Proceedings of the WSCG</i>: <span class="nowrap">209–</span>216.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=In%3A+Proceedings+of+the+WSCG&rft.atitle=On+improving+k-d+trees+for+ray+shooting&rft.pages=%3Cspan+class%3D%22nowrap%22%3E209-%3C%2Fspan%3E216&rft.date=2002&rft.au=Havran+V%2C+Bittner+J&rft_id=http%3A%2F%2Fdcgi.felk.cvut.cz%2Fhome%2Fbittner%2Fpublications%2Fwscg02.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFProcopiucAgarwalArgeVittner2003" class="citation book cs1">Procopiuc, T; Agarwal, M; Arge, L; Vittner, J (2003). "Bkd-tree: A dynamic scalable kd-tree". In Hadzilacos, T; Manolopoulos, Y; Roddick, J; Theodoridis, Y (eds.). <i>Lecture Notes in Computer Science</i>. Vol. 2750. Berlin: Springer-Verlag. pp. <span class="nowrap">46–</span>65.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Bkd-tree%3A+A+dynamic+scalable+kd-tree&rft.btitle=Lecture+Notes+in+Computer+Science&rft.place=Berlin&rft.pages=%3Cspan+class%3D%22nowrap%22%3E46-%3C%2Fspan%3E65&rft.pub=Springer-Verlag&rft.date=2003&rft.aulast=Procopiuc&rft.aufirst=T&rft.au=Agarwal%2C+M&rft.au=Arge%2C+L&rft.au=Vittner%2C+J&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-knlogn-10"><span class="mw-cite-backlink">^ <a href="#cite_ref-knlogn_10-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-knlogn_10-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFBrown_R2015" class="citation journal cs1">Brown R (2015). <a rel="nofollow" class="external text" href="http://jcgt.org/published/0004/01/03/">"Building a balanced <i>k</i>-d tree in <span class="texhtml">O(<i>kn</i> log <i>n</i>)</span> time"</a>. <i>Journal of Computer Graphics Techniques</i>. <b>4</b> (1): <span class="nowrap">50–</span>68.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+Graphics+Techniques&rft.atitle=Building+a+balanced+k-d+tree+in+%3Cspan+class%3D%22texhtml+%22+%3EO%28kn+log+n%29%3C%2Fspan%3E+time&rft.volume=4&rft.issue=1&rft.pages=%3Cspan+class%3D%22nowrap%22%3E50-%3C%2Fspan%3E68&rft.date=2015&rft.au=Brown+R&rft_id=http%3A%2F%2Fjcgt.org%2Fpublished%2F0004%2F01%2F03%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHristov2023" class="citation web cs1">Hristov, Hristo (March 29, 2023). <a rel="nofollow" class="external text" href="https://www.baeldung.com/cs/k-d-trees">"Introduction to K-D Trees"</a>. <i>Baeldung</i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Baeldung&rft.atitle=Introduction+to+K-D+Trees&rft.date=2023-03-29&rft.aulast=Hristov&rft.aufirst=Hristo&rft_id=https%3A%2F%2Fwww.baeldung.com%2Fcs%2Fk-d-trees&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text">Chandran, Sharat. <a rel="nofollow" class="external text" href="http://www.cs.umd.edu/class/spring2002/cmsc420-0401/pbasic.pdf">Introduction to kd-trees</a>. University of Maryland Department of Computer Science.</span> </li> <li id="cite_note-Lee1977-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-Lee1977_13-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFLeeWong1977" class="citation journal cs1">Lee, D. T.; Wong, C. K. (1977). "Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees". <i>Acta Informatica</i>. <b>9</b>. <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%2FBF00263763">10.1007/BF00263763</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:36580055">36580055</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Informatica&rft.atitle=Worst-case+analysis+for+region+and+partial+region+searches+in+multidimensional+binary+search+trees+and+balanced+quad+trees&rft.volume=9&rft.date=1977&rft_id=info%3Adoi%2F10.1007%2FBF00263763&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A36580055%23id-name%3DS2CID&rft.aulast=Lee&rft.aufirst=D.+T.&rft.au=Wong%2C+C.+K.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-Friedman:1977:AFB:355744.355745-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-Friedman:1977:AFB:355744.355745_14-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFFreidmanBentleyFinkel1977" class="citation journal cs1"><a href="/wiki/Jerome_H._Friedman" title="Jerome H. Friedman">Freidman, J. H.</a>; <a href="/wiki/Jon_Bentley_(computer_scientist)" title="Jon Bentley (computer scientist)">Bentley, J. L.</a>; Finkel, R. A. (1977). "An Algorithm for Finding Best Matches in Logarithmic Expected Time". <i><a href="/wiki/ACM_Transactions_on_Mathematical_Software" title="ACM Transactions on Mathematical Software">ACM Transactions on Mathematical Software</a></i>. <b>3</b> (3): 209. <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%2F355744.355745">10.1145/355744.355745</a>. <a href="/wiki/OSTI_(identifier)" class="mw-redirect" title="OSTI (identifier)">OSTI</a> <a rel="nofollow" class="external text" href="https://www.osti.gov/biblio/1443274">1443274</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:10811510">10811510</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=ACM+Transactions+on+Mathematical+Software&rft.atitle=An+Algorithm+for+Finding+Best+Matches+in+Logarithmic+Expected+Time&rft.volume=3&rft.issue=3&rft.pages=209&rft.date=1977&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A10811510%23id-name%3DS2CID&rft_id=https%3A%2F%2Fwww.osti.gov%2Fbiblio%2F1443274%23id-name%3DOSTI&rft_id=info%3Adoi%2F10.1145%2F355744.355745&rft.aulast=Freidman&rft.aufirst=J.+H.&rft.au=Bentley%2C+J.+L.&rft.au=Finkel%2C+R.+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFJacob_E._Goodman,_Joseph_O'Rourke_and_Piotr_Indyk2004" class="citation book cs1"><a href="/wiki/Jacob_E._Goodman" title="Jacob E. Goodman">Jacob E. Goodman</a>, Joseph O'Rourke and <a href="/wiki/Piotr_Indyk" title="Piotr Indyk">Piotr Indyk</a>, ed. (2004). "Chapter 39: Nearest neighbours in high-dimensional spaces". <i>Handbook of Discrete and Computational Geometry</i> (2nd ed.). CRC Press.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Chapter+39%3A+Nearest+neighbours+in+high-dimensional+spaces&rft.btitle=Handbook+of+Discrete+and+Computational+Geometry&rft.edition=2nd&rft.pub=CRC+Press&rft.date=2004&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFRosenberg1985" class="citation journal cs1">Rosenberg, J. B. (1985). "Geographical Data Structures Compared: A Study of Data Structures Supporting Region Queries". <i>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems</i>. <b>4</b>: <span class="nowrap">53–</span>67. <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%2FTCAD.1985.1270098">10.1109/TCAD.1985.1270098</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:31223074">31223074</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Transactions+on+Computer-Aided+Design+of+Integrated+Circuits+and+Systems&rft.atitle=Geographical+Data+Structures+Compared%3A+A+Study+of+Data+Structures+Supporting+Region+Queries&rft.volume=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E53-%3C%2Fspan%3E67&rft.date=1985&rft_id=info%3Adoi%2F10.1109%2FTCAD.1985.1270098&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A31223074%23id-name%3DS2CID&rft.aulast=Rosenberg&rft.aufirst=J.+B.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFHouthuys1987" class="citation journal cs1">Houthuys, P. (1987). "Box Sort, a multidimensional binary sorting method for rectangular boxes, used for quick range searching". <i>The Visual Computer</i>. <b>3</b> (4): <span class="nowrap">236–</span>249. <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%2FBF01952830">10.1007/BF01952830</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:3197488">3197488</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Visual+Computer&rft.atitle=Box+Sort%2C+a+multidimensional+binary+sorting+method+for+rectangular+boxes%2C+used+for+quick+range+searching&rft.volume=3&rft.issue=4&rft.pages=%3Cspan+class%3D%22nowrap%22%3E236-%3C%2Fspan%3E249&rft.date=1987&rft_id=info%3Adoi%2F10.1007%2FBF01952830&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A3197488%23id-name%3DS2CID&rft.aulast=Houthuys&rft.aufirst=P.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AK-d+tree" class="Z3988"></span></span> </li> <li id="cite_note-midpointsplit-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-midpointsplit_18-0">^</a></b></span> <span class="reference-text">S. Maneewongvatana and <a href="/wiki/David_Mount" title="David Mount">D. M. Mount</a>. <a rel="nofollow" class="external text" href="https://graphics.stanford.edu/courses/cs164-09-spring/Handouts/paper_mount_cgc99-smpack.pdf">It's okay to be skinny, if your friends are fat</a>. 4th Annual CGC Workshop on Computational Geometry, 1999.</span> </li> </ol></div></div> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Tree_data_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" /><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:CS_trees" title="Template:CS trees"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:CS_trees" title="Template talk:CS trees"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:CS_trees" title="Special:EditPage/Template:CS trees"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Tree_data_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 href="/wiki/Treap" title="Treap">Treap</a></li> <li><a href="/wiki/UB-tree" title="UB-tree">UB</a></li> <li><a href="/wiki/Weight-balanced_tree" title="Weight-balanced tree">Weight-balanced</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heaps</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary</a></li> <li><a href="/wiki/Binomial_heap" title="Binomial heap">Binomial</a></li> <li><a href="/wiki/Brodal_queue" title="Brodal queue">Brodal</a></li> <li><a href="/wiki/D-ary_heap" title="D-ary heap"><i>d</i>-ary</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci</a></li> <li><a href="/wiki/Leftist_tree" title="Leftist tree">Leftist</a></li> <li><a href="/wiki/Pairing_heap" title="Pairing heap">Pairing</a></li> <li><a href="/wiki/Skew_binomial_heap" title="Skew binomial heap">Skew binomial</a></li> <li><a href="/wiki/Skew_heap" title="Skew heap">Skew</a></li> <li><a href="/wiki/Van_Emde_Boas_tree" title="Van Emde Boas tree">van Emde Boas</a></li> <li><a href="/wiki/Weak_heap" title="Weak heap">Weak</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a 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 class="mw-selflink selflink"><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://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" 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=K-d_tree&oldid=1251096500">https://en.wikipedia.org/w/index.php?title=K-d_tree&oldid=1251096500</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:Computer_graphics_data_structures" title="Category:Computer graphics data structures">Computer graphics data structures</a></li><li><a href="/wiki/Category:Trees_(data_structures)" title="Category:Trees (data structures)">Trees (data structures)</a></li><li><a href="/wiki/Category:Geometric_data_structures" title="Category:Geometric data structures">Geometric data structures</a></li><li><a href="/wiki/Category:Database_index_techniques" title="Category:Database index techniques">Database index techniques</a></li><li><a href="/wiki/Category:Data_types" title="Category:Data types">Data types</a></li><li><a href="/wiki/Category:Rectangular_subdivisions" title="Category:Rectangular subdivisions">Rectangular subdivisions</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Commons_category_link_is_locally_defined" title="Category:Commons category link is locally defined">Commons category link is locally defined</a></li><li><a href="/wiki/Category:Articles_to_be_expanded_from_November_2008" title="Category:Articles to be expanded from November 2008">Articles to be expanded from November 2008</a></li><li><a href="/wiki/Category:All_articles_to_be_expanded" title="Category:All articles to be expanded">All articles to be expanded</a></li><li><a href="/wiki/Category:Articles_to_be_expanded_from_February_2011" title="Category:Articles to be expanded from February 2011">Articles to be expanded from February 2011</a></li><li><a href="/wiki/Category:Articles_with_example_Python_(programming_language)_code" title="Category:Articles with example Python (programming language) code">Articles with example Python (programming language) code</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 14 October 2024, at 11:20<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=K-d_tree&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><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" ><i>k</i>-d tree</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>14 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.eqiad.main-8669bc5c8-95k5q","wgBackendResponseTime":199,"wgPageParseReport":{"limitreport":{"cputime":"0.575","walltime":"0.904","ppvisitednodes":{"value":2156,"limit":1000000},"postexpandincludesize":{"value":65111,"limit":2097152},"templateargumentsize":{"value":2311,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":4,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":77384,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 656.166 1 -total"," 32.27% 211.727 1 Template:Reflist"," 16.61% 109.003 1 Template:Short_description"," 16.02% 105.147 3 Template:Cite_web"," 14.59% 95.711 1 Template:CS-Trees"," 13.96% 91.588 1 Template:Navbox"," 12.01% 78.799 2 Template:Expand_section"," 11.17% 73.318 2 Template:Ambox"," 10.72% 70.359 1 Template:Commonscat"," 10.15% 66.590 1 Template:Sister_project"]},"scribunto":{"limitreport-timeusage":{"value":"0.345","limit":"10.000"},"limitreport-memusage":{"value":7531748,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-8669bc5c8-f69xj","timestamp":"20250318155706","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"K-d tree","url":"https:\/\/en.wikipedia.org\/wiki\/K-d_tree","sameAs":"http:\/\/www.wikidata.org\/entity\/Q309949","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q309949","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":"2005-04-01T01:13:39Z","dateModified":"2024-10-14T11:20:09Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/b\/b6\/3dtree.png","headline":"multidimensional search tree for points in k dimensional space"}</script> </body> </html>