Suppose that we want to solve dynamic range closest pair problems. We will maintain a data structure for a set of numbers, where the operations are to insert a number into the set, delete a number from the set, or find the closest pair of numbers whose values are in the range $[L,R]$.
Describe how to solve this problem in logarithmic time per query using two pieces of extra information at each node $x$ of a binary search tree: The identity of the successor to $x$ (the node $y$ that comes immediately after $x$ in the sorted order of the current set), and the identity of the node $z$ that is a descendant of $x$ (possibly equal to $x$ itself) and, among descendants of $x$, has the closest successor. How can we use this information to answer each query efficiently?
If we modify the data structure of problem 1 by inserting a new number and a new node for that number, and then rebalancing the tree by performing some rotations, describe how to update the added information at the nodes of the tree. Which nodes might need to have their successor pointers changed, and what should their new successors be? Which nodes need to have their descendant-with-closest-successor pointers changed, and what should the new values of these pointers be?
Suppose that we wish to find shortest paths from a single starting vertex in graphs with $n$ vertices, $2n$ edges, and edge lengths that are integers in the range from $1$ to $\log_2 n$.
What is the running time of Dijkstra's algorithm on these graphs using a Fibonacci heap for its priority queue?
What is the running time of Dijkstra's algorithm on these graphs using a bucket queue for its priority queue?
What is the running time of Dijkstra's algorithm on these graphs using a van Emde Boas tree for its priority queue?
Which of these running times is best?