Articles Posted by admin

1. Let T be a red-black tree storing n entries, and let k be the key of an entry in T. Show how to construct from T, in O(logn) time, two red-black trees T′ and T′′, such that T′ contains all the...

Consider a sorted map that is implemented with a standard binary search tree T. Describe how to perform an operation removeSubMap(k1, k2) that removes all the entries whose keys fall within...

1. Consider a variation of splay trees, called half-splay trees, where splaying a node at depth d stops as soon as the node reaches depth ⌊d/2⌋. Perform an amortized analysis of half-splay trees.2....

Write a program that performs a simple n-body simulation, called “Jumping Leprechauns.” This simulation involves n leprechauns, numbered 1 to n. It maintains a gold value gi for each leprechaun i,...

Repeat the previous problem using an AVL tree, achieving a running time of O(slogn). Why doesn’t the solution to the previous problem trivially result in an O(s+logn) algorithm for AVL...