| 词条 | Priority search tree |
| 释义 |
In computer science, a priority search tree is a tree data structure for storing points in two dimensions. It was originally introduced by Edward McCreight.[1] It is effectively an extension of the priority queue with the purpose of improving the search time from O(n) to O(s + log n) time, where n is the number of points in the tree and s is the number of points returned by the search. DescriptionThe priority search tree is used to store a set of 2-dimensional points ordered by priority and by a key value. This is accomplished by creating a hybrid a priority queue and a binary search tree. The result is a tree where each nodes represent a point in the original dataset. The point contained by the node is the one with the lowest priority. In addition, each node also contains a key value used to divide the remaining points (usually the median of the keys, excluding the point of the node) into a left and right subtree. The points are divided by comparing their key values to the node key, delegating the ones with lower keys to the left subtree, and the ones strictly greater to the right subtree.[2] OperationsConstructionThe construction of the tree requires O(n log n) time and O(n) space. A proposed construction algorithm is proposed below: tree construct_tree(data) { if length(data) > 1 { node_point = find_point_with_minimum_priority(data) // Select the point with the lowest priority reduced_data = remove_point_from_data(data, node_point) node_key = calculate_median(reduced_data) // calculate median, excluding the selected point // Divide the points left_data = [] right_data = [] for (point in reduced_data) { if point.key <= node_key left_data.append(point) else right_data.append(point) }left_subtree = construct_tree(left_data) right_subtree = construct_tree(right_data) } else if length(data) == 1 { return leaf node // Leaf node containing the single remaining data point } else if length(data) == 0 { return null // This node is empty }} Grounded range searchThe priority search tree can be efficiently queried for a key in a closed interval and for a maximum priority value. That is, one can specify an interval [min_key, max_key] and another interval [-{{math|∞|size=100%}}, max_priority] and return the points contained within it. This is illustrated in the following pseudo code: points search_tree(tree, min_key, max_key, max_priority) { root = get_root_node(tree) result = [] if get_child_count(root) > 0 { if get_point_priority(root) > max_priority return null // Nothing interesting will exist in this branch. Returnif min_key <= get_point_key(root) <= max_key // is the root point one of interest? result.append(get_point(node)) if min_key < get_node_key(root) // Should we search left subtree? result.append(search_tree(root.left_sub_tree, min_key, max_key, max_priority)) if get_node_key(root) < max_key // Should we search right subtree? result.append(search_tree(root.right_sub_tree, min_key, max_key, max_priority)) return result else { // This is a leaf node if get_point_priority(root) < max_priority and min_key <= get_point_key(root) <= max_key // is leaf point of interest? result.append(get_point(node)) }} See also
References1. ^{{cite journal|last1=McCreight|first1=Edward|title="Priority search trees"|journal=SIAM Journal on Scientific Computing|date=May 1985|volume=14|issue=2|page=257-276}} 2. ^{{cite book|last1=Lee|first1=D.T|title=Handbook of Data Structures and Applications|date=2005|publisher=Chapman & Hall/CRC|location=London|isbn=1-58488-435-5|pages=18-21}} 2 : Trees (data structures)|Geometric data structures |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。