Algorithms in Java

The bst algorithms in the previous chapter work well for a wide variety of applications, but they do have the problem of bad worst-case performance....

Implement an efficient method that rebalances BSTs that do not have a count field in their nodes. Modify the standard BST insertion method in Program to...

To analyze the average-case performance costs for binary search trees, we made the assumption that the items are inserted in random order (see Section 12.7)....

In the root-insertion method of Section 12.8, we accomplished our primary objective of bringing the newly inserted node to the root of the tree by...

Top-Down 2-Trees Despite the performance guarantees that we can provide with randomized BSTs and with splay BSTs, both still admit the possibility that a particular search...

The top-down 2-insertion algorithm described in the previous section is easy to understand, but implementing it directly is cumbersome because of all the different cases...

In this section, we consider an approach to developing fast implementations of symbol-table operations which seems at first to be completely different from the tree-based...

How do we choose among randomized BSTs, splay BSTs, red–black BSTs, and skip lists for a particular application? We have concentrated on the differing nature...