A Self-balancing Binary Search Tree (BST) where difference between heights of left and right subtrees cannot be more than 1 for all nodes is called an AVL Tree.
Below is a simple implementation of AVL tree in C++ with in-line explanation in comments.
Full Code:
#include
#include
#include
// **************************************************
// Adelson-Velskii and Landis dynamically balanced
// tree class.
class AVLTree {
// - - - - - - - - - - - - - - - - - - - - - - - -
// Private Node subclass for the nodes of the tree.
private:
class Node {
// - - - - - - - - - - - - - - - - - - - - - -
// Private data for the node of the tree.
private:
// The actual data being stored.
int data;
// The height of this node from the deepest
// point.
int height;
// A pointer to the left subtree.
Node *left_child;
// A pointer to the node's parent.
Node *parent;
// A pointer to the right subtree.
Node *right_child;
// - - - - - - - - - - - - - - - - - - - - - -
// Public methods to process the node.
public:
// Constructor initializing the data.
Node(int val);
// Calculate the balance point.
int getBalance();
// Get the actual data.
int getData();
// Get the height.
int getHeight();
// Get the left subtree.
Node *getLeftChild();
// Get the node's parent.
Node *getParent();
// Get the right subtree.
Node *getRightChild();
// Remove the node's parent.
void removeParent();
// Set the left subtree.
Node *setLeftChild(Node *newLeft);
// Set the right subtree.
Node *setRightChild(Node *newRight);
// Set the node's height.
int updateHeight();
}; // Node
// - - - - - - - - - - - - - - - - - - - - - - - -
// Private data for the tree.
private:
// A pointer to the top node of the tree.
Node *root;
// - - - - - - - - - - - - - - - - - - - - - - - -
// Private methods to process the tree.
private:
// Balance the subtree.
void balanceAtNode(Node *n);
// Find the node containing the data.
Node *findNode(int val);
// Print the subtree.
void printSubtree(Node *subtree, int depth,
int offset, bool first);
// Rotate the subtree left.
void rotateLeft(Node *n);
// Rotate the subtree left.
void rotateRight(Node *n);
// Set the root.
void setRoot(Node *n);
// Figure out the default spacing for element.
int spacing(int offset);
// - - - - - - - - - - - - - - - - - - - - - - - -
// Public methods to process the tree.
public:
// Constructor to create an empty tree.
AVLTree();
// Constructor to populate the tree with one node.
AVLTree(int val);
// Get the tree's height.
int getHeight();
// Insert the value into the tree.
bool insert(int val);
// Print the tree.
void print();
// Remove the value from the tree.
bool remove(int val);
}; // AVLTree
// **************************************************
// AVLTree's Node subclass methods.
// --------------------------------------------------
// Constructor initializing the data.
AVLTree::Node::Node(int val) {
data = val;
height = 0;
parent = nullptr;
left_child = nullptr;
right_child = nullptr;
} // Node
// --------------------------------------------------
// Calculate the balance point. Negative, when the
// right side is deeper. Zero, when both sides are
// the same. Positive, when the left side is deeper.
int AVLTree::Node::getBalance() {
// If we don't have a left subtree, check the
// right.
int result;
if (left_child == nullptr)
// If neither subtree exists, return zero.
if (right_child == nullptr)
result = 0;
// Otherwise, the right subtree exists so make
// it's height negative and subtract one.
else
result = -right_child->height-1;
// Otherwise, we have a left subtree so if we
// don't have a right one, return the left's
// height plus one.
else if (right_child == nullptr)
result = left_child->height+1;
// Otherwise, both subtrees exist so subtract
// them to return the difference.
else
result = left_child->height-right_child->height;
return result;
} // getBalance
// --------------------------------------------------
// Get the actual data.
int AVLTree::Node::getData() {
return data;
} // getData
// --------------------------------------------------
// Get the height.
int AVLTree::Node::getHeight() {
return height;
} // getHeight
// --------------------------------------------------
// Get the left subtree.
AVLTree::Node *AVLTree::Node::getLeftChild() {
return left_child;
} // getLeftChild
// --------------------------------------------------
// Get the node's parent.
AVLTree::Node *AVLTree::Node::getParent() {
return parent;
} // getParent
// --------------------------------------------------
// Get the right subtree.
AVLTree::Node *AVLTree::Node::getRightChild() {
return right_child;
} // getRightChild
// --------------------------------------------------
// Remove the node's parent.
void AVLTree::Node::removeParent() {
parent = nullptr;
} // removeParent
// --------------------------------------------------
// Set the left subtree.
AVLTree::Node *AVLTree::Node::setLeftChild(
Node *newLeft) {
// If there is a left node, set it's parent to
// be us. In any event, make it our left subtree
// and update the height.
if (newLeft != nullptr)
newLeft->parent = this;
left_child = newLeft;
updateHeight();
return left_child;
} // setLeftChild
// --------------------------------------------------
// Set the right subtree.
AVLTree::Node *AVLTree::Node::setRightChild(
Node *newRight) {
// If there is a right node, set it's parent to
// be us. In any event, make it our right subtree
// and update the height.
if (newRight != nullptr)
newRight->parent = this;
right_child = newRight;
updateHeight();
return right_child;
} // setRightChild
// --------------------------------------------------
// Set the node's height.
int AVLTree::Node::updateHeight() {
// If we don't have a left subtree, check the
// right.
if (left_child == nullptr)
// If we don't have either subtree, the height
// is zero.
if (right_child == nullptr)
height = 0;
// Otherwise, we only have the right subtree so
// our height is one more than it's height.
else
height = right_child->height+1;
// Otherwise, the left subtree exists so if we
// don't have a right one, our height is one
// more than it's height.
else if (right_child == nullptr)
height = left_child->height+1;
// Otherwise, we have both subtree's so if the
// left's height is greater than the right, our
// height is one more than it.
else if (left_child->height > right_child->height)
height = left_child->height+1;
// Otherwise, the right subtree's height will be
// used so our height is one more than it.
else
height = right_child->height+1;
return height;
} // updateHeight
// **************************************************
// AVLTree class methods.
// --------------------------------------------------
// Constructor to create an empty tree.
AVLTree::AVLTree() {
root = nullptr;
} // AVLTree
// --------------------------------------------------
// Constructor to populate the tree with one node.
AVLTree::AVLTree(int val) {
root = new Node(val);
} // AVLTree
// --------------------------------------------------
// Balance the subtree.
void AVLTree::balanceAtNode(Node *n) {
// Get the current balance and if it is bad
// enough on the left side, rotate it right
// adjusting the subtree left, if required.
int bal = n->getBalance();
if (bal > 1) {
if (n->getLeftChild()->getBalance() < 0)
rotateLeft(n->getLeftChild());
rotateRight(n);
// Otherwise, if the balance is bad enough on
// the right side, rotate it left adjusting the
// subtree right, if required.
} else if (bal < -1) {
if (n->getRightChild()->getBalance() > 0)
rotateRight(n->getRightChild());
rotateLeft(n);
} // if
} // balanceAtNode
// --------------------------------------------------
// Find the node containing the data.
AVLTree::Node *AVLTree::findNode(int val) {
// While nodes remain, if we found the right
// node, exit the loop. If the value we want
// is less than the current, check the left
// subtree, otherwise, the right.
Node *temp = root;
while (temp != nullptr) {
if (val == temp->getData())
break;
else if (val < temp->getData())
temp = temp->getLeftChild();
else
temp = temp->getRightChild();
} // while
return temp;
} // findNode
// --------------------------------------------------
// Get the tree's height.
int AVLTree::getHeight() {
return root->getHeight();
} // getHeight
// --------------------------------------------------
// Insert the value into the tree.
// Returns:
// true: If addition is successful
// false: If item already exists
//
bool AVLTree::insert(int val) {
// If the tree is empty, add the new node as the
// root.
if (root == nullptr)
root = new Node(val);
// Otherwise, we need to find the insertion point.
else {
// Starting at the tree root search for the
// insertion point, until we have added the
// new node.
Node *added_node = nullptr;
Node *temp = root;
while (temp != nullptr && added_node == nullptr) {
// If the value is less than the current
// node's value, go left. If there isn't a
// left subtree, insert the node, otherwise,
// it is next to check.
i