COMP2012 Object-Oriented Programming and Data Structures
Topic 8: AVL Trees
Dr. Desmond Tsoi
Department of Computer Science & Engineering The Hong Kong University of Science and Technology Hong Kong SAR, China
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 1 / 36
Motivation
A binary search trees (BST) supports efficient searching if it is well balanced — its nodes are fairly evenly distributed on both its left and right sub-trees.
However, this is not always the case as insertions and deletions of tree nodes will generally make the resulting BST unbalanced.
In the worst case, the tree is de-generated to a sorted linked list and the searching time is linear time.
Target: A balanced binary search tree
A BST with N nodes and a height of the order of log N.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 2 / 36
AVL (Adelson-Velsky and Landis) Trees
An AVL tree is a BST where the height of the two sub-trees of ANY of its nodes may differ by at most one.
Each node stores a height value, which is used to check if the tree is balanced or not.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 3 / 36
AVL Trees
AVL Tree Properties
Every sub-tree of an AVL tree is itself an AVL tree. (An empty tree is an AVL tree too.)
With this property, an AVL tree is balanced and it is guaranteed that its height is logarithmic in the number of nodes, N. i.e., order of log(N ).
Efficiency of its following tree operations can always be guaranteed.
Searching: order of log(N) in the worst case
Insertion: order of log(N) in the worst case
Deletion: order of log(N) in the worst case
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 4 / 36
AVL Tree Implementation I
template
class AVL
{
private:
struct AVLnode
{
T value;
int height;
AVL left;
AVL right;
AVLnode(const T& x) : value(x), height(0) { }
// AVLnode(const T& x) : value(x), height(0), left(), right() { }
AVLnode(const AVLnode& node) = default; // Copy constructor
// AVLnode(const AVLnode& node) // Equivalent
// : value(node.value), height(node.heigjt),
// left(node.left), right(node.right) { }
̃AVLnode() { cout << "delete: " << value << endl; }
};
AVLnode* root = nullptr;
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 5 / 36
/* File: avl.h */
// Left subtree is also an AVL object
// Right subtree is also an AVL object
AVL Tree Implementation II
AVL& right_subtree() { return root->right; }
AVL& left_subtree() { return root->left; }
const AVL& right_subtree() const { return root->right; }
const AVL& left_subtree() const { return root->left; }
int height() const; // Find the height of tree
int bfactor() const; // Find the balance factor of tree
void fix_height() const; // Rectify the height of each node in tree
void rotate_left();
void rotate_right();
void balance();
public:
AVL() = default;
̃AVL() { delete root; } // Will delete the whole tree recursively!
// Shallow AVL copy using move constructor
AVL(AVL&& avl) { root = avl.root; avl.root = nullptr; }
// Single left or anti-clockwise rotation
// Single right or clockwise rotation
// AVL tree balancing
// Build an empty AVL tree by default
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 6 / 36
AVL Tree Implementation III
AVL(const AVL& avl) // Deep copy using copy constructor
{
if (avl.is_empty())
return;
root = new AVLnode(*avl.root); // Recursive
}
bool is_empty() const { return root == nullptr; }
const T& find_min() const; // Find the minimum value in an AVL
bool contains(const T& x) const; // Search an item
void print(int depth = 0) const; // Print by rotating -90 degrees
void insert(const T& x); // Insert an item in sorted order
void remove(const T& x); // Remove an item
};
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 7 / 36
AVL Tree Searching
Searching in AVL trees is the same as in BST.
// Goal: To search for an item x in an AVL tree
// Return: (bool) true if found, otherwise false
template
bool AVL
{
if (is_empty()) // Base case #1
return false;
else if (x == root->value) // Base case #2
return true;
else if (x < root->value) // Recursion on the left subtree
return left_subtree().contains(x);
else // Recursion on the right subtree
}
return right_subtree().contains(x);
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 8 / 36
AVL Tree Insertion and Rotation
To insert an item in an AVL tree
Search the tree and locate the place where the new item should be
inserted to.
Create a new node with the item and attach it to the tree.
The insertion may cause the AVL tree unbalanced
⇒ tree balancing by rotation(s)
Types of rotation
single rotation
double rotation (i.e., two single rotations)
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 9 / 36
AVL Tree Insertion and Rotation ..
Insertion may violate the AVL tree property in 4 cases:
1. Right-Right (RR)
Left (anti-clockwise) rotation [single rotation]:
Insertion into the right sub-tree of the right child of a node
2. Left-Left (LL)
Right (clockwise) rotation [single rotation]:
Insertion into the left sub-tree of the left child of a node
3. Left-Right (LR)
Left-right rotation [double rotation]:
Insertion into the right sub-tree of the left child of a node
4. Right-Left (RL)
Right-left rotation [double rotation]:
Insertion into the left sub-tree of the right child of a node
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 10 / 36
AVL Left (Anti-clockwise) Rotation
Left rotation at node a.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 11 / 36
AVL Code: Left Rotation
/* Goal: To perform a single left (anti-clocwise) rotation */
template
void AVL
{
AVLnode* b = right_subtree().root; // Points to node b
right_subtree() = b->left;
}
b->left = *this;
fix_height();
this->root = b;
fix_height();
// Note: *this is node a
// Fix the height of node a
// Node b becomes the new root
// Fix the height of node b, now the new root
Rm 3553, desmond@ust.hk
COMP2012 (Fall 2020)
12 / 36
AVL Right (Clockwise) Rotation
Right rotation at node a.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 13 / 36
AVL Code: Right Rotation
/* Goal: To perform right (clockwise) rotation */
template
void AVL
{
AVLnode* b = left_subtree().root; // Points to node b
left_subtree() = b->right;
}
b->right = *this;
fix_height();
this->root = b;
fix_height();
// Note: *this is node a
// Fix the height of node a
// Node b becomes the new root
// Fix the height of node b, now the new root
Rm 3553, desmond@ust.hk
COMP2012 (Fall 2020)
14 / 36
Left-Right (Double) Rotation
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 15 / 36
Right-Left (Double) Rotation
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 16 / 36
AVL Code: Insertion
/* To insert an item x to AVL tree and keep the tree balanced */
template
void AVL
{
if (is_empty())
root = new AVLnode(x);
// Base case
else if (x < root->value)
left_subtree().insert(x); // Recursion on the left sub-tree
else if (x > root->value)
right_subtree().insert(x); // Recursion on the left sub-tree
balance(); // Re-balance the tree at every visited node
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 17 / 36
AVL Code: Balancing
/* Goal: To balance an AVL tree */
template
void AVL
{
if (is_empty())
return;
fix_height();
int balance_factor = bfactor();
if (balance_factor == 2)
{
// Right subtree is taller by 2
}
if (right_subtree().bfactor() < 0) // Case 4: insertion to the L of RT
right_subtree().rotate_right();
return rotate_left(); // Cases 1 or 4: Insertion to the R/L of RT
}
else if (balance_factor == -2) // Left subtree is taller by 2
{
if (left_subtree().bfactor() > 0) // Case 3: insertion to the R of LT
left_subtree().rotate_left();
return rotate_right(); // Cases 2 or 3: insertion to the L/R of LT
}
// Balancing is not required for the remaining cases
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 18 / 36
AVL Code: Balancing ..
/* To find the height of an AVL tree */
template
int AVL
/* Goal: To rectify the height values of each AVL node */
template
void AVL
{
if (!is_empty())
{
int left_avl_height = left_subtree().height();
int right_avl_height = right_subtree().height();
root->height = 1 + max(left_avl_height, right_avl_height);
} }
/* balance factor = height of right sub-tree – height of left sub-tree */
template
int AVL
{
return is_empty() ? 0
: right_subtree().height() – left_subtree().height();
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 19 / 36
Example: AVL Tree Insertion
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 20 / 36
Example: AVL Tree Insertion ..
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 21 / 36
AVL Tree Deletion
To delete an item from an AVL tree.
1. Search and locate the node with the required key.
2. Delete the node like deleting a node in BST.
3. A node deletion may result in a unbalanced tree ⇒ Re-balance the tree by rotation(s).
single rotation
double rotation (i.e. two single but different rotations)
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 22 / 36
AVL Tree Deletion ..
Similar to node deletion in BST, 3 cases need to be considered 1. The node to be removed is a leaf node
⇒ Delete the leaf node immediately 2. The node to be removed has 1 child
⇒ Adjust a pointer to bypass the deleted node
3. The node to be removed has 2 children
⇒ Replace the node to be removed with either the
• maximum node in its left sub-tree, or
• minimum node in its right sub-tree Then remove the max/min node depending on the choice above.
Removing a node can render multiple ancestors unbalanced
⇒ every sub-tree affected by the deletion has to be re-balanced.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 23 / 36
Example: AVL Tree Deletion
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 24 / 36
Example: AVL Tree Deletion ..
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 25 / 36
Example: AVL Tree Deletion …
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 26 / 36
Example: AVL Tree Deletion ….
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 27 / 36
Example: AVL Tree Deletion …..
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 28 / 36
AVL Code: Deletion I
/* To remove an item x in AVL tree and keep the tree balanced */
template
void AVL
{
if (is_empty())
return;
// Item is not found; do nothing
if (x < root->value)
left_subtree().remove(x); // Recursion on the left sub-tree
else if (x > root->value)
right_subtree().remove(x); // Recursion on the right sub-tree
else
{
AVL& left_avl = left_subtree();
AVL& right_avl = right_subtree();
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 29 / 36
AVL Code: Deletion II
// Found node has 2 children
if (!left_avl.is_empty() && !right_avl.is_empty())
{
root->value = right_avl.find_min(); // Copy the min value
right_avl.remove(root->value); // Remove node with min value
}
else // Found node has 0 or 1 child
{
AVLnode* node_to_remove = root; // Save the node first
*this = left_avl.is_empty() ? right_avl : left_avl;
// Reset the node to be removed with empty children
right_avl.root = left_avl.root = nullptr;
delete node_to_remove;
}
}
balance(); // Re-balance the tree at every visited node
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 30 / 36
AVL Code: Find the Minimum Value
/* To find the minimum value stored in an AVL tree. */
template
const T& AVL
{
// It is assumed that the calling tree is not empty
const AVL& left_avl = left_subtree();
if (left_avl.is_empty()) // Base case: Found!
return root->value;
return left_avl.find_min(); // Recursion on the left subtree
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 31 / 36
AVL Testing Code
/* File: avl.tpp
*
* It contains template header and all the template functions
*/
#include “avl.h”
#include “avl-balance.cpp”
#include “avl-bfactor.cpp”
#include “avl-contains.cpp”
#include “avl-find-min.cpp”
#include “avl-fix-height.cpp”
#include “avl-height.cpp”
#include “avl-insert.cpp”
#include “avl-print.cpp”
#include “avl-remove.cpp”
#include “avl-rotate-left.cpp”
#include “avl-rotate-right.cpp”
Rm 3553, desmond@ust.hk
COMP2012 (Fall 2020) 32 / 36
AVL Testing Code .. I
#include
using namespace std;
#include “avl.tpp”
int main() {
AVL
while(true)
{
/* File: test-avl.cpp */
char choice; int value;
cout << "Action: f/i/m/p/q/r (end/find/insert/min/print/remove): ";
cin >> choice;
switch(choice)
{
case ‘f’:
cout << "Value to find: "; cin >> value;
cout << boolalpha << avl_tree.contains(value) << endl;
break;
case 'i':
cout << "Value to insert: "; cin >> value;
avl_tree.insert(value);
break;
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 33 / 36
AVL Testing Code .. II
} }
}
case ‘m’:
if (avl_tree.is_empty())
cerr << "Can't search an empty tree!" << endl;
else
cout << avl_tree.find_min() << endl;
break;
case 'p':
avl_tree.print();
break;
case 'q': default:
return 0;
case 'r':
cout << "Value to remove: "; cin >> value;
avl_tree.remove(value);
break;
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 34 / 36
AVL Trees: Pros and Cons
Pros:
Time complexity for searching is in the order of log(N) since AVL trees are always balanced.
Insertion and deletions are also in the order of log(N) since the operation is dominated by the searching step.
The tree re-balancing step adds no more than a constant factor to the time complexity of insertion and deletion.
Cons:
A bit more space for storing the height of an AVL node.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 35 / 36
That’s all! Any questions?
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 36 / 36