# First Swing at an AVL Tree Implementation in C++

I've implemented a simple AVL binary search tree. For no real reason I decided to implement this without multiplicity, so if we try to insert(5) twice, it's only stored once in the tree. I've also left out the in-order traversal and a few other methods I want to use this for, because I want to implement those elsewhere and just have the tree itself here.

I'd appreciate any and all comments relating to anything from how the code runs to how easy/difficult it is to read and maintain. I can take a beating - I'm new at this and want to improve as much as possible. Thanks in advance for your help.

#pragma once
#include "stdafx.h"
#include <cstdlib>
#include <algorithm>                    // For std::max.  I only use it in one place.  Should implement it myself in like 1 line.  "(a < b) ? a b" sort of thing.

template <class T>
struct Vertex {
T m_value;
int height;
Vertex * left;
Vertex * right;
Vertex * parent;
Vertex(T tee) { m_value = tee; height = 0; left = NULL; right = NULL; parent = NULL; }
};

template <class T>              // The only property we need is that T admits a total ordering.  User-made classes work as long as '<' is defined for them.
class AVL_Tree {
private:
Vertex<T> * m_root;
public:
AVL_Tree<T>() { m_root = NULL; }

Vertex<T> * findValue(T n) {          // Finds the value 'n' in the tree and returns a pointer to the vertex containing it, or NULL if it doesn't exist.
Vertex<T> * current = m_root;
if (m_root == NULL)
return NULL;                  // If the tree is empty, return NULL

while (current != NULL) {
if (current->m_value == n)          // Walk down the tree doing binary search.  If we find 'x', return a pointer to the vertex containing it.
return current;
else if (n > current->m_value)
current = current->right;
else if (n < current->m_value)
current = current->left;
}                                       // If this loop terminates without returning anything, then x is not in the tree.

return NULL;

}
bool isInTree(T x) {
return (this->findValue(x) != NULL);        // x is in the tree if and only if findValue returns something different from NULL
}
bool isLeaf(Vertex<T> * X) {
if (X == NULL)
return false;                                           // null pointers aren't leaves
return ((X->left == NULL) && (X->right == NULL));           // X is a leaf if and only if both children are null
}

int getHeight(Vertex<T> * X) {
if (X == NULL)
return -1;
else
return X->height;
}
int leftHeight(Vertex<T> * X) { return getHeight(X->left); }
int rightHeight(Vertex<T> * X) { return getHeight(X->right); }

void updateHeight(Vertex<T> * X) {      // Updates the height of the vertex X by adding 1 to the max of the heights of its children
X->height = std::max(getHeight(X->left), getHeight(X->right)) + 1;
}

// Next four methods:  Rotations for AVL update.  I forgot a few pointers the first time around, which resulted in the tree not working as intended.

void right_rotate(Vertex<T> * X) {
Vertex<T> * Y = X->left;
Vertex<T> * Z = X->parent;
if (Z != NULL) {
if (Z->left == X)
Z->left = Y;
else if (Z->right == X)
Z->right = Y;
}

X->left = Y->right;                      // There's no way Y is NULL since X is left-heavy whenever we call this method.
Y->right = X;
Y->parent = Z;
X->parent = Y;

updateHeight(X);
updateHeight(Y);
}

void other_right_rotate(Vertex<T> * X) {
Vertex<T> * Y = X->left;
Vertex<T> * B = Y->right;
Vertex<T> * Z = X->parent;
if (Z != NULL) {
if (Z->left == X)
Z->left = B;
else if (Z->right == X)
Z->right = B;
}

Vertex<T> * b1 = B->left;
Vertex<T> * b2 = B->right;

Y->right = b1;
X->left = b2;
B->left = Y;
B->right = X;
B->parent = Z;
Y->parent = B;
X->parent = B;

if (b1 != NULL)
b1->parent = Y;
if (b2 != NULL)
b2->parent = X;

updateHeight(X);
updateHeight(Y);
updateHeight(B);
}

void left_rotate(Vertex<T> * X) {
Vertex<T> * Y = X->right;
Vertex<T> * Z = X->parent;
if (Z != NULL) {
if (Z->left == X)
Z->left = Y;
else if (Z->right == X)
Z->right = Y;
}

X->right = Y->left;
Y->left = X;
X->parent = Y;
Y->parent = Z;

updateHeight(X);
updateHeight(Y);
}

void other_left_rotate(Vertex<T> * X) {
Vertex<T> * Y = X->right;
Vertex<T> * B = Y->left;
Vertex<T> * Z = X->parent;
if (Z != NULL) {
if (Z->left == X)
Z->left = B;
else if (Z->right == X)
Z->right = B;
}

Vertex<T> * b1 = B->left;
Vertex<T> * b2 = B->right;

X->right = b1;
Y->left = b2;
if (b1 != NULL)
b1->parent = X;
if (b2 != NULL)
b2->parent = Y;
B->left = X;
B->right = Y;
B->parent = Z;
X->parent = B;
Y->parent = B;
updateHeight(X);
updateHeight(Y);
updateHeight(B);
}

void updateRoot(Vertex<T> * X) { // walks up the tree from X until hitting a vertex with no parent.  Updates m_root to that vertex pointer.
Vertex<T> * current = X;
while (current->parent != NULL)
current = current->parent;

m_root = current;
}

void AVL_Update(Vertex<T> * X) {       // Starting at X, work our way up to the root, performing rotations when necessary to preserve the AVL property.

while (X != NULL) {
updateHeight(X);
int leftrightdifference = leftHeight(X) - rightHeight(X);

if ((-1 <= leftrightdifference) && (leftrightdifference <= 1)) {}       // Do nothing.  This vertex is balanced.

else if (leftrightdifference == -2) {
Vertex<T> * Y = X->right;
if (leftHeight(Y) <= rightHeight(Y))
left_rotate(X);
else if (leftHeight(Y) > rightHeight(Y))
other_left_rotate(X);
}

else if (leftrightdifference == 2) {
Vertex<T> * Y = X->left;
if (rightHeight(Y) <= leftHeight(Y))
right_rotate(X);
else if (rightHeight(Y) > leftHeight(Y))
other_right_rotate(X);
}

X = X->parent;

}

updateRoot(m_root);

}

Vertex<T> * PartialInOrderSuccessor(Vertex<T> * X) {  // This assumes X has a right child.  Otherwise doesn't do what it should.
Vertex<T> * current = X->right;
while (current->left != NULL)
current = current->left;

return current;
}

void deleteVertex(T n) {
Vertex<T> * X = findValue(n);           // X is a pointer to the vertex containing n, or NULL if there isn't one.
if (X == NULL)
return;

if (isLeaf(X)) {                        // If X is a leaf, delete it and AVL update starting with its parent.
Vertex<T> * Y = X->parent;
if (Y == NULL) {
delete X;
m_root = NULL;
return;                         // If our tree consisted of only one node, delete it and set m_root to NULL
}

else if (Y->left == X)
Y->left = NULL;
else if (Y->right == X)
Y->right = NULL;

delete X;
updateHeight(Y);
AVL_Update(Y);
}

else if ((X->left == NULL) || (X->right == NULL)) {
// If X has exactly one child, delete X, replace it with its child, and AVL update from there.

Vertex<T> * B = NULL;
if (X->left == NULL)
B = X->right;
else if (X->right == NULL)
B = X->left;                // B is X's unique non-null child

Vertex<T> * Y = X->parent;
if (Y == NULL) {
B->parent = NULL;
delete X;
m_root = B;                 // If X was the root, now B is the root.
}

else {
B->parent = Y;
if (Y->left == X)
Y->left = B;
else if (Y->right == X)
Y->right = B;
delete X;
updateHeight(Y);
AVL_Update(Y);
}

}

// Now, what if X has two children:

else {
Vertex<T> * B = PartialInOrderSuccessor(X);
Vertex<T> * C = B->parent;                      // B is 'lower' than X, hence definitely has a non-NULL parent.

B->left = X->left;
B->right = X->right;
C->left = NULL;             // It may have been the case that B was X's right child.  Then C = X and this doesn't matter
// As we're going to delete X anyway.  But in any other case, B had to be C's LEFT child.
B->parent = X->parent;

if (C == X) {
delete X;
updateHeight(B);
AVL_Update(B);
}

else {
delete X;
updateHeight(C);
AVL_Update(C);
}

}

}

void insert(T n) {
if (m_root == NULL) {
m_root = new Vertex<T>(n);
return;
}

Vertex<T> * current = m_root;
Vertex<T> * X = NULL;
Vertex<T> * newVertex = new Vertex<T>(n);

while (current != NULL) {
X = current;
T m = current->m_value;
if (m == n) return;          // Because in this implementation we've chosen to not allow multiplicity.  This would, of course, be easy to change.
if (n < m)
current = current->left;
else if (n > m)
current = current->right;
}
// So now X is storing the leaf under which we'll insert our new vertex

if (n < X->m_value) {
X->left = newVertex;
newVertex->parent = X;
updateHeight(X);
}

else if (n > X->m_value) {
X->right = newVertex;
newVertex->parent = X;
updateHeight(X);
}

AVL_Update(X);

}

};


# Pragma

Pragma is compiler dependent. I would suggest to use headers guards.

I am always against commenting code. If you need comments that might suggest bad naming. Additionally commenting stuff that is obvious is meaningless.

# C.48: Prefer in-class initializers to member initializers in constructors for constant initializers

Vertex(T tee) { m_value = tee; height = 0; left = NULL; right = NULL; parent = NULL; }


This could be just

struct Vertex {
T m_value;
int height {0};
Vertex * left {nullptr};
Vertex * right {nullptr};
Vertex * parent {nullptr};
Vertex(T tee) : m_value(tee) {}
};


# Conventions

It is important to use some kind of coding standard for code. You probably does not have one right now.

This is normal name for C++ function. That is a way you should name your functions.

Vertex<T> * findValue(T n)


This is other function but with pythonic name.

void other_right_rotate(Vertex<T> * X)


This also applies to local variable, but you have

leftrightdifference


# Hardcoding values

Try to give each number meaningful name, it will much more easier for readers to understand.

else if (leftrightdifference == -2)


# Long functions

Best functions are small (3-5 LOC) functions. Think about dividing long functions into several small functions. This make code more readable. You can give name for the functions that will explain short part of code. Additionally, small functions are easy to unit test.

# Using new

In modern C++ code you probably will never see new

Vertex<T> * newVertex = new Vertex<T>(n);


# Matter of taste

I personally use and, or instead of &&, || but it is a matter of taste.

if ((-1 <= leftrightdifference) && (leftrightdifference <= 1))


In my code it would be

if ((-1 <= leftrightdifference) and (leftrightdifference <= 1))


# Reformat code

Try to use IDE options where you can reformat code. Right now I think it is not automatically formatted.

• Thanks, I've learned a lot from each piece of advice. As far as naming conventions go, would something like Bob Martin's "Clean Code" be acceptable? – beerandmath Aug 8 '18 at 18:47
• All Bob Martin's books are amazing and way to go! Clean Code is much more than naming conventions. I really recommend it. – Newbie Aug 8 '18 at 18:50
• With respect to hard-coding values: do you mean I should do something like "int rightHeavy = -2; int leftHeavy = 2;" somewhere much earlier in the code, and replace that line with "if (treeBalance == leftHeavy)" ? And if so, where's a good place to set these conventions? I'd read somewhere else that global variables are frowned upon. – beerandmath Aug 8 '18 at 20:08
• Yes, you could define variable with great name before you use it in method. Check Wikipedia "Magic number" – Newbie Aug 8 '18 at 20:24

## Isolate platform-specific code

If you must have stdafx.h, (and it's not necessary here) consider wrapping it so that the code is portable:

#ifdef WINDOWS
#include "stdafx.h"
#endif


## Use include guards in all .h files

It's better to include guards than #pragma once because, by definition, a #pragma is compiler-specific and non-portable, while the include guards are explicitly part of the C++ standard. See SF.8

## Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful.

## Use const where possible

The getHeight, findValue, and a few other functions do not (and should not) alter the tree and should therefore be declared const. A number of the parameters should also be const.

## Provide a destructor

Right now, there is no explicit destructor and so this class leaks memory. That's a bug that should be fixed by providing a destructor that deletes the allocated memory.

## Fix the bugs

The deleteVertex does not work properly. In particular, if the deleted node has two children, the routine finds node B and the parent of B, C. The problem is that if B already has any children, these pointers are overwritten. Even with that fixed, however, there are other problems which I'll leave it to you to find. I'd recommend tracing through the code, making a diagram as you go.

• Thanks for all your feedback - I've learned a lot from each point. On the topic of nullptr, I've noticed that one of the benefits in the link doesn't really work here. i.e. overloading (say) foo(Vertex<T> * X) with foo(std::nullptr_t X) doesn't allow me to move my "if X == nullptr" code into the overloaded function because even when I'm passing a nullptr value... something something about the compiler needing to know at compile time the type of each object, and for a vertex X, X->left might have the value nullptr, but has the type Vertex<T> *. Do you know a way to get around this? – beerandmath Aug 9 '18 at 19:06