Page 151 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes First, Eunice has two children. So, we find the child with the greatest key in Eunice’s left subtree,
which is Dontonio, delete it, and replace Eunice with Dontonio. We start by deleting Dontonio:
3
Daisy
2 2
Eunice
Binky
1 1
Baby Calista 1
Daisy Luther
0 0
Ahmed Boo 0
Fred

And we start checking at Eunice. It is imbalanced. Looking at it, we see that it’s a Zig-Zag, so we
have to double-rotate about Fred:

3
Daisy
2 1
Fred
Binky
1 1
Baby Calista 0 0
Daisy Eunice Luther
0 0
Ahmed Boo

Now, the subtree rooted by Fred is balanced, but the subtree’s height is one less than it used to
be, so we need to move to it’s parent and check it. Its height is unchanged, and it is balanced, so
we’re done – as a last step, we replace Eunice with Dontonio:

AVL Tree Algorithms

#ifndef AVL_TREE_H
#define AVL_TREE_H
#include “dsexceptions.h”
#include <iostream> // For NULL
using namespace std;
// AvlTree class
//
// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x (unimplemented)
// bool contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items

146 LOVELY PROFESSIONAL UNIVERSITY