Optimal Binary Search Trees with Near Minimal Height

Details Optimal Binary Search Trees with Near Minimal Height Optimal Binary Search Trees with Near Minimal Height

2010-11-05

arxiv.org/abs/1011.1337v1

Computer Science

Data Structures and Algorithms

Scientific paper

Suppose we have n keys, n access probabilities for the keys, and n+1 access probabilities for the gaps between the keys. Let h_min(n) be the minimal height of a binary search tree for n keys. We consider the problem to construct an optimal binary search tree with near minimal height, i.e.\ with height h <= h_min(n) + Delta for some fixed Delta. It is shown, that for any fixed Delta optimal binary search trees with near minimal height can be constructed in time O(n^2). This is as fast as in the unrestricted case. So far, the best known algorithms for the construction of height-restricted optimal binary search trees have running time O(L n^2), whereby L is the maximal permitted height. Compared to these algorithms our algorithm is at least faster by a factor of log n, because L is lower bounded by log n.

Affiliated with

Also associated with

No associations

Rating

Optimal Binary Search Trees with Near Minimal Height does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Binary Search Trees with Near Minimal Height, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Binary Search Trees with Near Minimal Height will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-453794