Tree/LogN Min Search
Skeina, The Algorithm Design Manual, Chapter 3
Problem 3-11: Suppose we're given a sequence of values x1, x2, ..., xn and we seek to quickly answer questions of the form: given i, given j, find the samllest value in xi, ..., xj.
Part a - design a data structure using space, answering queries in time.
Part b - design a data structure using space, time.
For part a = use a hash table. We pass it every combination of (i,j) and save the minimum value as a value. Use space, time.
I puzzled over part b fora long while.
The Algorist wiki (link) gives one possible solution, that's a bit tricky. Even the solution takes some puzzling over.)
Implement a binary tree, where each tree node represents a particular range of indices. The higher in the tree a node is, the larger the range of indices it covers.
The root node spans the whole input sequence. The root node's children span the left and right halves of the input sequence. Etc.
Each leaf spans a single element range of input, meaning there are log(N) levels to the tree (where N is the number of indices in the array).
The lowest value in the range is the value at that position in the input sequence.
Total O(N) nodes in tree.
- Query function is recursive, and passes the query (which has a low and high value), starting from the root
- If the query range matches the current node's range, return the current node's value
- If the query range is entirely within the left/right hand side (query.low > node.low && query.high < node.high), return the result of calling query on left/right hand node
- Otherwise return lowest results from calling query on LH and on RH (minimum of two, only checking query.low > node.low or query.high < node.high)
- Query visits maximum of 2 leaf nodes
TreesPart of Computer Science Notes
Series on Data Structures
Abstract data type: Trees/ADT
Preorder traversal: Trees/Preorder
Postorder traversal: Trees/Postorder
In-Order traversal: Binary Trees/Inorder
Breadth-First Search: BFS
Breadth-First Traversal: BFT
Depth-First Search: DFS
Depth-First Traversal: DFT
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT
Flags · Template:TreesFlagBase · e