     ## An In-Depth Look at AVL Trees Part I 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 Simple single rotation. It gets a little more complicated when you have a fuller tree, see below:

Right Right Again 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. 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. 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). Left Right

The opposite of the Right Left use case, rotate left, rotate right: 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 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 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>
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;

//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>
if(node->getData() < itrNode->getData()){
DEBUG_OUT("Entering left subtree");
if(itrNode->getLeftChild() == nullptr){
itrNode->setLeftChild(node);
node->setParent(itrNode);
}
else {
}
}
else {
DEBUG_OUT("Entering right subtree");
if(itrNode->getRightChild() == nullptr){
itrNode->setRightChild(node);
node->setParent(itrNode);
}
else {
}
}
}

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.displayFullNodeInfo();
tree1.displayFullNodeInfo();
tree1.displayFullNodeInfo();
tree1.displayFullNodeInfo();

//left left default case
AVLTree<int> tree2(10);
tree2.displayFullNodeInfo();
tree2.displayFullNodeInfo();

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

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

```

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

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

Happy coding!

S M T W T F S
12345
6789101112
13141516171819
202122232425 26
27282930

### Recent Entries

• • • • • • • • • • ### 1 user(s) viewing

1 Guests
0 member(s)
0 anonymous member(s)