Binary search trees - Data Structures and Problem Solving Using Java - page 764

single rotation Switches the roles of the parent and child while maintaining
search order. Balance is restored by tree rotations. (709)
skew Removal of left horizontal links by performing a rotation between a node
and its left child. (730)
split Fixing consecutive right horizontal links by performing a rotation
between a node and its right child. (730)

common errors

1. Using an unbalanced search tree when the input sequence is not random
will give poor performance.
2. The remove operation is very tricky to code correctly, especially for a bal-
anced search tree.
3. Lazy deletion is a good alternative to the standard remove , but you must
then change other routines, such as findMin .
4. Code for balanced search trees is almost always error-prone.
5. Forgetting to return a reference to the new subtree root is wrong for the
private helper methods insert and remove . The return value should be
assigned to root .
6. Using sentinels and then writing code that forgets about the sentinels can
lead to infinite loops. A common case is testing against null when a
nullNode sentinel is used.

on the internet

All of the code in this chapter is available online.

BinarySearchTree.java Contains the implementation of
BinarySearchTree ; BinaryNode.java
has the node declaration.
BinarySearchTreeWithRank.java
Adds order statistics.

Rotations.java Contains the basic rotations, as static methods.

RedBlackTree.java Contains the implementation of the

RedBlackTree class.

AATree.java Contains the implementation of the AATree class.

TreeSet.java Contains the implementation of the TreeSet

class.

MapImpl.java Contains the abstract MapImpl class.

TreeMap.java Contains the implementation of the TreeMap

class.