# Tree/LogN Min Search

### From charlesreid1

## Contents

# Skeina, The Algorithm Design Manual, Chapter 3

## Problem 3-11

**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.

### Part a

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.

### Part b

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.

Algorithm:

- 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

# Flags

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
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 OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |