Home Data Structures and Algorithms with C++ AVL Trees in C++

Lesson 19 of 48

In Progress

← Previous Next→

AVL Trees in C++

Yasin Cakal

AVL Trees in C++ are one of the most efficient data structures for implementing a self-balancing binary search tree. AVL Trees are named after their inventors, Adelson-Velsky and Landis, who first published them in their 1962 paper titled “An Algorithm for the Organization of Information.” This data structure is used to store and manage data in a way that is both efficient and easily accessible. AVL Trees are popular due to their ability to maintain balance, which allows for time-efficient operations such as search, insert and delete. In this article, we will discuss the structure of an AVL Tree, the time complexity of its operations, the space complexity of an AVL Tree, and some sample C++ code to help you understand how to implement an AVL Tree in your own projects.

What is an AVL Tree?

An AVL Tree is a type of self-balancing binary search tree. A binary search tree is a data structure that stores data in a way that allows for quick retrieval and management of data. Each node in the tree stores a data element, and each node has two children, a left child and a right child. The left child contains a data element that is less than the parent node, and the right child contains a data element that is greater than the parent node. This structure allows for efficient searching and sorting of data.

The AVL Tree is a type of binary search tree that uses the concept of self-balancing to maintain optimal performance. This means that the AVL Tree uses a set of rules to ensure that the height of the tree is minimized. The AVL Tree is considered to be one of the most efficient data structures for implementing a self-balancing binary search tree.

Time Complexity of AVL Trees in C++

The time complexity of an AVL Tree in C++ depends on the operation that is being performed. The average time complexity of search, insert and delete operations on an AVL Tree is O(log n). The worst case time complexity of search, insert and delete operations on an AVL Tree is O(n).

Space Complexity of AVL Trees in C++

The space complexity of an AVL Tree in C++ is O(n). This means that the amount of space required to store the data in an AVL Tree is proportional to the number of elements in the tree.

How to Implement an AVL Tree in C++

Now that we have discussed the structure, time complexity, and space complexity of an AVL Tree, let’s take a look at some sample C++ code to help you understand how to implement an AVL Tree in your own projects.

The first step in implementing an AVL Tree in C++ is to create a node class. This class will be used to store the data for each node in the tree. The node class should include data members for the data element, the left child, and the right child. The node class should also include a constructor to initialize the data members.

class Node { 
public: 
    int data; 
    Node* left; 
    Node* right; 
    Node(int d){ 
        data = d; 
        left = NULL; 
        right = NULL; 
    } 
};

Next, we need to create a tree class to represent our AVL Tree. The tree class should include a root node, which will be used to point to the root node of the AVL Tree. The tree class should also include methods to perform operations on the tree, such as insert, search, and delete.

class AVLTree { 
private: 
    Node* root; 
public: 
    AVLTree(){ 
        root = NULL; 
    } 
    void insert(int data); 
    void search(int data); 
    void delete(int data); 
};

Finally, we need to write the implementations for the insert, search, and delete methods of the tree class. The insert method should take a data element and insert it into the AVL Tree. The search method should take a data element and search the tree for it. The delete method should take a data element and delete it from the tree.

// Method to insert a data element into the AVL Tree 
void AVLTree::insert(int data) { 
    // Create a new node with the given data 
    Node* n = new Node(data); 
    // If the tree is empty, set the root node to the new node 
    if(root == NULL) { 
        root = n; 
    } 
    else { 
        // Traverse the tree to find the correct place to insert the node 
        Node* current = root; 
        Node* parent = NULL; 
        while(true) { 
            parent = current; 
            if(data < current->data) { 
                // Go to the left 
                current = current->left; 
                if(current == NULL) { 
                    // Insert the node 
                    parent->left = n; 
                    break; 
                } 
            } 
            else { 
                // Go to the right 
                current = current->right; 
                if(current == NULL) { 
                    // Insert the node 
                    parent->right = n; 
                    break; 
                } 
            } 
        } 
    } 
    // Balance the tree 
    balance(n,root); 
} 

// Method to search for a data element in the AVL Tree 
void AVLTree::search(int data) { 
    // Start at the root of the tree 
    Node* current = root; 
    // Traverse the tree until the node is found 
    while(current != NULL) { 
        if(current->data == data) { 
            // Node found 
            return; 
        } 
        else if(data < current->data) { 
            // Go to the left 
            current = current->left; 
        } 
        else { 
            // Go to the right 
            current = current->right; 
        } 
    } 
    // Node not found 
    return; 
} 

// Method to delete a data element from the AVL Tree 
void AVLTree::delete(int data) { 
    // Start at the root of the tree 
    Node* current = root; 
    Node* parent = NULL; 
    // Traverse the tree until the node is found 
    while(current != NULL) { 
        if(current->data == data) { 
            // Node found 
            break; 
        } 
        else { 
            parent = current; 
            if(data < current->data) { 
                // Go to the left 
                current = current->left; 
            } 
            else { 
                // Go to the right 
                current = current->right; 
            } 
        } 
    } 
    // Check if the node is a leaf node 
    if(current->left == NULL && current->right == NULL) { 
        // Node is a leaf node 
        if(parent->left == current) { 
            parent->left = NULL; 
        } 
        else { 
            parent->right = NULL; 
        } 
    } 
    // Check if the node has one child 
    else if(current->left == NULL || current->right == NULL) { 
        // Node has one child 
        if(current->left != NULL) { 
            if(parent->left == current) { 
                parent->left = current->left; 
            } 
            else { 
                parent->right = current->left; 
            } 
        } 
        else { 
            if(parent->left == current) { 
                parent->left = current->right; 
            } 
            else { 
                parent->right = current->right; 
            } 
        } 
    } 
    // Node has two children 
    else { 
        // Find the successor node 
        Node* successor = getSuccessor(current); 
        if(current == root) { 
            root = successor; 
        } 
        else if(current == parent->left) { 
            parent->left = successor; 
        } 
        else { 
            parent->right = successor; 
        } 
        successor->left = current->left; 
    } 
    // Balance the tree 
    balance(parent, root); 
}

Conclusion

In conclusion, AVL Trees in C++ are an efficient data structure for implementing a self-balancing binary search tree. AVL Trees use a set of rules to ensure that the height of the tree is minimized, which allows for time-efficient operations such as search, insert and delete. The time complexity of search, insert and delete operations on an AVL Tree is O(log n) on average, and O(n) in the worst case. The space complexity of an AVL Tree is O(n).

Exercises

Write a program to insert the following values into an AVL Tree: 25, 15, 50, 10, 22, 35, 70, 4, 12, 18, 24, 31, 44, 66, 90.

#include <iostream> 
#include <stdlib.h> 

// Node class for AVL Tree nodes 
class Node { 
public: 
    int data; 
    Node* left; 
    Node* right; 
    Node(int d){ 
        data = d; 
        left = NULL; 
        right = NULL; 
    } 
}; 

// AVL Tree class 
class AVLTree { 
private: 
    Node* root; 
public: 
    AVLTree(){ 
        root = NULL; 
    } 
    void insert(int data); 
    void balance(Node* n, Node* root); 
}; 

// Method to insert a data element into the AVL Tree 
void AVLTree::insert(int data) { 
    // Create a new node with the given data 
    Node* n = new Node(data); 
    // If the tree is empty, set the root node to the new node 
    if(root == NULL) { 
        root = n; 
    } 
    else { 
        // Traverse the tree to find the correct place to insert the node 
        Node* current = root; 
        Node* parent = NULL; 
        while(true) { 
            parent = current; 
            if(data < current->data) { 
                // Go to the left 
                current = current->left; 
                if(current == NULL) { 
                    // Insert the node 
                    parent->left = n; 
                    break; 
                } 
            } 
            else { 
                // Go to the right 
                current = current->right; 
                if(current == NULL) { 
                    // Insert the node 
                    parent->right = n; 
                    break; 
                } 
            } 
        } 
    } 
    // Balance the tree 
    balance(n,root); 
} 

// Balance the tree 
void AVLTree::balance(Node* n, Node* root) { 
    // TODO: Balance the tree 
}

int main() { 
    AVLTree tree; 
  
    tree.insert(25); 
    tree.insert(15); 
    tree.insert(50); 
    tree.insert(10); 
    tree.insert(22); 
    tree.insert(35); 
    tree.insert(70); 
    tree.insert(4); 
    tree.insert(12); 
    tree.insert(18); 
    tree.insert(24); 
    tree.insert(31); 
    tree.insert(44); 
    tree.insert(66); 
    tree.insert(90); 
  
    return 0; 
}

Write a program to delete the value 50 from an AVL Tree.

#include <iostream> 
#include <stdlib.h> 

// Node class for AVL Tree nodes 
class Node { 
public: 
    int data; 
    Node* left; 
    Node* right; 
    Node(int d){ 
        data = d; 
        left = NULL; 
        right = NULL; 
    } 
}; 

// AVL Tree class 
class AVLTree { 
private: 
    Node* root; 
public: 
    AVLTree(){ 
        root = NULL; 
    } 
    void delete(int data); 
    Node* getSuccessor(Node* n); 
    void balance(Node* n, Node* root); 
}; 

// Method to delete a data element from the AVL Tree 
void AVLTree::delete(int data) { 
    // Start at the root of the tree 
    Node* current = root; 
    Node* parent = NULL; 
    // Traverse the tree until the node is found 
    while(current != NULL) { 
        if(current->data == data) { 
            // Node found 
            break; 
        } 
        else { 
            parent = current; 
            if(data < current->data) { 
                // Go to the left 
                current = current->left; 
            } 
            else { 
                // Go to the right 
                current = current->right; 
            } 
        } 
    } 
    // Check if the node is a leaf node 
    if(current->left == NULL && current->right == NULL) { 
        // Node is a leaf node 
        if(parent->left == current) { 
            parent->left = NULL; 
        } 
        else { 
            parent->right = NULL; 
        } 
    } 
    // Check if the node has one child 
    else if(current->left == NULL || current->right == NULL) { 
        // Node has one child 
        if(current->left != NULL) { 
            if(parent->left == current) { 
                parent->left = current->left; 
            } 
            else { 
                parent->right = current->left; 
            } 
        } 
        else { 
            if(parent->left == current) { 
                parent->left = current->right; 
            } 
            else { 
                parent->right = current->right; 
            } 
        } 
    } 
    // Node has two children 
    else { 
        // Find the successor node 
        Node* successor = getSuccessor(current); 
        if(current == root) { 
            root = successor; 
        } 
        else if(current == parent->left) { 
            parent->left = successor; 
        } 
        else { 
            parent->right = successor; 
        } 
        successor->left = current->left; 
    } 
    // Balance the tree 
    balance(parent, root); 
}

// Balance the tree 
void AVLTree::balance(Node* n, Node* root) { 
    // TODO: Balance the tree 
}

int main() { 
    AVLTree tree; 
  
    tree.delete(50); 
  
    return 0; 
}

Write a program to search for the value 44 in an AVL Tree.

#include <iostream> 
#include <stdlib.h> 

// Node class for AVL Tree nodes 
class Node { 
public: 
	int data; 
	Node *left; 
	Node *right; 

	Node(int); 
}; 

Node::Node(int data) 
{ 
	this->data = data; 
	left = NULL; 
	right = NULL; 
} 

// AVLTree class 
class AVLTree { 
	Node *root; 

	// Gets the height of an AVL Tree node 
	int height(Node *node) 
	{ 
		if (node == NULL) 
			return 0; 
		return node->data; 
	} 

	// Searches for a given key in an AVL Tree 
	bool search(Node *node, int key) 
	{ 
		if (node == NULL) 
			return false; 

		if (node->data == key) 
			return true; 

		if (node->data < key) 
			return search(node->right, key); 

		// else 
		return search(node->left, key); 
	} 

public: 
	AVLTree(); 

	// Searches for a given key in an AVL Tree 
	bool search(int key) 
	{ 
		return search(root, key); 
	} 
}; 

AVLTree::AVLTree() 
{ 
	root = NULL; 
} 

// Driver code 
int main() 
{ 
	AVLTree tree; 

	// Searches for the value 44 in the AVL Tree 
	if (tree.search(44)) 
		std::cout << "Present"; 
	else
		std::cout << "Not Present"; 

	return 0; 
}

Write a program to insert the value 22 into an AVL Tree.

#include <iostream> 
#include <stdlib.h> 

// Node class for AVL Tree nodes 
class Node { 
public: 
	int data; 
	Node *left; 
	Node *right; 

	Node(int); 
}; 

Node::Node(int data) 
{ 
	this->data = data; 
	left = NULL; 
	right = NULL; 
} 

// AVLTree class 
class AVLTree { 
	Node *root; 

	// Gets the height of an AVL Tree node 
	int height(Node *node) 
	{ 
		if (node == NULL) 
			return 0; 
		return node->data; 
	} 

	// Inserts a new value into an AVL Tree 
	Node* insert(Node* node, int key) 
	{ 
		if (node == NULL) 
			return new Node(key); 

		if (key < node->data) 
			node->left = insert(node->left, key); 
		else if (key > node->data) 
			node->right = insert(node->right, key); 
		else
			return node; 

		// Update height of this ancestor node 
		node->data = 1 + max(height(node->left), 
							height(node->right)); 

		return node; 
	} 

public: 
	AVLTree(); 

	// Inserts a new value into an AVL Tree 
	void insert(int key) 
	{ 
		root = insert(root, key); 
	} 
}; 

AVLTree::AVLTree() 
{ 
	root = NULL; 
} 

// Driver code 
int main() 
{ 
	AVLTree tree; 

	// Inserts the value 22 into the AVL Tree 
	tree.insert(22); 

	return 0; 
}

Write a program to delete the value 55 from an AVL Tree.

#include <iostream> 
#include <stdlib.h> 

// Node class for AVL Tree nodes 
class Node { 
public: 
	int data; 
	Node *left; 
	Node *right; 

	Node(int); 
}; 

Node::Node(int data) 
{ 
	this->data = data; 
	left = NULL; 
	right = NULL; 
} 

// AVLTree class 
class AVLTree { 
	Node *root; 

	// Gets the height of an AVL Tree node 
	int height(Node *node) 
	{ 
		if (node == NULL) 
			return 0; 
		return node->data; 
	} 

	// Searches for a node with the given key in an AVL Tree 
	Node* search(Node* node, int key) 
	{ 
		if (node == NULL) 
			return NULL; 

		if (node->data == key) 
			return node; 

		if (node->data < key) 
			return search(node->right, key); 

		// else 
		return search(node->left, key); 
	} 

	// Deletes a node with the given key from an AVL Tree 
	Node* deleteNode(Node* node, int key) 
	{ 
		if (node == NULL) 
			return NULL; 

		// If the key to be deleted is smaller than 
		// the root's key, then it lies in left subtree 
		if (key < node->data) 
			node->left = deleteNode(node->left, key); 

		// If the key to be deleted is greater than the 
		// root's key, then it lies in right subtree 
		else if (key > node->data) 
			node->right = deleteNode(node->right, key); 

		// if key is same as root's key, then this is the node 
		// to be deleted 
		else
		{ 
			// node with only one child or no child 
			if (node->left == NULL) 
			{ 
				Node *temp = node->right; 
				free(node); 
				return temp; 
			} 
			else if (node->right == NULL) 
			{ 
				Node *temp = node->left; 
				free(node); 
				return temp; 
			} 

			// node with two children: Get the inorder successor (smallest 
			// in the right subtree) 
			Node* temp = minValueNode(node->right); 

			// Copy the inorder successor's content to this node 
			node->data = temp->data; 

			// Delete the inorder successor 
			node->right = deleteNode(node->right, temp->data); 
		} 
		return node; 
	} 

public: 
	AVLTree(); 

	// Deletes a node with the given key from an AVL Tree 
	void deleteNode(int key) 
	{ 
		root = deleteNode(root, key); 
	} 
}; 

AVLTree::AVLTree() 
{ 
	root = NULL; 
} 

// Driver code 
int main() 
{ 
	AVLTree tree; 

	// Deletes the value 55 from the AVL Tree 
	tree.deleteNode(55); 

	return 0; 
}

Data Structures and Algorithms with C++

Participants 445