AVL Trees – Rotation and Traversals in C++ 

In this sample C++ assignment, our expert is demonstrating to students the concepts in the following areas: –

  • Implementation of AVL trees.
  • Working of AVL rotation.
  • How traversals are done on trees.
  • Intensions are to make students practice more with template classes and asserts for testing.

SOLUTION: –

#include <iostream>

#include <string>

#include <cassert>

#include <vector>

// local includes

#include “AVLTree.h”

#include “Data.h”

using namespace std;

void testDoubleData(){

// testing getData

DoubleData d1 {};

DoubleData d2 {5};

assert (d1.getData() == 0); // default value

assert (d2.getData() == 5); // testing 1-arg constructor

DoubleData d3 {d2};

assert (d3.getData() == 5); // testing copy constructor

DoubleData d4 {*(new DoubleData(3))};

assert (d4.getData() == 3); // testing move constructor

// testing setData

double y = 7.5;

d1.setData(y);

assert (d1.getData() == 7.5);

d1.setData(8.5);

assert (d1.getData() == 8.5);

// testing compare, should be a.compare(b) = a-b

assert (d1.compare(d2) == 3.5);

}

void testAVLTree(){

AVLTree<DoubleData> a {};

std::vector<DoubleData*> v {5, new DoubleData{}};

assert (a.getHeight() == 0 || a.getHeight() == -1);

double counter = 0;

std::cout << “testing insertion and single rotation cases: ” << std::endl;

for (auto& x : v){

x = new DoubleData(counter);

a.insert(*x);

/* These test all the single rotations */

if (counter == 1) {assert(a.getHeight() == 1);}

if (counter == 2) {assert(a.getHeight() == 1);}

if (counter == 3) {assert(a.getHeight() == 2);}

if (counter == 4) {assert(a.getHeight() == 2);}

counter++;

}

std::cout << std::endl;

std::cout << “testing double rotation cases: ” << std::endl;

a.insert(DoubleData(2.5));

assert(a.getHeight() == 2);

a.insert(DoubleData(3.5));

a.insert(DoubleData(1.5));

a.insert(DoubleData(1.2));

a.insert(DoubleData(1.7));

a.insert(DoubleData(-1));

a.insert(DoubleData(0.5));

a.insert(DoubleData(1.3));

a.insert(DoubleData(1.1));

a.insert(DoubleData(1.6));

a.insert(DoubleData(-2));

a.insert(DoubleData(1.05));

assert(a.getHeight() == 4);

std::cout << std::endl;

std::cout<<“testing traversals:”<<std::endl;

a.printPreorder();

a.printInorder();

a.printPostorder();

a.printLevelOrder();

std::cout << std::endl;

std::cout << “removing 2.5:” << std::endl;

a.remove(DoubleData(2.5));

a.printLevelOrder();

std::cout << std::endl;

std::cout << “removing 1.5:” << std::endl;

a.remove(DoubleData(1.5));

a.printPostorder();

std::cout << std::endl;

// // testing copy constructor

AVLTree<DoubleData> b {a};

cout << “should be same:” << endl;

a.printPostorder();

b.printPostorder();

std::cout << std::endl;

a.empty();

cout << “should be empty now:” << endl;

assert (a.getHeight() == -1 ||      // a null tree can have height -1 or 0,

a.getHeight() == 0);    // which is subject to preference and usage

a.printPostorder();

std::cout << “end of test”<< std::endl;

}

int main (int argc, char* argv []){

testDoubleData();

testAVLTree();

std::cout << “end of main”<< std::endl;

return 0;

}

#ifndef AVLTREE_H

#define AVLTREE_H

#include “Data.h”

template <typename T>

class AVLTree {

private:

struct AVLNode {

AVLNode* leftChild;

AVLNode* rightChild;

T* data;

int duplicates; // used if there are duplicate values in the tree

// instead of changing rotation rules

int height;

AVLNode () :      // default constructor

leftChild {nullptr},

rightChild {nullptr},

data {nullptr},

duplicates {0},

height {0} {};

~AVLNode () = default;

AVLNode (T& value) :

leftChild {nullptr},

rightChild {nullptr},

duplicates {0},

height {0} {

data = new T{value};

};

AVLNode (T&& value):

leftChild {nullptr},

rightChild {nullptr},

duplicates {0},

height {0} {

data = new T{value};

}

AVLNode (T& value, AVLNode* left, AVLNode* right) :

leftChild {left},

rightChild {right},

duplicates {0},

height {0} {

data = new T{value};

};

AVLNode (T&& value, AVLNode* left, AVLNode* right) :

leftChild {left},

rightChild {right},

duplicates {0},

height {0} {

data = new T{value};

}

};

AVLNode* root;

// accessors ————————————————————-

// Utility function for getting a height

int height(AVLNode *t) const {

return t == nullptr ? -1 : t->height;

}

// will return the height of a given AVLNode*. Look at the definition for

// height. -1 if the tree is empty, or max height of children + 1.

// Must use recursion, since it counts leaves-up and we start traversals

// at root.

int getHeight(AVLNode* node) const {

if (node == nullptr)

return 0;

int leftHeight = getHeight(node->leftChild);

int rightHeight = getHeight(node->rightChild);

if (leftHeight > rightHeight)

return leftHeight + 1;

return rightHeight + 1;

}

// returns the depth from the current subtree (node is subroot)

// must use recursion.

int getDepthAux(const T& value, AVLNode* node) const {

if (node == nullptr)

return 0;

if (value < *node->data)

return 1 + getDepthAux(value, node->leftChild);

if (value > *node->data)

return 1 + getDepthAux(value, node->rightChild);

return 1;

}

// driver function for getDepthAux(T&,AVLNode*), which does the recursion.

// getDepth(T&,AVLNode*) does an extra check for node not found in tree.

int getDepth(const T& value, AVLNode* node) const {

if (!findNode(value, node)){

return -1;  // return -1 if node does not exist in tree

} else {

return getDepthAux(value, node);

}

}

// returns the AVLNode* that points to the node containing the

// parameter value in its data member.

// the node parameter is the root of the current subtree.

// Must use recursion.

AVLNode* findNode(const T& value, AVLNode* node) const {

if (node == nullptr)

return nullptr;

if (value < *node->data)

return findNode(value, node->leftChild);

if (value > *node->data)

return findNode(value, node->rightChild);

return node;

}

// returns the AVLNode* that points to the node containing the

// parameter value in its data member.

AVLNode* findNode(const T& value) const {

return findNode(value, root);

}

// method to clone a subtree and return it.

AVLNode* clone (AVLNode* node) const {

if (!node){

return nullptr;

} else {

AVLNode* temp = new AVLNode (*node->data,

clone(node->leftChild),

clone(node->rightChild));

temp->duplicates = node->duplicates;

temp->height = getHeight(node);

return temp;

}

}

// Possibly several functions to be used by printing traversal functions

// (below). These functions may need to know what the last leaf in a

// subtree is to print nicely (by my standards, anyway).

// CODE HERE

// should print the tree in a preorder traversal

void printPreorder(AVLNode* node) const {

if (node == nullptr)

return;

std::cout << *(node->data) << ” “;

printPreorder(node->leftChild);

printPreorder(node->rightChild);

}

// should print the tree in an inorder traversal

void printInorder(AVLNode* node) const {

if (node == nullptr)

return;

printInorder(node->leftChild);

std::cout << *(node->data) << ” “;

printInorder(node->rightChild);

}

// should print the tree in a postorder traversal

void printPostorder(AVLNode* node) const {

if (node == nullptr)

return;

printPostorder(node->leftChild);

printPostorder(node->rightChild);

std::cout << *(node->data) << ” “;

}

// mutators ————————————————————

// inserts a new value into the given subtree with node as the root.

// If the value already exists, just incrememnt the duplicates counter.

// Else, create memory for it and place pointers appropriately.

// Must use recursion.

void insert(T& x, AVLNode* & t){

if (t == nullptr)

t = new AVLNode(x, nullptr, nullptr);

else if (x < *(t->data))

insert(x, t->leftChild);

else if (x > *(t->data))

insert(x, t->rightChild);

else

{

t->duplicates++;

return;

}

balance(t);

}

// will balance the tree with node as the offending root, like

// alpha in our class discussions. Should call onf of the rotate functions.

// Don’t forget to set the height at the end!

void balance(AVLNode* & t){

if (t == nullptr)

return;

if (height(t->leftChild) – height(t->rightChild) > 1)

if (height(t->leftChild->leftChild) >= height(t->leftChild->rightChild))

rotateLeft(t);

else

rotateDoubleLeft(t);

else

if (height(t->rightChild) – height(t->leftChild) > 1)

if (height(t->rightChild->rightChild) >= height(t->rightChild->leftChild))

rotateRight(t);

else

rotateDoubleRight(t);

t->height = max(height(t->leftChild), height(t->rightChild)) + 1;

}

// Return the higher value

int max(int val1, int val2) {

return val1 > val2 ? val1 : val2;

}

// Rotate binary tree node with left child, i.e. a single rotation

// for case 1. Update the heights, and set new root.

void rotateLeft(AVLNode*& k2){

AVLNode *k1 = k2->leftChild;

k2->leftChild = k1->rightChild;

k1->rightChild = k2;

k2->height = max(height(k2->leftChild), height(k2->rightChild)) + 1;

k1->height = max(height(k1->leftChild), k2->height) + 1;

k2 = k1;

}

// Rotate binary tree node with right child, i.e. a single rotation

// for case 4. Update the heights, and set new root.

void rotateRight(AVLNode*& k1){

AVLNode *k2 = k1->rightChild;

k1->rightChild = k2->leftChild;

k2->leftChild = k1;

k1->height = max(height(k1->leftChild), height(k1->rightChild)) + 1;

k2->height = max(height(k2->rightChild), k1->height) + 1;

k1 = k2;

}

// Double rotate binary tree node: first left child with its right

// child, then subroot with its new left child (was grandchild previously).

// I.e. rotation case 2. Update the heights, and set new root.

void rotateDoubleLeft(AVLNode*& node){

rotateRight(node->leftChild);

rotateLeft(node);

}

// Double rotate binary tree node: first left child with its right

// child, then subroot with its new left child (was grandchild previously).

// I.e. rotation case 2. Update the heights, and set new root.

void rotateDoubleRight(AVLNode*& node){

rotateLeft(node->rightChild);

rotateRight(node);

}

// Find the smallest item in a subtree

AVLNode * findMin(AVLNode *t) const {

if (t == nullptr)

return nullptr;

if (t->leftChild == nullptr)

return t;

return findMin(t->leftChild);

}

// removes a given value from the tree. If the Node containing the value

// has duplicates, decrement the duplicates. Else deallocate the memory and

// recursively call remove to fix the tree, as discussed in class.

void remove(T& x, AVLNode*& t){

if (t == nullptr)

return;

if (x < *t->data)

remove(x, t->leftChild);

else if (*t->data < x)

remove(x, t->rightChild);

else if (t->leftChild != nullptr && t->rightChild != nullptr) {

t->data = findMin(t->rightChild)->data;

remove(*t->data, t->rightChild);

} else {

AVLNode *oldNode = t;

t = (t->leftChild != nullptr) ? t->leftChild : t->rightChild;

delete oldNode;

}

balance(t);

}

// private function to recursively empty

void empty(AVLNode* node){

if (node == nullptr)

return;

empty(node->leftChild);

empty(node->rightChild);

delete node;

}

// Recursive print level order

void printLevelOrder(AVLNode *root, int level) {

if (root == nullptr)

return;

if (level == 1)

std::cout << *root->data << ” “;

else {

printLevelOrder(root->leftChild, level – 1);

printLevelOrder(root->rightChild, level – 1);

}

}

public:

AVLTree():

root {nullptr} {};

~AVLTree(){

empty();

}

// copy constructor: should copy all of the data from the other tree

// into this tree.

AVLTree(const AVLTree<T>& other){

root = clone(other.root);

}

// accessors ——————————————————–

int getHeight() const {

if (root == nullptr)

return 0;

return root->height;

}

// searches the tree for a value. If it is found, the height

// is returned. If not, then -1 is returned.

int getHeight(const T& value) const {

AVLNode* node = findNode(value);

return node ? node->height : -1; // ternary operator

}

// returns the depth for the whole tree. should be 0 if the

// tree is nonempty, and -1 if it is empty.

int getDepth() const {

if (root){

return 0;

} else {

return -1;

}

}

// returns the depth for a given value.

// should be -1 if tree is empty, or the number of steps

// down from root node if not.

int getDepth(T& value) const {

if (!root){

return -1;

} else {

return getDepth(value, root);

}

}

// will return the balance factor of a value in the tree.

// if the value does not exist, return -128 (the lowest value for

// a 1-byte char). If it does exist, return the balance factor.

char getBalanceFactor(T& value) const {

AVLNode *t = findNode(value);

if (t == nullptr)

return -128;

return height(t->leftChild) – height(t->rightChild);

}

// driver function to call the private preorder traversal

void printPreorder(){

std::cout << “[“;

printPreorder(root);

std::cout << “]” << std::endl;

}

// driver function to call the private preorder traversal

void printInorder(){

std::cout << “[“;

printInorder(root);

std::cout << “]” << std::endl;

}

// driver function to call the private preorder traversal

void printPostorder(){

std::cout << “[“;

printPostorder(root);

std::cout << “]” << std::endl;

}

// should print the tree in a level-order traversal (NOT driver function)

void printLevelOrder(){

std::cout << “[“;

if (root != nullptr) {

int h = root->height + 1;

for (int i = 1; i <= h; i++)

printLevelOrder(root, i);

}

std::cout << “]” << std::endl;

}

// mutators —————————————————–

// call private balance(1) on tree

void balance(){

balance(root);

}

// calls private remove function to remove starting at root

void remove(T& value){

remove(value, root);

}

void remove(T&& value){

T temp = T{value};

remove(temp);

}

// driver function for emptying the tree, since there is no public access

// to root of tree (as many other functions do in this file)

void empty(){

empty(root);

root = nullptr;

}

// calls private insert function to insert starting at root

void insert(T& value){

insert(value, root);

}

void insert(T&& value){

T temp = T{value};

insert(temp);

}

// Prints a tree formatted

void debugPrintInorder() {

debugPrintInorder(root, 0);

}

// should print the tree in an inorder traversal formatted to see visual

void debugPrintInorder(AVLNode* node, int tabs) const {

if (node == nullptr)

return;

debugPrintInorder(node->rightChild, tabs + 1);

for (int i = 0; i < tabs; i++)

std::cout << ”    “;

std::cout << *(node->data) << ” ” << std::endl;

debugPrintInorder(node->leftChild, tabs + 1);

}

};

#endif