Back to Code List
c++

Adelson-Velskii and Landis' (AVL) Tree

This a an implementation of an AVL tree with several helper functions and output options. AVL trees are an interesting self-balancing binary tree structure.

   main.cpp

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

ofstream outputFile; //outputFile is defined as a global variable

struct AvlNode
{
	int key;
	int height;
	AvlNode *left;				
	AvlNode *right;				

	AvlNode (int key1, int height1 = 0, AvlNode *left1 = NULL, AvlNode *right1 = NULL)
	{
		key = key1;
		height = height1;
		left = left1;
		right = right1;
	}
};

class AvlTree 
{
	private:
		AvlNode * root;
		void destroySubTree(AvlNode * v);//destroy a subtree rooted at v
		void displayPreOrder(AvlNode *);//pre-order traversal
		void displayInOrder(AvlNode *);//in-order traversal
		void displayPostOrder(AvlNode *);//post-order traversal
		void remove(AvlNode * &, int);//remove
		void insert(AvlNode * &, int);//insert
		void balance(AvlNode * &); //make the tree balanced after each insert/remove
		void rightRotate (AvlNode * &);//right rotation
		void leftRotate (AvlNode * &);//left rotation
		void doubleLeftRightRotate (AvlNode * &);//left right double rotation
		void doubleRightLeftRotate (AvlNode * &);//right left double rotation

	public:
		AvlTree() { root = NULL; }
		~AvlTree() { destroySubTree(root); }
		AvlNode * search(int);
		void displayPreOrder() { displayPreOrder(root); }
		void displayInOrder() { displayInOrder(root); }
		void displayPostOrder() { displayPostOrder(root); }
		void insert(int x) { insert(root,x); }//insert a new key x
		void remove(int x) { remove(root,x); }//remove a key x
		int getHeight(AvlNode * v);//return the height of node v
		int getTreeHeight() {return getHeight(root);}//return the height of the tree
		int getRoot() {return root->key;}//return the root
};

int AvlTree::getHeight(AvlNode * v)
{
	if (v == NULL)
		return -1;
	else
		return v->height;
}

void AvlTree::destroySubTree(AvlNode *v)
{
	if (v == NULL)
		return;
	else
	{
		destroySubTree(v->left);
		destroySubTree(v->right);
		delete v;
	}
}

void AvlTree::insert(AvlNode * & v, int x)
{
	if (v == NULL)
		v = new AvlNode(x);
	else if (x == v->key)
		return;
	else if (x < v->key)
		insert(v->left, x);
	else
		insert(v->right, x);

	balance(v);
}

void AvlTree::balance(AvlNode * & v)
{
	if (v == NULL) return;
	if ((getHeight(v->left) - getHeight(v->right)) > 1) {
		if (getHeight(v->left->left) >= getHeight(v->left->right))//left-left
			rightRotate(v);
		else//left-right case
			doubleLeftRightRotate(v);
	}
	if ((getHeight(v->right) - getHeight(v->left)) > 1) {
		if (getHeight(v->right->right) >= getHeight(v->right->left))//right-right
			leftRotate(v);
		else//right-left case
			doubleRightLeftRotate(v);
	}
	v->height = 1+max(getHeight(v->left), getHeight(v->right));
}

void AvlTree::rightRotate (AvlNode * & k2)
{
	AvlNode* leftNode = k2->left;
	k2->left = leftNode->right;
	leftNode->right = k2;

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

	k2 = leftNode;
}

void AvlTree::leftRotate (AvlNode * & k1)
{
	AvlNode* rightNode = k1->right;
	k1->right = rightNode->left;
	rightNode->left = k1;

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

	k1 = rightNode;
}

void AvlTree::doubleLeftRightRotate (AvlNode * & v)
{
	//rotate right up (to the left), then rotate same node up again (to the right)
	//call leftRotate, then call rightRotate
	leftRotate(v->left);
	rightRotate(v);
}

void AvlTree::doubleRightLeftRotate (AvlNode * & v)
{
	//rotate left up (to the right), then rotate same node up again (to the left)
	//call rightRotate, then call leftRotate
	rightRotate(v->right);
	leftRotate(v);
}

void AvlTree::displayPreOrder(AvlNode *v)
{
	if (v != NULL)
	{
		cout << v->key << "  ";
		outputFile << v->key << "  ";
		displayPreOrder(v->left);
		displayPreOrder(v->right);
	}
}

void AvlTree::displayInOrder(AvlNode *v)
{
	if (v != NULL)
	{
		displayInOrder(v->left);
		cout << v->key << "  ";
		outputFile << v->key << "  ";
		displayInOrder(v->right);
	}
}

void AvlTree::displayPostOrder(AvlNode *v)
{
	if (v != NULL)
	{
		displayPostOrder(v->left);
		displayPostOrder(v->right);
		cout << v->key << "  ";
		outputFile << v->key << "  ";
	}
}

AvlNode * AvlTree::search(int x)
{
	AvlNode *v = root;
	while (v != NULL && v->key != x)
	{
		if (x < v->key)
			v = v->left;
		else
			v = v->right;
	}

	if (v != NULL)
		return v;
	else
		return NULL;
}

void AvlTree::remove(AvlNode * & v, int x)
{
	if (v == NULL)
		return;
	if (x < v->key)
		remove(v->left, x);
	else if (x > v->key)
		remove(v->right, x);
	else//x == v->key
	{
		// if at least one child is NULL
		if (v->left == NULL || v->right == NULL)
		{
			AvlNode * garbageNode = v;
			if (v->right == NULL)
				v = v->left;
			else
				v = v->right;
		}
		else // v has two children
		{
			AvlNode * u = v->right;
			//find the smallest key on the right subtree of v
			while(u->left != NULL)
				u = u->left;
			//assign the key value of u to v
			v->key = u->key;
			remove(v->right,v->key);
		}
	}

	balance(v);
}

int main()
{
	AvlTree tree;
	
	//open the input file
	ifstream inputFile;
	inputFile.open("input.txt");
	if (!inputFile)
		cout << "Error opening the input file " << endl;
	
	//open the output file, outputFile is defined as a global variable
	outputFile.open("output.txt");
	if (!outputFile)
		cout << "Error opening the output file " << endl;

	//read operations from the input file
	string op;
	int x;
	while(inputFile >> op)
	{
		if (op == "insert")
		{
			inputFile >> x; // read the value x for insert
			tree.insert(x);
		}
		else if (op == "remove")
		{
			inputFile >> x; // read the value x for remove 
			tree.remove(x);
		}
		else
			cout << "Error reading opeartions"; 
	}

	//print the pre-odrder traversal to both screen and the outputfile
	cout << "The pre-order traversal list is: " << endl;
	outputFile << "The pre-order traversal list is: " << endl;
	tree.displayPreOrder();
	cout << endl;
	outputFile << endl;

	//print the in-order traversal to both screen and the outputfile
	cout << "The in-order traversal list is: " << endl;
	outputFile << "The in-order traversal list is: " << endl;
	tree.displayInOrder();
	cout << endl;
	outputFile << endl;
	
	//print the root and its height to both screen and the output file 
	cout << "The root is: " << tree.getRoot() << endl;
	outputFile << "The root is: " << tree.getRoot() << endl;
	cout << "The height of the tree is: " << tree.getTreeHeight() << endl;
	outputFile << "The height of the tree is: " << tree.getTreeHeight() << endl;
	
	/* The following commented code may help you debug your program.
	 * You may change "16" to other keys as you need. 
	AvlNode * v = tree.search(16);
	if (v != NULL)
	{
	    cout << "The key is found. Its height is: " << tree.getHeight(v) << endl;
		if (v->left != NULL) 
			cout << "It's left child is: " << v->left->key << "." << endl;
		else
			cout << "It does not have a left child. " << endl;
		
		if (v->right != NULL) 
			cout << "It's right child is: " << v->right->key << "." << endl;
		else
			cout << "It does not have a right child. " << endl;
	}
	else
		cout << "The key is not found." << endl;
	*/


	inputFile.close();
	outputFile.close();

	return 0;
}
    

   input.txt

insert 1
insert 2
insert 3
insert 4
insert 5
insert 6
insert 7
insert 16
insert 15
insert 14
insert 13
insert 12
insert 11
insert 10
insert 8
insert 9
remove 4
remove 5
remove 6
insert 20
    

   output.txt

The pre-order traversal list is: 
11  7  2  1  3  9  8  10  15  13  12  14  16  20  
The in-order traversal list is: 
1  2  3  7  8  9  10  11  12  13  14  15  16  20  
The root is: 11
The height of the tree is: 3