De-amortizing Binary Search Trees

Details De-amortizing Binary Search Trees De-amortizing Binary Search Trees

2011-11-07

arxiv.org/abs/1111.1665v1

Computer Science

Data Structures and Algorithms

Scientific paper

We present a general method for de-amortizing essentially any Binary Search Tree (BST) algorithm. In particular, by transforming Splay Trees, our method produces a BST that has the same asymptotic cost as Splay Trees on any access sequence while performing each search in O(log n) worst case time. By transforming Multi-Splay Trees, we obtain a BST that is O(log log n) competitive, satisfies the scanning theorem, the static optimality theorem, the static finger theorem, the working set theorem, and performs each search in O(log n) worst case time. Moreover, we prove that if there is a dynamically optimal BST algorithm, then there is a dynamically optimal BST algorithm that answers every search in O(log n) worst case time.

Affiliated with

Also associated with

No associations

Rating

De-amortizing Binary Search Trees 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 De-amortizing Binary Search Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and De-amortizing Binary Search Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692962