How can you augment a splay tree so you can find how many items are between x and y? — Store size of subtrees at each node. Find x, splay to root. Each splay, insert, and delete must maintain size in node. Find y, and along the way add up the sizes in the left subtrees, and 1 for each visited left-hand node. Splay y to root to ensure balance.