AVL Tree
Post By kanra
Blogs AVL Tree
March 28, 2019
Category
Data Structure
Tag
AlgorithmC++
An AVL tree is a self-balancing binary search tree.
It is like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O( logn ) search time.
In an AVL tree, the heights of the two child subtrees of any node differ by at most one.
If at any time they differ by more than one, rebalancing is done to restore this property.
Insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation.
Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly to be balanced.

 

A non-empty binary tree T is balanced if:
1) Left subtree of T is balanced
2) Right subtree of T is balanced
3) The difference between heights of left subtree and right subtree is not more than 1.

 

 

Abstract Data Type (ADT)

template<class type>
struct node_avl
{
	type *data;
	node_avl<type> *left, *right;
	short BF;			// balance factor range from -1, 0, 1
};

 

Get the size (# of node) of a AVL

template<class type>
int AVL_size(node_avl<type> * root)
{
	return ((root) ? 1 + AVL_size(root->left) + AVL_size(root->right) : 0);
}

 

Get the height of a AVL

template<class type>
int AVL_height(node_avl<type> * root)
{
	if (root)
	{
		int left = AVL_height(root->left);
		int right = AVL_height(root->right);
		if (left > right)
			return ++left;
		else
			return ++right;
	}

	return 0;
}

 

Determine if the AVL tree is balanced

/*
Returns true if the tree is height-balanced
*/
template<class type>
bool AVL_is_balanced(node_avl<type> *root)
{
	int lh;			/* for height of left subtree */
	int rh;			/* for height of right subtree */

	/* If tree is empty then return true */
	if (root == NULL)
		return 1;

	/* Get the height of left and right sub trees */
	lh = AVL_height(root->left);
	rh = AVL_height(root->right);

	int differ = lh - rh;

	// The difference of heights of left subtree and right subtree is not more than 1.
	if ((differ == 1 || differ == 0 || differ == -1) &&
		AVL_is_balanced(root->left) &&
		AVL_is_balanced(root->right))
		return 1;

	/* The tree is not height-balanced here*/
	return 0;
}

 

Clear an AVL tree

template<class type>
int AVL_clear(node_avl<type>* &root)
{
	int count = 0;
	if (root)
	{
		count = AVL_clear(root->left) + AVL_clear(root->right) + 1;

		delete root->data;
		delete root;
		root = NULL;
	}

	return count;
}

 

Display item by value in order for an AVL

template<class type>
int AVL_display(node_avl<type>* root)
{
	int count = 0;
	if (root)
	{
		count += AVL_display(root->left);
		cout << *(root->data) << " "; 
		++count;
		count += AVL_display(root->right);
	}

	return count;
}

 

Display items in tree-liked structure for an AVL

template<class type>
int AVL_display_tree(node_avl<type> *root, int lv)
{
	int cc = 0;
	if (root)
	{
		cc = AVL_display_tree(root->right, lv + 1) + 1;
		int sp = lv;
		while (sp-- > 1)
			cout << "         ";

		cout << "   " << *(root->data) << "[" << root->BF << "]"
			<< ((root->left && root->right) ? " < " : ((root->right) ? " / " : ((root->left) ? " \\ " : ""))) 
            << endl; 
            cc += AVL_display_tree(root->left, lv + 1);
	}

	return cc;
}

 

Insertion function of AVL tree

Process:
1. Insert at leaf as BST, update balance factor of parent node on the way back.
2. If parent node BF becomes 2, do left rotate.
3. If parent node BF becomes -2, do right rotate.

 

This operation require 3 functions:

1. A recursive traversal function
2. Right rotate function

  • Root is a node with balance factor of -2, rotate right with its left child
  • Root is a node with balance factor of -1, rotate right with its left child

3. Left rotate function

  • Root is a node with balance factor of 2, rotate left with its right child
  • Root is a node with balance factor of 1, rotate left with its right child

 

/*
Return updated balancing factor of current stack node
Telling previous stack if there is rotation needed
*/
template<class type>
bool AVL_insert(const type & to_insert, node_avl<type>*& root)
{
	if (root)
	{
		bool change_BF;		// need to change the BF?
		if (to_insert < *(root->data))
		{
			// if last stack perform rotate, no change on later BF
			change_BF = AVL_insert(to_insert, root->left);
			if (change_BF)
			{
				--(root->BF);
				if (root->BF == 0)		//	if node's BF on its back become 0, no change on later node
					return 0;

				if (root->BF == -2)		// come back from left, balance factor = -2, right rotate 
					return AVL_right_rotate(root);				// perform rotate return 0;
			}
		}
		else
		{
			// if last stack perform rotate, no change on later BF
			change_BF = AVL_insert(to_insert, root->right);
			if (change_BF)
			{
				++(root->BF);
				if (root->BF == 0)
					return 0;

				if (root->BF == 2)		// come back from right, balance factor = 2, left rotate 
					return AVL_left_rotate(root);
			}
		}

		// no return above
		return change_BF;
	}
	else
	{
		root = new node_avl<type>;
		root->data = new type;
		*(root->data) = to_insert;
		root->BF = 0;
		root->left = root->right = NULL;
		return 1;
	}
}

/*
Perform a right rotate

Return BF 0 as already balanced
*/
template<class type>
bool AVL_right_rotate(node_avl<type>*& root)
{
	node_avl<type> * old = root;
	if (root->BF == -2)		// root node with BF == -2
	{
		root = root->left;
		if (root->BF == 1)		// root's left child with BF == 1, perform left rotate for its left child first
			AVL_left_rotate(root);
		
		old->left = root->right;
		root->right = old;
		if (root->BF == 0)
		{
			root->BF = 1;
			old->BF = -1;
		}
		else if (root->BF == -1)
		{
			old->BF = 0;					// old root node become height balanced
			root->BF = 0;
		}
		else									// new root BF == -2
		{
			old->BF = 1;					// old root node carry right child
			root->BF = 0;
		}
	}
	else		// root node with BF == -1
	{
		root = root->left;
		old->left = root->right;
		root->right = old;
		if (root->BF == 0)
		{
			old->BF = 0;
			root->BF = 1;
		}
		else if (root->BF == -1)					// new root carry left side more, rotate right
			root->BF = old->BF = 1;				// old and new root node carry right child
		else			// new root = 1
		{
			old->BF = 0;								// old root node become height balanced
			root->BF = 2;							// new root now carray right more 
		}
	}
	return 0;
}

/*
Perform a left rotate

Return BF 0 as already balanced
*/
template<class type>
bool AVL_left_rotate(node_avl<type>*& root)
{
	node_avl<type> * old = root;
	if (root->BF == 2)		// root node with BF == 2
	{
		root = root->right;
		if (root->BF == -1)		// root's right child with BF == -1, perform right rotate for its right child first
			AVL_right_rotate(root);

		old->right = root->left;
		root->left = old;
		if (root->BF == 0)
		{
			root->BF = -1;
			old->BF = 1;
		}
		else if (root->BF == 1)
		{
			old->BF = 0;						// old root node become height balanced
			root->BF = 0;
		}
		else										// new root BF == 2
		{
			old->BF = -1;					// old root node carry left child
			root->BF = 0;
		}
	}
	else		// root node with BF == 1
	{
		root = root->right;
		old->right = root->left;
		root->left = old;
		if (root->BF == 0)
		{
			old->BF = 0;
			root->BF = -1;
		}
		else if (root->BF == 1)						// new root carry right side more, rotate left
			root->BF = old->BF = -1;				// old and new root node carry left child
		else			// new root = -1
		{
			old->BF = 0;								// old root node become height balanced
			root->BF = -2;							// new root now carray left more 
		}
	}
	return 0;
}

 

Deletion function of AVL tree

Process:
1. Same process as BST, go to find the node to be deleted.
2. Replace with and delete the inorder successor.
2. On the way back after removing a leaf, update node’s BF as necessary.
3. If node become 2, -2, do rotation.
4. After rotation, if node’s BF become 0, height reduced, update parents nodes’ BF on the way back.

 

This operation require 5 functions:

1. A wrapper delete function having a global flag whether to change BF
2. A recursive traversal function
3. Right rotate function
4. Left rotate function
5. Remove and supply the smallest element of a subtree (Finding inorder successor)

 

/*
A wrapper function for deletion of AVL tree
*/
template<class type>
bool AVL_remove(const type & to_remove, node_avl<type>*& root)
{
	bool change_BF = 1;
	return AVL_remove(to_remove, root, change_BF);
}

/*
A recursion function for the remove function

Return if it succeed to delete a node 
*/
template<class type>
bool AVL_remove(const type & to_remove, node_avl<type>*& root, bool &change_BF)
{
	if (root)
	{
		if (to_remove == *(root->data))
		{
			if (root->left && root->right)				// node with both child
			{
				// replace with the left most node of the root's right subtree (take out 1 from right)
				AVL_remove_supply_smallest(root->data, root->right, change_BF);	
				if (change_BF)
				{
					if (root->BF == 0)
						change_BF = 0;		// this root's BF was 0, after delete a child, no need to change later nodes' BF

					--(root->BF);

					if (root->BF == -2)					// right subtree - 1,  balance factor = -2, right rotate 
					{
						AVL_right_rotate(root);
						if (root->BF != 0)					// after rotate, root's still not balanced, height was not reduced
							change_BF = 0;				// no need to change later nodes' BF
					}
				}
			}
			else if (!root->left && !root->right)		// end leaf
			{
				delete root->data;
				delete root;
				root = NULL;
			}
			else			// node carry left or right child
			{
				node_avl<type> *del = root;
				root = ((root->left) ? root->left : root->right);
				delete del->data;
				delete del;
			}

			return 1;
		}
		else if (to_remove < *(root->data))
		{
			bool result = AVL_remove(to_remove, root->left, change_BF);
			if (result && change_BF)
			{
				if (root->BF == 0)
					change_BF = 0;		// this root's BF was 0, after delete a child, no need to change later nodes' BF

				++(root->BF);

				if (root->BF == 2)						// left subtree - 1, balance factor = 2, left rotate 
				{
					AVL_left_rotate(root);
					if (root->BF != 0)						// after rotate, root's still not balanced, height was not reduced
						change_BF = 0;					// no need to change later nodes' BF
				}
			}

			return result;
		}
		else
		{
			bool result = AVL_remove(to_remove, root->right, change_BF);
			if (result && change_BF)
			{
				if (root->BF == 0)
					change_BF = 0;		// this root's BF was 0, after delete a child, no need to change later nodes' BF

				--(root->BF);

				if (root->BF == -2)					// right subtree - 1,  balance factor = -2, right rotate 
				{
					AVL_right_rotate(root);
					if (root->BF != 0)					// after rotate, root's still not balanced, height was not reduced
						change_BF = 0;				// no need to change later nodes' BF
				}
			}
			return result;
		}
	}

	return 0;
}

/*
Remove the smallest item and supply it back by parameter

replace with the left most node of the root's right subtree (take out 1 from right)
*/
template<class type>
bool AVL_remove_supply_smallest(type *&receive, node_avl<type>* &root, bool & change_BF)
{
	if (root)
	{
		if (root->left)
		{
			AVL_remove_supply_smallest(receive, root->left, change_BF);
			if (change_BF)
			{
				if (root->BF == 0)		// this root's BF was 0
					change_BF = 0;		// after delete a child, no need to change later nodes' BF

				++(root->BF);

				if (root->BF == 2)						// left subtree - 1, balance factor = 2, left rotate 
				{
					AVL_left_rotate(root);
					if (root->BF != 0)						// after rotate, root's still not balanced, height was not reduced
						change_BF = 0;					// no need to change later nodes' BF
				}
			}
		}
		else
		{
			node_avl<type>* del = root;
			delete receive;
			receive = root->data;
			root = root->right;
			delete del;
		}

		return 1;
	}

	return 0;
}

 

AUTHOR : kanra
EMAIL : karawakara@gmail.com
Working on Networking, Web Development, Software Development, Server-side deployment. Having fun on doing experiments on new technologies.
Related Posts