| 词条 | Relaxed k-d tree |
| 释义 |
|name= Relaxed k-d tree |type= Multidimensional BST |invented_by= Amalia Duch, Vladimir Estivill-Castro and Conrado Martínez |invented_year= 1998 |space_avg= O(n) |space_worst= O(n) |search_avg= O(log n) |search_worst= O(n) |insert_avg= O(log n) |insert_worst= O(n) |delete_avg= O(log n) |delete_worst= O(n) }} A relaxed K-d tree or relaxed K-dimensional tree is a data structure which is a variant of K-d trees. Like K-dimensional trees, a relaxed K-dimensional tree stores a set of n-multidimensional records, each one having a unique K-dimensional key x=(x0,... ,xK−1). Unlike K-d trees, in a relaxed K-d tree, the discriminants in each node are arbitrary. Relaxed K-d trees were introduced in 1998.[1] DefinitionsA relaxed K-d tree for a set of K-dimensional keys is a binary tree in which:
If K = 1, a relaxed K-d tree is a binary search tree. As in a K-d tree, a relaxed K-d tree of size n induces a partition of the domain D into n+1 regions, each corresponding to a leaf in the K-d tree. The bounding box (or bounds array) of a node {x,j} is the region of the space delimited by the leaf in which x falls when it is inserted into the tree. Thus, the bounding box of the root {y,i} is [0,1]K, the bounding box of the left subtree's root is [0,1] × ... × [0,yi] × ... × [0,1], and so on. Supported queriesThe average time complexities in a relaxed K-d tree with n records are:
See also
References1. ^{{Cite book|title=Randomized K-Dimensional Binary Search Trees|last=Duch|first=Amalia|last2=Estivill-Castro|first2=Vladimir|last3=Martínez|first3=Conrado|date=1998-12-14|publisher=Springer Berlin Heidelberg|isbn=9783540653851|editor-last=Chwa|editor-first=Kyung-Yong|series=Lecture Notes in Computer Science|pages=198–209|language=en|doi=10.1007/3-540-49381-6_22|editor-last2=Ibarra|editor-first2=Oscar H.|citeseerx = 10.1.1.55.3293}} 2. ^{{cite journal|last1=Duch|first1=Amalia|last2=Martínez|first2=Conrado|title=Improving the Performance of Multidimensional Search Using Fingers|journal=ACM Journal of Experimental Algorithms|date=2005|volume=10|url=http://www.cs.upc.edu/~conrado/research/papers/jea-dm05.pdf|accessdate=23 August 2016}} 3. ^{{cite book|last1=Chwa|first1=Kyung-Yong|last2=Ibarra|first2=Oscar H.|title=Algorithms and Computation: 9th International Symposium, ISAAC'98, Taejon, Korea, December 14-16, 1998, Proceedings|publisher=Springer|isbn=9783540493815|pages=202–203|url=https://books.google.com/?id=MhNqCQAAQBAJ&pg=PA202&lpg=PA202&dq=Relaxed+k-d+tree+exact+match+queries#v=onepage&q=Relaxed%20k-d%20tree%20exact%20match%20queries&f=false|accessdate=23 August 2016|language=en|date=2003-06-29}} 1 : Trees (data structures) |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。