Priority search tree

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer science, a priority search tree is a tree data structure for storing points in two dimensions. It was originally introduced by Edward M. McCreight. 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.

In computer science, a priority search tree is a tree data structure for storing points in two dimensions. It was originally introduced by Edward M. McCreight. 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. 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 However, if the points are sorted by their key values then the tree can be constructed in linear time. This can easily be done by constructing a balanced binary tree over the key values (as leaves) in linear time. Each internal node stores a pointer to the lowest priority node and count of number of items in the subtree rooted at that node. Thus, the node with minimum priority can be identified in constant time. The median of remaining points and the item with next smallest priority can be identified in O(log n) time. Thus, the recurrence relation is T(n)=2T(n/2)+O(log n)=O(n). 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. Return if min_key

Text derived from https://en.wikipedia.org/w/index.php?oldid=1351903062 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001351903062 · captured 1777575798.0 · version history

Cite this page as: encyclopegia.org, “Priority search tree”, snapshot enwiki-001351903062. https://encyclopegia.org/a/priority-search-tree

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.