0% found this document useful (0 votes)

6 views67 pages

Module-2 Part-1 AVL Tree

The document discusses Advanced Balanced Search Trees, particularly focusing on AVL Trees, which maintain balance to ensure efficient operations like searching, insertion, and deletion with a time complexity of O(log n). It highlights the problems with standard Binary Search Trees (BSTs) becoming unbalanced and explains how AVL Trees use rotations to maintain balance. Common types of advanced balanced trees are also mentioned, including Red-Black Trees and B-Trees.

Uploaded by

jayshree

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)

6 views67 pages

Module-2 Part-1 AVL Tree

Uploaded by

jayshree

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

Advance Data Structure & Algorithms

Module:2
Advanced Balanced Search Trees

Subject Incharge
Ms. Jayshree R. Sanap
Contents
Advanced Balanced Search Trees

➢ In data structures, search trees are used to store data in a sorted and
hierarchical manner so that searching, insertion, and deletion can be done
efficiently.
➢ A balanced search tree is a special type of tree that automatically maintains
its height as small as possible, even after many insertions and deletions.
This balance ensures that operations always take O(log n) time.

➢ When the data size becomes very large and performance becomes critical (like in
databases and file systems), we use Advanced Balanced Search Trees.

Why do we need them?

● A normal Binary Search Tree (BST) can become skewed (like a linked list)
● This increases time complexity from O(log n) to O(n)
● Balanced trees prevent this problem by restructuring themselves

ADSA
Ms.J. Sanap
Advanced Balanced Search Trees

Problem with Normal BST

Insert these keys in a normal BST: 10, 20, 30, 40

● BST structure:

40 Tree becomes skewed

Search time = O(n)

ADSA
[Link]
Advanced Balanced Search Trees

Balanced Search Tree Solution (AVL Tree)

After automatic balancing:

/ \

10 30

Height is minimized
Search, Insert, Delete = O(log n)
Tree remains efficient regardless of input order

ADSA
[Link]
Advanced Balanced Search Trees

Common Advanced Balanced Search Trees

● AVL Tree
● Red–Black Tree
● B-Tree
● B+ Tree
● Splay Tree

ADSA
Ms.J. Sanap
A Binary Search Tree (BST)

A Binary Search Tree (BST) is a type of binary tree data structure in which
each node contains a unique key and satisfies a specific ordering property:
● All nodes in the left subtree of a node contain values strictly less than the root
node’s value.
● All nodes in the right subtree of a node contain values strictly greater than the
root node’s value.

ADSA
Ms.J. Sanap
A Binary Search Tree (BST)

ADSA
Ms.J. Sanap
The Problem with BST: Unbalanced Trees

● A standard BST relies on the order of insertions. While the average search,
insertion, and deletion time is O(logn)
● a BST can become severely unbalanced—or "skewed"—if data is inserted in
sorted or near-sorted order.
●

ADSA
Ms.J. Sanap
The Problem with BST: BST Degeneration

When you insert data into a BST in a sorted (ascending or descending) order, the
tree loses its branching structure and turns into a single long chain, essentially
becoming a Linked List.

● Standard BST Performance: In a balanced tree, operations like searching,

insertion, and deletion take O(logn) time.

● However, in a skewed BST (worst-case), these operations slow down to O(n)

because you have to traverse every node to find an element.

ADSA
Ms.J. Sanap
The solution: Why AVL Tree came to be

The AVL Tree (named after inventors Adelson-Velsky and Landis) was created to
solve this by being a self-balancing BST.

1. Guaranteed Balance: An AVL tree maintains a "Balance Factor" for every node,
ensuring the heights of the left and right subtrees differ by no more than 1.
2. Automatic Rotations: Whenever an insertion or deletion makes the tree
unbalanced, the AVL tree performs specific rotations (LL, RR, LR, or RL) to fix
itself immediately.

3. Optimal Performance: By staying balanced, an AVL tree guarantees that the

height of the tree remains logarithmic. This ensures that the worst-case time
complexity for search, insert, and delete is always O(logn).

ADSA
Ms.J. Sanap
AVL Tree
● An AVL tree is a type of binary search tree used in computer science. It is special
because it keeps itself balanced. This means it makes sure that the tree doesn't
get too tall and skinny, which would make finding things slow.
● An AVL tree defined as a self-balancing Binary Search Tree (BST) where the
difference between heights of left and right subtrees for any node cannot be more
than one.
● The importance of AVL trees in data structures is that they ensure operations like
search, insert, and delete are always fast, even if we do them many times.
● This makes AVL trees very useful in applications like databases and memory
management, where we need to quickly find or update information.

ADSA
Ms.J. Sanap
AVL Tree: Properties of AVL Tree
● Balanced Tree: An AVL tree is always balanced. This means that the heights of
the left and right subtrees of any node differ by at most one.
● Height-Balanced Property: The difference in height (also called the balance
factor) between the left and right subtrees of any node is -1, 0, or 1.
● Self-Balancing: An AVL tree automatically performs rotations to maintain
balance after every insertion and deletion.
● Binary Search Tree Properties: An AVL tree follows the properties of a binary
search tree (BST). This means that for any node, the left subtree contains only
nodes with values less than the node's value, and the right subtree contains only
nodes with values greater than the node's value.
● Rotations: To maintain balance, an AVL tree uses four types of rotations: left
rotation, right rotation, left-right rotation, and right-left rotation.

ADSA
Ms.J. Sanap
AVL Tree: Balance Factor of AVL Tree
● The AVL tree balance factor is a key concept used to maintain the tree's
balanced property.
● In AVL trees, the heights of the two child subtrees of any node differ by no more
than one. This balance is maintained through rotations during insertion and
deletion operations.
● The balancing factor (BF) of a node in an AVL tree is defined as the height
difference between its left and right subtrees.
For a node, the balancing factor is calculated as:

ADSA
Ms.J. Sanap
Example of an AVL Tree
● The balance factors for different nodes are: 12 , 8 , 18 , 5 , 11, 17, 4 . Since all
differences are lies between -1 to +1, so the tree is an AVL tree or Balanced BST.

ADSA
Ms.J. Sanap
Operations on an AVL Tree

● Searching : It is same as normal Binary Search Tree (BST) as an AVL

Tree is always a BST. So we can use the same implementation as BST.
The advantage here is time complexity is O(log n)
● Insertion : It does rotations along with normal BST insertion to make
sure that the balance factor of the impacted nodes is less than or equal
to 1 after insertion
● Deletion : It also does rotations along with normal BST deletion to
make sure that the balance factor of the impacted nodes is less than or
equal to 1 after deletion.

ADSA
Ms.J. Sanap
AVL Tree
➔ Rotations: rotations are designed to restore balance in O(1) time while ensuring
the overall time complexity remains O(log n).
➔ AVL Trees use four cases to rebalance themselves after insertions and deletions:

● Left-Left (LL),
● Right-Right (RR),
● Left-Right (LR)
● Right-Left (RL)