Lecture 16 AVL Trees

The document discusses self-balancing binary search trees (BSTs), specifically AVL trees. It provides an overview of AVL trees, including their properties of having balance factors between -1 and 1. It describes the balance factor of a node, and the four cases for balancing an AVL tree after insertion or deletion through rotations: left-left, right-right, left-right, and right-left cases. Basic left and right rotations are also covered to rebalance the tree in these cases.

Uploaded by

All Rounded Gamer

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

37 views9 pages

Lecture 16 AVL Trees

Uploaded by

All Rounded Gamer

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 9

18-Apr-23

Self Balancing BSTs

CSC-211 Data Structures and Algorithms

Slides prepared by: Dr. Omar Ahmad

Lecture outline

• Self Balancing Search Trees

• AVL Trees
• Balance Factor in AVL Trees
• Balancing AVL Trees
• Basic Rotations in AVL Trees
• Four Cases of Balancing AVL Trees
• Deleting Nodes from AVL Trees
• Red-Black Trees

1
18-Apr-23

Self Balancing Trees

A self-balancing (or height-balanced) binary search tree is any

node-based binary search tree that automatically keeps its height
(maximal number of levels below the root) small in the face of
arbitrary item insertions and deletions.
We will be covering two types of self-balancing trees:
• AVL Trees
• Red-Black Trees
4

AVL Trees

“AVL trees are binary search trees (BSTs) in which the difference
between the height of the left and right subtree is either -1, 0, or
+1.”
AVL trees are also called a self-balancing binary search trees.
These trees help to maintain the logarithmic search time. They
are named after their inventors (AVL) Adelson, Velsky, and
Landis.

2
18-Apr-23

AVL Trees

It takes linear time to search

for an element; hence there
is no use of using the Binary
Search Tree structure. On
the other hand, if the height
of the tree is balanced, we
get better searching time.

AVL Trees
Here, the keys are the same,
but since they are inserted
in a different order, they
take different positions, and
the height of the tree
remains balanced. Hence
search will not take more
than O(logn) for any
element of the tree.
7

3
18-Apr-23

AVL Trees

In AVL trees, we keep a check on the height of the tree during

insert and delete operations. Modifications are made to maintain
the balanced height without violating the fundamental properties
of Binary Search Tree.

Balance Factor in AVL Trees

Balance factor (BF) is a fundamental attribute of every node in
AVL trees that helps to monitor the tree's height.
• Balance factor(node) = height(node->left) - height(node->right)
• Allowed values of BF are –1, 0, and +1.
• The value –1 indicates that the right sub-tree contains one extra level.
• The value +1 indicates that the left sub-tree contains one extra level.
• The value 0 shows that the tree has equal levels on both sides (it is balanced).

4
18-Apr-23

Balance Factor in AVL Trees

• Balance factor(node) = height(node->left) - height(node->right)
• Allowed values of BF are –1, 0, and +1.
• The value –1 indicates that the right sub-tree contains one extra level.
• The value +1 indicates that the left sub-tree contains one extra level.
• The value 0 shows that the tree has equal nodes on both sides (it is balanced).

Balancing AVL Trees

To make the AVL Tree balance itself, when inserting or deleting a
node from the tree, rotations are performed.
Following are the cases when rotations need to be performed
when inserting or deleting a new node:
• Case 1: Left – Left
• Case 2: Right – Right
• Case 3: Left – Right
• Case 4: Right – Left
11

5
18-Apr-23

Basic Rotations in AVL Trees

We will apply the following two basic rotations to different
nodes of an imbalanced BST to make it a valid AVL Tree
1. Left Rotation
2. Right Rotation

Basic Rotations in AVL Trees

Terminology:
root: First ancestral node at
which the Balance Factor
becomes invalid (2, or -2)
pivot: Node that moves to the
current position of root.

6
18-Apr-23

Basic Rotations in AVL Trees

Left Rotation
Pre-requisite: Right subtree of root can not be NULL.
Steps:
1. Parent(root)->root = pivot
2. root->right = pivot->left
3. pivot->left = root

Basic Rotations in AVL Trees

Right Rotation
Pre-requisite: Left subtree of root can not be NULL.
Steps:
1. Parent(root)->root = pivot
2. root->left = pivot->right
3. pivot->right = root

7
18-Apr-23