Data Structures, Algorithms, & Applications in C++
Chapter 15, Exercise 19

Methods outputFromHoldingTrack (Program 8.11) and putIntoHoldingTrack (Program 8.12) currently take Theta(numberOfTracks) time. As suggested at the end of Section 8.5.3 we can augment the data structures used in Section 8.5.3 with an AVL tree t. The AVL tree t contains the top cars (together with the holding tracks they come from) in each of the holding tracks, and the search key used is the car index.

When the top car is deleted from holding track itsTrack in method outputFromoldingTrack, this car must be deleted from the AVL tree and the new car at the top of holding track itsTrack inserted. Each of these operations takes O(log nmberOfTracks) time. We can find the new smallestCar and itsTrack by making as many left child moves as possible starting at the root of the AVL tree. Therefore, the complexity of outputFromHoldingTrack is now O(log numberOfTracks).

In method putInHoldingTrack we must first find the holding track with the smallest car > c at its top. This can be done by starting at the root of the AVL tree and walking down to a leaf. If the car in the current AVL tree node is < c, we move into the right subtree of this node (the left subtree contains smaller cars which are not candidates for the answer); and if the car in the current AVL tree node is > c, it is the best candidate for the answer found so far and we move into its left subtree looking for a better candidate (the right subtree contains worse candidates). The described search takes O(height of tree) = O(log numberOfTracks) time.

Whe c is added to the best holding track, we must delete the corresponding entry from the AVL tree and insert the car c together with its holding track number into the AVL tree. The overall complexity of putInHoldingTrack is now O(log numberOfTracks).

Since the use of an AVL tree as described above reduces the complexity of both outputFromHoldingTrack and putInHoldingTrack to O(log numberOfTracks), the overall complexity of the solution of Section 8.5.3 becomes O(n log numberOfTracks).