Subscribe to Stuck in an Infiniteloop        RSS Feed
-----

An In-Depth Look at AVL Trees Part I

Icon Leave Comment
Holy crap! It's been four years since the last one of these tutorials? What have I been doing with my life?!?!

Who knows. Without any further ado, here we go:

AVL Trees

Quote

In computer science, an AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. It was the first such data structure to be invented. 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. Lookup, 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 a quick refresher on binary search trees, check out this cool guy's blog post.


Part I

Insertion

It got complicated doing all the use cases for this, so I left deletion for another post.

The key piece of data in an AVL tree node is the balance factor (seen in parentheses in the below diagrams). It tells us whether or not the tree is unbalanced at that node. The balance factor is calculated by (height(node.leftChild) - height(node.rightChild)).

0 means it is a leaf node or has the same height tree on each side
1/-1 means left/right subtree is one node higher
2/-2 means left/right subtree is two nodes higher

When we hit 2/-2 we have to "rebalance" the tree. This is done by one or two rotations at the subtree rooted at the unbalanced node. There are four base cases:

Left Right
Left Left
Right Left
Right Right


The "it's so nice, they named it twice" are the true "base" cases. They only require one rotation to correct the tree. The other two (not as nice) require two rotations. The following illustrate the code that is below. Pictures!

Right Right

Attached Image

Simple single rotation. It gets a little more complicated when you have a fuller tree, see below:

Right Right Again

Attached Image

In the event that the left subtree is not empty on the rotation, we have to hold onto it and attach it as the right child in the left subtree of the new root.

Right Left

In this case, we have a node on the right of the unbalanced node with a left node. We'll need to rotate the right child to the right and then rotate the unbalanced node to the left.

Attached Image

In the code for the cases that require two rotations, a bool flag is passed in to tell the function whether or not this is the first in a series of rotations. The reason is, in the simple one rotation use case, you need to set certain children, but here you don't because the tree is not yet "ready".

Left Left

The beauty of this tree is that the operations are mirrored! Pretty much the same operation/code, but reversed. This examples shows a single rotation that is not the actual root of the tree, but another node. This node is the "root" of that subtree and we rotate once accordingly.

Attached Image

Left Left Again

The same as the above left let example except we add one more node that requires a dangling node while we rotate at the root and then reattach. (Same example as the right right more complicated one).

Attached Image

Left Right

The opposite of the Right Left use case, rotate left, rotate right:

Attached Image


Code:

Node.h
#ifndef NODE_H
#define NODE_H

#include <memory>
#include <ostream>

template<class T>
class Node {
private:
	T data;
	int balanceFactor;
	int height; //heiht of the subtree this node is a root of
	std::shared_ptr<Node<T>> left;
	std::shared_ptr<Node<T>> right;
	std::shared_ptr<Node<T>> parent;
	Node& operator=(Node&);
public:
	Node();
	Node(T);
	Node(const Node&);

	int getBalanceFactor()						{return balanceFactor;}
	int getHeight()								{return height;}
	T getData()									{return data;};
	std::shared_ptr<Node<T>> getLeftChild()		{return left;};
	std::shared_ptr<Node<T>> getRightChild()		{return right;};
	std::shared_ptr<Node<T>> getParent()			{return parent;};

	void setBalanceFactor(int);
	void setHeight(int);
	void setLeftChild(std::shared_ptr<Node<T>>);
	void setRightChild(std::shared_ptr<Node<T>>);
	void setParent(std::shared_ptr<Node<T>>);
	void setData(T);

	friend std::ostream& operator <<(std::ostream& out, const Node<T>& node){
		out << node.data << " bf:" << node.balanceFactor << " h: " << node.height << std::endl;
		return out;
	}
};

template<class T>
Node<T>::Node(){
	data = 0;
	parent = left = right = nullptr;
	balanceFactor = height = 0;
}

template<class T>
Node<T>::Node(T element){
	data = element;
	parent = left = right = nullptr;
	balanceFactor = height = 0;
}

template<class T>
Node<T>::Node(const Node<T>& cp){
	data = cp.data;
	parent = cp.parent;
	left = cp.left;
	right = cp.right;
	balanceFactor = cp.balanceFactor;
	height = cp.height;
}

template<class T>
void Node<T>::setBalanceFactor(int val){
	balanceFactor = val;
}

template<class T>
void Node<T>::setHeight(int val){
	height = val;
}

template<class T>
void Node<T>::setLeftChild(std::shared_ptr<Node<T>> node){
	left = node;
}

template<class T>
void Node<T>::setRightChild(std::shared_ptr<Node<T>> node){
	right = node;
}

template<class T>
void Node<T>::setParent(std::shared_ptr<Node<T>> node){
	parent = node;
}

template<class T>
void Node<T>::setData(T element){
	data = element;
}

#endif




AVLTree.h
#ifndef AVL_TREE_H
#define AVL_TREE_H

#include "Node.h"
#include <iostream>
#include <set>
#define DEBUG

//nifty trick to enforce a semicolon on the end of lines using this macro
//DEBUG_OUT(whatever); in code
#ifdef DEBUG
#define DEBUG_OUT(x) \
	do { std::cout << x << std::endl; } while(false)
#endif

#define LOG_LINE(x) \
	do { std::cout << x << std::endl;} while(false)

#define LOG(x) \
	do { std::cout << x;} while(false)

template <class T>
class AVLTree {
private:
	std::shared_ptr<Node<T>> root;
	std::shared_ptr<Node<T>> curNode;
	std::shared_ptr<Node<T>> earliestUnbalancedNode;
	int height;
	std::set<T> elements;
	bool unbalanced;

	//private helpers for cleaner recursion
	void add(std::shared_ptr<Node<T>>, std::shared_ptr<Node<T>>);
	void remove(std::shared_ptr<Node<T>>, std::shared_ptr<Node<T>>);
	void preOrder(std::shared_ptr<Node<T>>);
	void postOrder(std::shared_ptr<Node<T>>);
	void inOrder(std::shared_ptr<Node<T>>);
	void inOrderFullNode(std::shared_ptr<Node<T>>);

	void recursiveHeightCalc(std::shared_ptr<Node<T>>);
	int calculateSubtreeHeight(std::shared_ptr<Node<T>>);
	void balanceTree(std::shared_ptr<Node<T>>);
	void rotateLeft(std::shared_ptr<Node<T>>, bool firstOp = false);
	void rotateRight(std::shared_ptr<Node<T>>, bool firstOp = false);
public:
	AVLTree(T);
	~AVLTree();

	void addNode(T);
	void removeNode(T);
	void preOrderTraversal();
	void postOrderTraversal();
	void inOrderTraversal();
	void displayFullNodeInfo();

};



template <class T>
AVLTree<T>::AVLTree(T rootVal){
	root = std::make_shared<Node<T>>(rootVal);
	elements.insert(rootVal);
	curNode = root;
	height = 1;
	unbalanced = false;
}

template <class T>
AVLTree<T>::~AVLTree(){

}

template <class T>
void AVLTree<T>::addNode(T value){
	DEBUG_OUT("Adding node " << value);
	std::shared_ptr<Node<T>> newNode = std::make_shared<Node<T>>(value);
	//fucking dumb, I hate this crap, why does the compiler need the typename here?
	//worst random issue I run into frequently, "dependent name"
	//fine it could be a type, whatever. get your life together compiler
	std::pair<typename std::set<T>::iterator, bool> result;
	result = elements.insert(value);
	if (result.second == false){
		DEBUG_OUT("Element " << value << " already in tree");
		return;
	}
	curNode = root;
	add(curNode, newNode);

	//calculate subtree heights to see if the tree became unbalanced after last insertion
	//balanceFactor = height (left subtree) - height (right subtree)
	//this function will assign BF to each node as it goes down

	recursiveHeightCalc(root);

	//at most one subtree can be -2/2/unbalanced
	if(unbalanced){
		DEBUG_OUT("Tree is unbalanced at node: " << earliestUnbalancedNode->getData());
		balanceTree(earliestUnbalancedNode);
		unbalanced = false;
		earliestUnbalancedNode = nullptr;
	}
}

template <class T>
void AVLTree<T>::rotateLeft(std::shared_ptr<Node<T>> node, bool firstOp){
	//node is the root of the unbalanced subtree
	//node becomes left child of its right child
	Node<T> temp(*node->getRightChild());
	std::shared_ptr<Node<T>> newRoot  = node->getRightChild(); //no new allocation
	newRoot->setLeftChild(node);
//	newRoot->setRightChild(temp.getRightChild()); //this is redundant
	node->setRightChild(nullptr);
	//in the event we are rotating the root of the tree, reassign handle and make parent nil
	if(root == node){
		DEBUG_OUT("node rotated left was tree root, reassigning");
		root = newRoot;
		newRoot->setParent(nullptr);
		//if we rotated the root, make its right child the left child of node->getRightChild
		if(temp.getLeftChild() != nullptr) newRoot->getLeftChild()->setRightChild(temp.getLeftChild());
	}
	else {
		DEBUG_OUT("Unbalanced root was not tree root");
		newRoot->setParent(node->getParent()); //non tree root case, grab next ancestor
		if(firstOp){
			newRoot->getParent()->setLeftChild(newRoot);
		}
		else {
			newRoot->getParent()->setRightChild(newRoot);
		}
	}
	node->setParent(newRoot);

	recursiveHeightCalc(root);
}

template <class T>
void AVLTree<T>::rotateRight(std::shared_ptr<Node<T>> node, bool firstOp){
	//node is the root of the unbalanced tree
	Node<T> temp(*node->getLeftChild());
	std::shared_ptr<Node<T>> newRoot  = node->getLeftChild(); //no new allocation
	newRoot->setRightChild(node);
	node->setLeftChild(nullptr);
	if(root == node){
		DEBUG_OUT("node rotated right was tree root, reassigning");
		root = newRoot;
		newRoot->setParent(nullptr);
		//if we rotated the root, make its left child the right child of node->getLeftChild
		if(temp.getRightChild() != nullptr) newRoot->getRightChild()->setLeftChild(temp.getRightChild());
	}
	else {
		DEBUG_OUT("Unbalanced root was not tree root");
		newRoot->setParent(node->getParent()); //non tree root case, grab next ancestor
		if(firstOp){
			newRoot->getParent()->setRightChild(newRoot);
		}
		else {
			newRoot->getParent()->setLeftChild(newRoot);
		}
	}
	node->setParent(newRoot);

	recursiveHeightCalc(root);
}

template <class T>
void AVLTree<T>::balanceTree(std::shared_ptr<Node<T>> node){
	//get rid of these checks by flagging which side of the tree we go down
	if(node->getBalanceFactor() == -2){
		DEBUG_OUT("Right subtree of this node is unbalanced");
		if(node->getRightChild()->getBalanceFactor() == -1){
			DEBUG_OUT("Right Right case");
			//one rotation to the left will fix the tree
			rotateLeft(node);
		}
		else {
			DEBUG_OUT("Right Left case");
			//rotate the child of the unbalanced subtree to the right then rotate left, bam done
			rotateRight(node->getRightChild(), true);
			rotateLeft(node);
		}
	}
	else{ //2
		DEBUG_OUT("Left subtree of this node is unbalanced");
		if(node->getLeftChild()->getBalanceFactor() == 1){
			DEBUG_OUT("Left Left case");
			//one rotation to the right will fix the tree
			rotateRight(node);
		}
		else {
			DEBUG_OUT("Left Right case");
			rotateLeft(node->getLeftChild(), true);
			rotateRight(node);
		}
	}
}

//this function calculates subtree heights and does balance factors
//originally this was going to be recursive, maybe do that in the future
template <class T>
int AVLTree<T>::calculateSubtreeHeight(std::shared_ptr<Node<T>> node){
	if(node->getLeftChild() == nullptr and node->getRightChild() == nullptr){
		node->setHeight(0);
		node->setBalanceFactor(0);
		return 1; //this isn't really necessary
	}
	else if(node->getLeftChild() != nullptr and node->getRightChild() == nullptr){
		node->setHeight(node->getLeftChild()->getHeight() + 1);
		node->setBalanceFactor((node->getLeftChild()->getHeight()+1)-0);//pointless math, but here for illustration
	}
	else if(node->getLeftChild() == nullptr and node->getRightChild() != nullptr){
		node->setHeight(node->getRightChild()->getHeight() + 1);
		node->setBalanceFactor(0-(node->getRightChild()->getHeight()+1));
	}
	else if(node->getLeftChild() != nullptr and node->getRightChild() != nullptr){
		node->setHeight(
				(node->getLeftChild()->getHeight() < node->getRightChild()->getHeight()) ?
						node->getRightChild()->getHeight() + 1 :
						node->getLeftChild()->getHeight() + 1
				);
		node->setBalanceFactor(node->getLeftChild()->getHeight() - node->getRightChild()->getHeight());
	}
	int bf = node->getBalanceFactor();
	DEBUG_OUT("node in calcsubtree: " << *node);
	if((bf == -2) or (bf == 2)){
		unbalanced = true;
		if(earliestUnbalancedNode == nullptr) earliestUnbalancedNode = node;
	}
}

template <class T>
void AVLTree<T>::removeNode(T value){
	if(elements.find(value) == elements.end()){
		LOG_LINE("Element " << value << " not in tree");
		return;
	}
	//do this later
}

template <class T>
void AVLTree<T>::add(std::shared_ptr<Node<T>> itrNode, std::shared_ptr<Node<T>> node){
	if(node->getData() < itrNode->getData()){
		DEBUG_OUT("Entering left subtree");
		if(itrNode->getLeftChild() == nullptr){
			itrNode->setLeftChild(node);
			node->setParent(itrNode);
		}
		else {
			add(itrNode->getLeftChild(), node);
		}
	}
	else {
		DEBUG_OUT("Entering right subtree");
		if(itrNode->getRightChild() == nullptr){
			itrNode->setRightChild(node);
			node->setParent(itrNode);
		}
		else {
			add(itrNode->getRightChild(), node);
		}
	}
}

template <class T>
void AVLTree<T>::recursiveHeightCalc(std::shared_ptr<Node<T>> node){
	if(node->getLeftChild() != nullptr) recursiveHeightCalc(node->getLeftChild());
	if(node->getRightChild() != nullptr) recursiveHeightCalc(node->getRightChild());
	calculateSubtreeHeight(node);
}

//****************************************************************
// TRAVERSAL
//****************************************************************
template <class T>
void AVLTree<T>::preOrder(std::shared_ptr<Node<T>> node){
	LOG(node->getData() << " ");
	if(node->getLeftChild() != nullptr) preOrder(node->getLeftChild());
	if(node->getRightChild() != nullptr) preOrder(node->getRightChild());
}

template <class T>
void AVLTree<T>::postOrder(std::shared_ptr<Node<T>> node){
	if(node->getLeftChild() != nullptr) preOrder(node->getLeftChild());
	if(node->getRightChild() != nullptr) preOrder(node->getRightChild());
	LOG(node->getData() << " ");
}

template <class T>
void AVLTree<T>::inOrder(std::shared_ptr<Node<T>> node){
	if(node->getLeftChild() != nullptr) preOrder(node->getLeftChild());
	LOG(node->getData() << " ");
	if(node->getRightChild() != nullptr) preOrder(node->getRightChild());
}

template <class T>
void AVLTree<T>::inOrderFullNode(std::shared_ptr<Node<T>> node){
	if(node->getLeftChild() != nullptr) inOrderFullNode(node->getLeftChild());
	LOG(*node);
	if(node->getRightChild() != nullptr) inOrderFullNode(node->getRightChild());
}

template <class T>
void AVLTree<T>::preOrderTraversal(){
	LOG_LINE("pre order traversal: ");
	preOrder(root);
	LOG_LINE("");
}

template <class T>
void AVLTree<T>::postOrderTraversal(){
	LOG_LINE("post order traversal: ");
	postOrder(root);
	LOG_LINE("");
}

template <class T>
void AVLTree<T>::inOrderTraversal(){
	LOG_LINE("in order traversal: ");
	inOrder(root);
	LOG_LINE("");
}

template <class T>
void AVLTree<T>::displayFullNodeInfo(){
	LOG_LINE("in order traversal full node info: ");
	inOrderFullNode(root);
}

#endif




main.cpp
#include <iostream>
#include <string>
#include "AVLTree.h"
using namespace std;

int main(){

	//right right default case
	AVLTree<int> tree1(5);
	tree1.addNode(10);
	tree1.addNode(15);
	tree1.displayFullNodeInfo();
	tree1.addNode(12);
	tree1.displayFullNodeInfo();
	tree1.addNode(16);
	tree1.displayFullNodeInfo();
	tree1.addNode(17);
	tree1.displayFullNodeInfo();

	//left left default case
	AVLTree<int> tree2(10);
	tree2.addNode(8);
	tree2.addNode(5);
	tree2.displayFullNodeInfo();
	tree2.addNode(4);
	tree2.addNode(3);
	tree2.addNode(2);
	tree2.displayFullNodeInfo();

	//default right left case
	AVLTree<int> tree3(3);
	tree3.addNode(5);
	tree3.addNode(4);
	tree3.displayFullNodeInfo();

	//default left right case
	AVLTree<int> tree4(5);
	tree4.addNode(3);
	tree4.addNode(4);
	tree4.displayFullNodeInfo();
	return 0;
}



------------------

Stay tuned for part II! [Probably after the holidays]

Happy coding!

0 Comments On This Entry

 

December 2017

S M T W T F S
     12
3456789
10111213 14 1516
17181920212223
24252627282930
31      

Tags

    Recent Entries

    Search My Blog

    5 user(s) viewing

    5 Guests
    0 member(s)
    0 anonymous member(s)