In Sections 1.4, 4.5, and 5.3, we d

In Sections 1.4, 4.5, and 5.3, we discussed the binary search tree—one of the principal data structures for implementing dictionaries. It is a binary tree whose nodes
contain elements of a set of orderable items, one element per node, so that all elements in the left subtree are smaller than the element in the subtree’s root, and all
the elements in the right subtree are greater than it. Note that this transformation
from a set to a binary search tree is an example of the representation-change technique. What do we gain by such transformation compared to the straightforward
implementation of a dictionary by, say, an array? We gain in the time efficiency
of searching, insertion, and deletion, which are all in(logn), but only in the average case. In the worst case, these operations are in(n)because the tree can
degenerate into a severely unbalanced one with its height equal ton−1.
Computer scientists have expended a lot of effort in trying to find a structure
that preserves the good properties of the classical binary search tree—principally,
the logarithmic efficiency of the dictionary operations and having the set’s elements sorted—but avoids its worst-case degeneracy. They have come up with two
approaches.
The first approach is of the instance-simplification variety: an unbalanced
binary search tree is transformed into a balanced one. Because of this, such
trees are called self-balancing. Specific implementations of this idea differ
by their definition of balance. AnAVL treerequires the difference between
the heights of the left and right subtrees of every node never exceed 1. A
red-black treetolerates the height of one subtree being twice as large as the
other subtree of the same node. If an insertion or deletion of a new node
creates a tree with a violated balance requirement, the tree is restructured
by one of a family of special transformations calledrotationsthat restore the
balance required. In this section, we will discuss only AVL trees. Information
about other types of binary search trees that utilize the idea of rebalancing
via rotations, including red-black trees andsplay trees, can be found in the
references [Cor09], [Sed02], and [Tar83].