Data Structures, Algorithms, & Applications in Java
Chapter 16, Exercise 17
Please read the solutions to Exercises 15.19 and 16.15 before you proceed.
We shall combine the ideas used in these solutions
to arrive at our
implementation of an indexed AVL tree.
Although we can develop IndexedAVLtree
as a subclass of
AVLtree, we shall
develop IndexedAVLtree as a subclass of
BinarySearchTree.
The shortest and simplest codes result from the use of recursion.
However, since our primary motivation to use AVL trees is run time
efficiency, we shall develop the codes as iterative ones.
First we develop a class IAVLElement
for the element field of a binry search tree. The code is given below.
// top-level nested class
static class IAVLElement
{
// data members
Object element; // element in node
int leftSize; // number of elements in left subtree
int bf; // balance factor of node
// constructors
IAVLElement(int theLeftSize, int theBalanceFactor, Object theElement)
{
leftSize = theLeftSize;
bf = theBalanceFactor;
element = theElement;
}
IAVLElement(Object theElement)
{element = theElement;}
/** @return equivalent string suitable for output */
public String toString()
{return element.toString();}
}
The code to search for an element invokes the search method
for the super class and then extracts the element from the
object returned by the super class' search method.
/** @return element whose key is theKey
* @return null if there is no element with key theKey */
public Object get(Object theKey)
{
Object theElement = super.get(theKey);
if (theElement == null)
// no matching element
return null;
else
return ((IAVLElement) theElement).element;
}
To facilitate the implementation of the method get(theIndex),
we first develop the method getDataElement(theIndex),
which returns the element field (this is of type
Data) of the node whose index is
theIndex.
/** @return Data object of element whose index is theIndex
* @return null if there is no element with index theIndex */
Data getDataElement(int theIndex)
{
BinaryTreeNode p = root;
while (p != null)
{
IAVLElement q = (IAVLElement) ((Data) p.element).element;
if (theIndex < q.leftSize)
// desired element is in left subtree
p = p.leftChild;
else
if (theIndex > q.leftSize)
{// desired element is in right subtree
theIndex -= q.leftSize + 1;
p = p.rightChild;
}
else
// found desired element
return (Data) p.element;
}
// no element with index equal to theIndex
return null;
}
Now we use the method getDataElement to arrive
at the code for get(theIndex).
/** @return element whose index is theIndex
* @return null if there is no element with index theIndex */
public Object get(int theIndex)
{
Data theData = getDataElement(theIndex);
if (theData == null)
// no element with index theIndex
return null;
else
return ((IAVLElement) theData.element).element;
}
To assist in the development of the code for the insert operation,
we first develop methods to adjust balance factors
and to perform the different types of rotations
needed to restore balance.
The method fixBF is used to
change the balance factors of nodes on the path form
a node q to (but not including) the newly inserted node
r. The balance factors of all these nodes
were 0 prior to the insertion.
theKey is the key of the newly inserted element.
It is used to construct the path to the newly inserted node.
/** set balance factors on path from q to r */
static void fixBF(BinaryTreeNode q, BinaryTreeNode r, Comparable theKey)
{// Balance factors from q to r were originally 0.
// They need to be changed to +1 or -1.
// Use theKey to find path from q to r.
while (q != r)
if (theKey.compareTo(((Data) q.element).key) < 0)
{// height of left subtree has increased
((IAVLElement) ((Data) q.element).element).bf = 1;
q = q.leftChild;
}
else
{// height of right subtree has increased
((IAVLElement) ((Data) q.element).element).bf = -1;
q = q.rightChild;
}
}
The methods to perform the four different types of rotations
are given below. They do the pointer and balance factor changes
required by Figures 16.4 (LL rotation), 16.5 (LR rotation),
and the corresponding figures for RR and RL rotations (see solution to
Exercise 12).
/** LL rotation around a, pa is parent of a and b is left child of a */
void llRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b)
{
// restructure subtree at a
a.leftChild = b.rightChild;
b.rightChild = a;
((IAVLElement) ((Data) a.element).element).leftSize -=
((IAVLElement) ((Data) b.element).element).leftSize + 1;
if (pa != null)
// a is not the root
if (a == pa.leftChild)
pa.leftChild = b;
else
pa.rightChild = b;
else
root = b;
// set balance factors
((IAVLElement) ((Data) a.element).element).bf = 0;
((IAVLElement) ((Data) b.element).element).bf = 0;
}
/** RR rotation around a, pa is parent of a and b is right child of a */
void rrRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b)
{
// restructure subtree at a
a.rightChild = b.leftChild;
b.leftChild = a;
((IAVLElement) ((Data) b.element).element).leftSize +=
((IAVLElement) ((Data) a.element).element).leftSize + 1;
if (pa != null)
// a is not the root
if (a == pa.leftChild)
pa.leftChild = b;
else
pa.rightChild = b;
else
root = b;
// set balance factors
((IAVLElement) ((Data) a.element).element).bf = 0;
((IAVLElement) ((Data) b.element).element).bf = 0;
}
/** LR rotation around a, pa is parent of a and b is left child of a */
void lrRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b)
{
BinaryTreeNode c = b.rightChild;
// restructure subtree at a
a.leftChild = c.rightChild;
b.rightChild = c.leftChild;
c.leftChild = b;
c.rightChild = a;
((IAVLElement) ((Data) a.element).element).leftSize -=
((IAVLElement) ((Data) b.element).element).leftSize +
((IAVLElement) ((Data) c.element).element).leftSize + 2;
((IAVLElement) ((Data) c.element).element).leftSize +=
((IAVLElement) ((Data) b.element).element).leftSize + 1;
if (pa != null)
// a is not the root
if (a == pa.leftChild)
pa.leftChild = c;
else
pa.rightChild = c;
else
root = c;
// set balance factors
int bfOfC = ((IAVLElement) ((Data) c.element).element).bf;
if (bfOfC == 1)
{
((IAVLElement) ((Data) a.element).element).bf = -1;
((IAVLElement) ((Data) b.element).element).bf = 0;
}
else
if (bfOfC == -1)
{
((IAVLElement) ((Data) a.element).element).bf = 0;
((IAVLElement) ((Data) b.element).element).bf = 1;
}
else
{// bfOfC = 0
((IAVLElement) ((Data) a.element).element).bf = 0;
((IAVLElement) ((Data) b.element).element).bf = 0;
}
((IAVLElement) ((Data) c.element).element).bf = 0;
}
/** RL rotation around a, pa is parent of a and b is right child of a */
void rlRotate(BinaryTreeNode pa, BinaryTreeNode a, BinaryTreeNode b)
{
BinaryTreeNode c = b.leftChild;
// restructure subtree at a
a.rightChild = c.leftChild;
b.leftChild = c.rightChild;
c.leftChild = a;
c.rightChild = b;
((IAVLElement) ((Data) b.element).element).leftSize -=
((IAVLElement) ((Data) c.element).element).leftSize + 1;
((IAVLElement) ((Data) c.element).element).leftSize +=
((IAVLElement) ((Data) a.element).element).leftSize + 1;
if (pa != null)
// a is not the root
if (a == pa.leftChild)
pa.leftChild = c;
else
pa.rightChild = c;
else
root = c;
// set balance factors
int bfOfC = ((IAVLElement) ((Data) c.element).element).bf;
if (bfOfC == 1)
{
((IAVLElement) ((Data) a.element).element).bf = 0;
((IAVLElement) ((Data) b.element).element).bf = -1;
}
else
if (bfOfC == -1)
{
((IAVLElement) ((Data) a.element).element).bf = 1;
((IAVLElement) ((Data) b.element).element).bf = 0;
}
else
{// bfOfC = 0
((IAVLElement) ((Data) a.element).element).bf = 0;
((IAVLElement) ((Data) b.element).element).bf = 0;
}
((IAVLElement) ((Data) c.element).element).bf = 0;
}
The code for the insert operation is given below.
The first part of the code searches for the place to insert
the new element using a process identical to that used
to insert an element into an unbalanced search tree.
The left size values are adjusted under the assumption that the
insert will succeed. In case it fails, we reset the
left size values using the method resetLeftSize.
When we search for the place to insert
the new element, we also keep track of the most recently
seen node whose current balance factor is +1 or -1.
Following the insertion, this node is the candidate node
for the A node around which a rotation
(if necessary) is to be performed.
The nature of the imbalance (if any) at A
is determined, and the appropriate rotation performed.
/** insert an element with the specified key
* overwrite old element if there is already an
* element with the given key
* @return old element (if any) with key = theKey */
public Object put(Object theKey, Object theElement)
{
BinaryTreeNode p = root, // search pointer
pp = null, // parent of p
a = null, // node with bf != 0
pa = null; // parent of a
// find place to insert theElement
// also record most recent node with bf != 0
// in a and its parent in pa
Comparable elementKey = (Comparable) theKey;
while (p != null)
{// examine p.element.key
Data pData = (Data) p.element;
if (((IAVLElement) pData.element).bf != 0)
{// new candidate for a node
a = p;
pa = pp;
}
pp = p;
// move p to a child
if (elementKey.compareTo(pData.key) < 0)
{// assume the insert will add a new node in left subtree
((IAVLElement) ((Data) p.element).element).leftSize += 1;
p = p.leftChild;
}
else if (elementKey.compareTo(pData.key) > 0)
p = p.rightChild;
else
{// overwrite element with same key
Object elementToReturn =
((IAVLElement) pData.element).element;
((IAVLElement) pData.element).element = theElement;
resetLeftSize(-1, elementKey);
return elementToReturn;
}
}
// get a node for theElement and attach to pp
IAVLElement q = new IAVLElement(0, 0, theElement);
BinaryTreeNode r = new BinaryTreeNode
(new Data(elementKey, q));
if (root != null)
// the tree is not empty
if (elementKey.compareTo(((Data) pp.element).key) < 0)
pp.leftChild = r;
else
pp.rightChild = r;
else
{// insertion into empty tree
root = r;
return null;
}
// see if we must rebalance or simply change balance factors
if (a != null)
{// possible rebalancing needed
Data aData = (Data) a.element;
if (((IAVLElement) aData.element).bf < 0)
// bf = -1 before insertion
if (elementKey.compareTo(aData.key) < 0)
{// insertion in left subtree
// height of left subtree has increased by 1
// new bf of a is 0, no rebalancing
((IAVLElement) aData.element).bf = 0;
// fix bf on path from a to r
fixBF(a.leftChild, r, elementKey);
}
else
{// insertion in right subtree
// bf of a is -2, rebalance
BinaryTreeNode b = a.rightChild;
if (elementKey.compareTo(((Data) b.element).key) > 0)
{// RR case
fixBF(b.rightChild, r, elementKey);
rrRotate(pa, a, b);
}
else
{// RL case
fixBF(b.leftChild, r, elementKey);
rlRotate(pa, a, b);
}
}
else // bf = +1 before insertion
if (elementKey.compareTo(aData.key) > 0)
{// insertion in right subtree
// height of right subtree has increased by 1
// new bf of a is 0, no rebalancing
((IAVLElement) aData.element).bf = 0;
// fix bf on path from a to r
fixBF(a.rightChild, r, elementKey);
}
else
{// insertion in left subtree
// bf of a is +2, rebalance
BinaryTreeNode b = a.leftChild;
if (elementKey.compareTo(((Data) b.element).key) < 0)
{// LL case
fixBF(b.leftChild, r, elementKey);
llRotate(pa, a, b);
}
else
{// LR case
fixBF(b.rightChild, r, elementKey);
lrRotate(pa, a, b);
}
}
}
else // a is nulL, no rebalancing
fixBF(root, r, elementKey);
return null;
}
The code to reset left size values when an insert fails is
given below.
/** add r to all leftSize values on the path from the root
* to the node with key = theKey */
void resetLeftSize(int r, Comparable theKey)
{
BinaryTreeNode p = root;
while (p != null)
if (theKey.compareTo(((Data) p.element).key) < 0)
{
((IAVLElement) ((Data) p.element).element).leftSize += r;
p = p.leftChild;
}
else if (theKey.compareTo(((Data) p.element).key) > 0)
p = p.rightChild;
else return;
}
The code to remove/delete an element has two parts. The first part
assumes that the delete will succeed and decrements left size values as
we move down the AVL tree searching for the element that is to be deleted.
The path from the root
to the parent of the physically deleted node is saved on a stack.
The rebalancing code follows the discussion in the text very closely.
It also makes use of the fact that the following
pairs of rotations are indentical LL and R1, LR and R-1,
RR and L-1, and RL and L1. It also uses the fact that
LL and R0 and RR and L0 rotations differ only in the final balance
factors. See the solution to Exercise 14 for the figures
for L0, L1, and L-1 rotations.
/** @return matching element and remove it
* @return null if no matching element */
public Object remove(Object theKey)
{
Comparable searchKey = (Comparable) theKey;
// define a stack to hold path taken from root
// to physically deleted node
ArrayStack stack = new ArrayStack();
// p will eventually to point to node with key theKey
BinaryTreeNode p = root; // search pointer
while (p != null && !theKey.equals(((Data) p.element).key))
{// move to a child of p
stack.push(p);
if (searchKey.compareTo(((Data) p.element).key) < 0)
{// assume remove will succeed, decrease leftSize by 1
((IAVLElement) ((Data) p.element).element).leftSize--;
p = p.leftChild;
}
else
p = p.rightChild;
}
if (p == null)
{// no element with key theKey, increment leftSize values
// that were decremented during search
resetLeftSize(1, searchKey);
return null;
}
// found the matching element, save this element
Object theElement = ((IAVLElement) ((Data) p.element).element).element;
// restructure tree
// handle case when p has two children
if (p.leftChild != null && p.rightChild != null)
{// p has two children, convert to 0 or 1 child case
// find largest element in left subtree of p
stack.push(p);
BinaryTreeNode s = p.leftChild;
while (s.rightChild != null)
{// move to larger element
stack.push(s);
s = s.rightChild;
}
// move largest from s to p
Data pData = (Data) p.element;
pData.key = ((Data) s.element).key;
((IAVLElement) pData.element).element =
((IAVLElement) ((Data) s.element).element).element;
((IAVLElement) pData.element).leftSize--;
p = s;
}
// p has at most one child
// save child pointer in c
BinaryTreeNode c;
if (p.leftChild != null)
c = p.leftChild;
else
c = p.rightChild;
// delete p
if (p == root)
root = c;
else
// is p a left or right child?
if (p == ((BinaryTreeNode) stack.peek()).leftChild)
((BinaryTreeNode) stack.peek()).leftChild = c;
else
((BinaryTreeNode) stack.peek()).rightChild = c;
Comparable pKey = ((Data) p.element).key;
// pKey may not equal theKey
// rebalance tree and correct balance factors
// use stack to retrace path to root
// set q to parent of deleted node
BinaryTreeNode q;
try {q = (BinaryTreeNode) stack.pop();}
catch (Exception e)
{return theElement;} // root was deleted
while (q != null)
{
Data qData = (Data) q.element;
IAVLElement qAVL = (IAVLElement) qData.element;
if (pKey.compareTo(qData.key) <= 0)
{// node p was deleted from the left subtree of q
// height of left subtree reduced by 1
qAVL.bf--;
if (qAVL.bf == -1)
// height of q is unchanged, nothing more to do
return theElement;
if (qAVL.bf == -2)
{// q is unbalanced, classify unbalance and rotate
BinaryTreeNode b = q.rightChild,
pa; // q is a node
// pa is parent of a
try {pa = (BinaryTreeNode) stack.pop();}
catch (Exception e)
{pa = null;} // stack empty
IAVLElement bAVL = (IAVLElement) ((Data) b.element).element;
switch (bAVL.bf)
{
case 0: // L0 imbalance
rrRotate(pa, q, b);
bAVL.bf = 1;
qAVL.bf = -1; // q is a node
return theElement;
case 1: // L1 imbalance
rlRotate(pa, q, b);
break; // must continue on path to root
case -1: // L-1 imbalance
rrRotate(pa, q, b);
}
q = pa;
}
else
// qAVL.bf is 0
try {q = (BinaryTreeNode) stack.pop();}
catch (Exception e)
{q = null;} // stack empty
}
else
{// pKey > qData.key
// deleted from right subtree of q
// height of right subtree reduced by 1
qAVL.bf++;
if (qAVL.bf == 1)
// height of q is unchanged, nothing more to do
return theElement;
if (qAVL.bf == 2)
{// q is unbalanced
// classify imbalance and rotate
BinaryTreeNode b = q.leftChild,
pa; // q is a node
// pa is parent of a
try {pa = (BinaryTreeNode) stack.pop();}
catch (Exception e)
{pa = null;} // stack empty
IAVLElement bAVL = (IAVLElement) ((Data) b.element).element;
switch (bAVL.bf)
{
case 0: // R0 imbalance
llRotate(pa, q, b);
bAVL.bf = -1;
qAVL.bf = 1; // q is a node
return theElement;
case 1: // R1 imbalance
llRotate(pa, q, b);
break; // must continue on path to root
case -1: // R-1 imbalance
lrRotate(pa, q, b);
}
q = pa;
}
else
// qAVL.bf is 0
try {q = (BinaryTreeNode) stack.pop();}
catch (Exception e)
{q = null;} // stack empty
}
}
return theElement;
}
The code for an indexed delete is very similar and is given below.
/** @return element with index theIndex and remove it
* @return null if no element has this index */
public Object remove(int theIndex)
{
if (root == null || theIndex < 0)
// empty tree or invalid index
return null;
// define a stack to hold path taken from root
// to physically deleted node
java.util.Stack stack = new java.util.Stack();
// save theIndex
int savedIndex = theIndex;
// p will eventually to point to node with index'th element
BinaryTreeNode p = root; // search pointer
IAVLElement pIAVL = (IAVLElement) ((Data) p.element).element;
while (theIndex != pIAVL.leftSize)
{
stack.push(p);
if (theIndex < pIAVL.leftSize)
{// desired element is in left subtree, assume remove will succeed
((IAVLElement) ((Data) p.element).element).leftSize--;
p = p.leftChild;
}
else
{// desired element is in right subtree
theIndex -= pIAVL.leftSize + 1;
p = p.rightChild;
}
if (p == null) break;
pIAVL = (IAVLElement) ((Data) p.element).element;
}
if (p == null)
// theIndex > number of elements - 1, must have made only right
// child moves, no leftSize values to reset
return null;
// found the matching element, save this element
Object theElement = ((IAVLElement) ((Data) p.element).element).element;
// restructure tree
// handle case when p has two children
if (p.leftChild != null && p.rightChild != null)
{// p has two children, convert to 0 or 1 child case
// find largest element in left subtree of p
stack.push(p);
BinaryTreeNode s = p.leftChild;
while (s.rightChild != null)
{// move to larger element
stack.push(s);
s = s.rightChild;
}
// move largest from s to p
Data pData = (Data) p.element;
pData.key = ((Data) s.element).key;
((IAVLElement) pData.element).element =
((IAVLElement) ((Data) s.element).element).element;
((IAVLElement) pData.element).leftSize--;
p = s;
}
// p has at most one child
// save child pointer in c
BinaryTreeNode c;
if (p.leftChild != null)
c = p.leftChild;
else
c = p.rightChild;
// delete p
if (p == root)
root = c;
else
// is p a left or right child?
if (p == ((BinaryTreeNode) stack.peek()).leftChild)
((BinaryTreeNode) stack.peek()).leftChild = c;
else
((BinaryTreeNode) stack.peek()).rightChild = c;
Comparable pKey = ((Data) p.element).key;
// pKey may not equal theKey
// rebalance tree and correct balance factors
// use stack to retrace path to root
// set q to parent of deleted node
BinaryTreeNode q;
try {q = (BinaryTreeNode) stack.pop();}
catch (Exception e)
{return theElement;} // root was deleted
while (q != null)
{
Data qData = (Data) q.element;
IAVLElement qAVL = (IAVLElement) qData.element;
if (pKey.compareTo(qData.key) <= 0)
{// node p was deleted from the left subtree of q
// height of left subtree reduced by 1
qAVL.bf--;
if (qAVL.bf == -1)
// height of q is unchanged, nothing more to do
return theElement;
if (qAVL.bf == -2)
{// q is unbalanced, classify unbalance and rotate
BinaryTreeNode b = q.rightChild,
pa; // q is a node
// pa is parent of a
try {pa = (BinaryTreeNode) stack.pop();}
catch (Exception e)
{pa = null;} // stack empty
IAVLElement bAVL = (IAVLElement) ((Data) b.element).element;
switch (bAVL.bf)
{
case 0: // L0 imbalance
rrRotate(pa, q, b);
bAVL.bf = 1;
qAVL.bf = -1; // q is a node
return theElement;
case 1: // L1 imbalance
rlRotate(pa, q, b);
break; // must continue on path to root
case -1: // L-1 imbalance
rrRotate(pa, q, b);
}
q = pa;
}
else
// qAVL.bf is 0
try {q = (BinaryTreeNode) stack.pop();}
catch (Exception e)
{q = null;} // stack empty
}
else
{// pKey > qData.key
// deleted from right subtree of q
// height of right subtree reduced by 1
qAVL.bf++;
if (qAVL.bf == 1)
// height of q is unchanged, nothing more to do
return theElement;
if (qAVL.bf == 2)
{// q is unbalanced
// classify imbalance and rotate
BinaryTreeNode b = q.leftChild,
pa; // q is a node
// pa is parent of a
try {pa = (BinaryTreeNode) stack.pop();}
catch (Exception e)
{pa = null;} // stack empty
IAVLElement bAVL = (IAVLElement) ((Data) b.element).element;
switch (bAVL.bf)
{
case 0: // R0 imbalance
llRotate(pa, q, b);
bAVL.bf = -1;
qAVL.bf = 1; // q is a node
return theElement;
case 1: // R1 imbalance
llRotate(pa, q, b);
break; // must continue on path to root
case -1: // R-1 imbalance
lrRotate(pa, q, b);
}
q = pa;
}
else
// qAVL.bf is 0
try {q = (BinaryTreeNode) stack.pop();}
catch (Exception e)
{q = null;} // stack empty
}
}
return theElement;
}
The elements can be output in ascending order by performing
an inorder traversal.
The method for this is inherited from the super class
BinarySearchTree.
The complexity of both get methods,
put,
and both
remove methods is O(h),
where h is the height of the input tree.
Since the tree is an AVL tree, its height is
O(log n).
The ascend operation performs
an inorder traversal which takes O(n) time.
All codes, test data, and output can be found in the files
IndexedAVLtree.*.