AVL treee

AVL Trees
An AVL search tree is a type of binary search tree (BST) that is self-balancing, ensuring that
the height of the tree remains logarithmic relative to the number of nodes. This balance is
achieved by maintaining the balance factor of each node, which measures the difference in
height between its left and right subtrees.
Key Features of AVL Trees
1. Balance Factor:
o For each node in the tree:
Balance Factor=Height of Left Subtree−Height of Right Subtree\text{Balance
Factor} = \text{Height of Left Subtree} - \text{Height of Right
Subtree}Balance Factor=Height of Left Subtree−Height of Right Subtree
o The balance factor must be either −1-1−1, 000, or +1+1+1. If this condition is
violated, the tree is rebalanced.
2. Balancing Operations:
o If an operation (like insertion or deletion) causes an imbalance, rotations are
performed to restore balance:
 Single Rotations: Left Rotation (LL) or Right Rotation (RR).
 Double Rotations: Left-Right Rotation (LR) or Right-Left Rotation (RL).
3. Height-Balanced:
o Ensures that no two subtrees differ in height by more than 1, making operations
like search, insertion, and deletion run in O(log⁡n)O(\log n)O(logn) time.
4. Binary Search Tree Property:
o The left child of a node contains values smaller than the node, and the right child
contains values greater than the node.
Advantages of AVL Trees
 Efficient Searching: Ensures logarithmic time complexity for searching due to the
balanced nature of the tree.
 Consistent Performance: Balancing prevents the tree from degenerating into a linear
structure (like a linked list).
Disadvantages of AVL Trees
 Overhead: Additional balancing operations may slightly increase the cost of insertion
and deletion.
 Complexity: Implementation is more complicated compared to simple binary search
trees.
Example
Initial Tree (Before Balancing):
3
/
2
/
1
After inserting 1, the tree becomes imbalanced because the left subtree is taller. A Right
Rotation is performed on node 3 to restore balance:
Balanced Tree (After Right Rotation):

markdown
Copy code
2
/ \
1 3
This rebalancing ensures that the AVL tree remains height-balanced.
Example :
Write a c++ code to implementation of an AVL tree in C++ to insert the numbers 3, 5, 11, 8, 4, 1,
12, 7, 2, 6.
#include <iostream>
using namespace std;
// AVL Tree Node Structure
struct Node {
int data;
Node* left;
Node* right;
int height;
Node(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
};
// Function to get the height of a node
int getHeight(Node* node) {
return node ? node->height : 0;
// Function to calculate the balance factor of a node
int getBalanceFactor(Node* node) {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
// Utility function to update the height of a node
void updateHeight(Node* node) {
if (node) {
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
// Right Rotation
Node* rotateRight(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
updateHeight(y);
updateHeight(x);
return x;
// Left Rotation
Node* rotateLeft(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
updateHeight(x);
updateHeight(y);
return y;
// Balancing the node

Node* balance(Node* node) {
int balanceFactor = getBalanceFactor(node);
// Left heavy
if (balanceFactor > 1) {
if (getBalanceFactor(node->left) < 0) {
node->left = rotateLeft(node->left); // Left-Right case
return rotateRight(node); // Left-Left case
// Right heavy
if (balanceFactor < -1) {
if (getBalanceFactor(node->right) > 0) {
node->right = rotateRight(node->right); // Right-Left case
return rotateLeft(node); // Right-Right case
return node; // No imbalance
// Insert function
Node* insert(Node* root, int key) {
if (!root) return new Node(key);

if (key < root->data) {
root->left = insert(root->left, key);
} else if (key > root->data) {
root->right = insert(root->right, key);
} else {
return root; // No duplicate keys allowed
updateHeight(root);
return balance(root);
// In-order Traversal
void inOrder(Node* root) {
if (root) {
inOrder(root->left);
cout << root->data << " ";
inOrder(root->right);
int main() {
Node* root = nullptr;

// Inserting numbers
int numbers[] = {3, 5, 11, 8, 4, 1, 12, 7, 2, 6};
for (int num : numbers) {
root = insert(root, num);
// Displaying the tree using in-order traversal
cout << "In-order traversal of the AVL tree: ";
inOrder(root);
cout << endl;
return 0;
Question no 1:Write a program to Search the minimum number in AVL tree.
Question no 2:Write a program to Search the maximum number in AVL tree.
Question no 3: Write a program to Search the minimum subtree in the AVL tree.

AVL treee

Uploaded by

Copyright:

Available Formats

AVL treee

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

AVL treee

Uploaded by

Copyright:

Available Formats

AVL Trees

Key Features of AVL Trees

Advantages of AVL Trees

Disadvantages of AVL Trees

Initial Tree (Before Balancing):

Balanced Tree (After Right Rotation):

This rebalancing ensures that the AVL tree remains height-balanced.

using namespace std;

// AVL Tree Node Structure

// Function to get the height of a node

int getHeight(Node* node) {

return node ? node->height : 0;

// Function to calculate the balance factor of a node

int getBalanceFactor(Node* node) {

return node ? getHeight(node->left) - getHeight(node->right) : 0;

// Utility function to update the height of a node

void updateHeight(Node* node) {

node->height = 1 + max(getHeight(node->left), getHeight(node->right));

// Balancing the node

int balanceFactor = getBalanceFactor(node);

node->left = rotateLeft(node->left); // Left-Right case

return rotateRight(node); // Left-Left case

if (balanceFactor < -1) {

node->right = rotateRight(node->right); // Right-Left case

return rotateLeft(node); // Right-Right case

return node; // No imbalance

Node* insert(Node* root, int key) {

if (!root) return new Node(key);

root->left = insert(root->left, key);

} else if (key > root->data) {

root->right = insert(root->right, key);

return root; // No duplicate keys allowed

void inOrder(Node* root) {

cout << root->data << " ";

Node* root = nullptr;

int numbers[] = {3, 5, 11, 8, 4, 1, 12, 7, 2, 6};

for (int num : numbers) {

root = insert(root, num);

// Displaying the tree using in-order traversal

cout << "In-order traversal of the AVL tree: ";

cout << endl;

Question no 1:Write a program to Search the minimum number in AVL tree.

Question no 2:Write a program to Search the maximum number in AVL tree.

You might also like