翻訳と辞書 Words near each other ・ Range Rover (L405) ・ Range Rover (P38A) ・ Range Rover Classic ・ Range Rover Evoque ・ Range Rover Sport ・ Range Ryder and the Calgary Kid ・ Range safety ・ Range Safety and Telemetry System ・ Range searching ・ Range segmentation ・ Range Software ・ Range space ・ Range state ・ Range table ・ Range Township, Madison County, Ohio ・ Range tree ・ Range voting ・ Range War ・ Range war ・ Range War (Hell on Wheels) ・ Range Warfare ・ Range, Alabama ・ Range, Ohio ・ Range, Wisconsin ・ Range-Frequency Theory ・ Range-R ・ Rangea ・ Rangeban, Cotabato ・ Rangecourt ・ Ranged weapon Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Range tree ： ウィキペディア英語版 Range tree In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently, and is typically used in two or higher dimensions. Range trees were introduced by Jon Louis Bentley in 1979. Similar data structures were discovered independently by Lueker, Lee and Wong, and Willard. The range tree is an alternative to the ''k''-d tree. Compared to ''k''-d trees, range trees offer faster query times of (in Big O notation) $O(\backslash log^dn+k)$ but worse storage of $O(n\backslash log^\; n)$, where ''n'' is the number of points stored in the tree, ''d'' is the dimension of each point and ''k'' is the number of points reported by a given query. Bernard Chazelle improved this to query time $O(\backslash log^\; n\; +\; k)$ and space complexity $O\backslash left(n\backslash left(\backslash frac\backslash right)^\backslash right)$. == Description == A range tree on a set of 1-dimensional points is a balanced binary search tree on those points. The points stored in the tree are stored in the leaves of the tree; each internal node stores the largest value contained in its left subtree. A range tree on a set of points in ''d''-dimensions is a recursively defined multi-level binary search tree. Each level of the data structure is a binary search tree on one of the ''d''-dimensions. The first level is a binary search tree on the first of the ''d''-coordinates. Each vertex ''v'' of this tree contains an associated structure that is a (''d''−1)-dimensional range tree on the last (''d''−1)-coordinates of the points stored in the subtree of ''v''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Range tree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.