opBinTree.H File Reference

Optimal Binary Search Tree construction using dynamic programming. More...

#include <limits>
#include <tpl_dynArray.H>

Include dependency graph for opBinTree.H:

Go to the source code of this file.

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Macros
#define	COST(i, j)   (cost[(i)*(n+1) + (j)])
#define	TREE(i, j)   (tree[(i)*(n+1) + (j)])

Functions
static void	Aleph::compute_optimal_costs (DynArray< double > &cost, double p[], const size_t n, DynArray< int > &tree)
	Compute optimal costs and tree structure using dynamic programming.
template<class Node , typename Key >
static Node *	Aleph::compute_tree (Key keys[], DynArray< int > &tree, const size_t n, const size_t i, const size_t j)
	Recursively construct the optimal BST from the tree matrix.
template<class Node , typename Key >
Node *	Aleph::build_optimal_tree (Key keys[], double p[], const size_t n)
	Build an optimal binary search tree based on access probabilities.

Detailed Description

Optimal Binary Search Tree construction using dynamic programming.

This module implements the dynamic programming algorithm for constructing an optimal binary search tree given keys and their access probabilities. The algorithm minimizes the expected search cost.

Uses two optimizations:

• Prefix sums: O(1) range sum queries instead of O(n)
• Knuth's optimization: Reduces search space using monotonicity of optimal roots

Time complexity: O(n²) (with Knuth's optimization) Space complexity: O(n²)

See also

Knuth, D.E. "Optimum Binary Search Trees" Acta Informatica 1 (1971)

Author

Leandro Rabindranath León

Definition in file opBinTree.H.

Macro Definition Documentation

COST

#define COST	(		i,
			j
	)		(cost[(i)*(n+1) + (j)])

Definition at line 61 of file opBinTree.H.

TREE

#define TREE	(		i,
			j
	)		(tree[(i)*(n+1) + (j)])

Definition at line 62 of file opBinTree.H.