AVL Tree C++

#algorithms #cpp #trees

AVL Tree is a balanced binary search tree in which any two subtree height only differ by at most 1 i.e height of |Left child - Right child| <= 1. Along with key and value at each node we also store the computed Height property.

We do Rebalancing if the difference is more than 1.
AVL supports following operations:-

Find in O(logN)
Insert in O(logN)
Delete in O(logN)

Analysis of operations

 AVLInsert(k, R)
  Insert(k, R)
  N <- Find(k, R)
  Rebalance(N)

 Rebalancing
 if |N.Left.Height - N.Right.Height| <= 1

 Rebalance(N)
  p <- N.Parent
  if N.Left.Height > N.Right.Height + 1:
    RebalanceRight(N)
  if N.Right.Height > N.Left.Height + 1:
    RebalanceLeft(N)
  AdjustHeight(N)
  if P != null:
    Rebalance(N)

 AdjustHeight(N)
  N.Height <- 1 + max(N.Left.Height + N.Right.Height)

Code

The code is pretty straightforward, we will just implement the operations. It is self explanatory and pretty verbose


//
//  AVLTree.h
//  Data structures
//
//  Created by Lalit Yadav on 06/09/20.
//  Copyright © 2020 Lalit Yadav. All rights reserved.
//

#ifndef AVLTree_h
#define AVLTree_h

#include <iostream>

using namespace std;

struct Node {
  int data;
  int height;
  Node * parent;
  Node * left;
  Node * right;
};

typedef Node * Nodeptr;

class AVLTree {
  Nodeptr root;
  Nodeptr Maximum(Nodeptr node);
  int GetHeight(Nodeptr node);
  void AdjustHeight(Nodeptr node);
  void ReplaceChild(Nodeptr parent, Nodeptr child, Nodeptr new_child);

  void RotateLeft(Nodeptr node);
  void RotateRight(Nodeptr node);

  void Rebalance(Nodeptr node);
  void RebalanceLeft(Nodeptr node);
  void RebalanceRight(Nodeptr node);
  public:
    AVLTree(): root(nullptr) {}
  AVLTree(int key);
  bool IsEmpty();
  Nodeptr Root();
  Nodeptr Find(int key);
  void Insert(int key);
  void Delete(int key);
  void PrintInOrder(Nodeptr node);
  void PrintPreOrder(Nodeptr node);
};

bool AVLTree::IsEmpty() {
  return root == nullptr;
}

Nodeptr AVLTree::Root() {
  return root;
}

Nodeptr AVLTree::Maximum(Nodeptr node) {
  if (node -> right != NULL) {
    return Maximum(node -> right);
  } else {
    return node;
  }
}

int AVLTree::GetHeight(Nodeptr node) {
  if (node == nullptr)
    return 0;

  return node -> height;
}

Nodeptr AVLTree::Find(int key) {
  if (IsEmpty()) {
    return nullptr;
  }

  auto parent = root;

  while (parent != nullptr) {
    if (key > parent -> data && parent -> right != nullptr)
      parent = parent -> right;
    else if (key < parent -> data && parent -> left != nullptr)
      parent = parent -> left;
    else
      return parent;
  }

  return parent;
}

void AVLTree::AdjustHeight(Nodeptr node) {
  node -> height = 1 + max(GetHeight(node -> left), GetHeight(node -> right));
}

void AVLTree::RotateLeft(Nodeptr node) {
  auto pivot = node -> right;

  // Update the parent of the node
  pivot -> parent = node -> parent;
  node -> parent = pivot;

  // Update the child of of the updated parent
  if (pivot -> parent == nullptr)
    root = pivot;
  else if (pivot -> parent -> left == node)
    pivot -> parent -> left = pivot; // Update the child link of the parent
  else
    pivot -> parent -> right = pivot;

  node -> right = pivot -> left;

  if (pivot -> left != nullptr)
    pivot -> left -> parent = node;

  pivot -> left = node;

  AdjustHeight(node);
  AdjustHeight(pivot);
}

void AVLTree::RotateRight(Nodeptr node) {
  auto pivot = node -> left;

  pivot -> parent = node -> parent;
  node -> parent = pivot;

  if (pivot -> parent == nullptr)
    root = pivot;
  else if (pivot -> parent -> left == node)
    pivot -> parent -> left = pivot;
  else
    pivot -> parent -> right = pivot;

  node -> left = pivot -> right;

  if (pivot -> right != nullptr)
    pivot -> right -> parent = node;

  pivot -> right = node;

  AdjustHeight(node);
  AdjustHeight(pivot);
}

void AVLTree::RebalanceLeft(Nodeptr node) {
  auto right_child = node -> right;

  if (right_child != nullptr) {
    if (GetHeight(right_child -> left) > GetHeight(right_child -> right))
      RotateRight(right_child);
  }

  RotateLeft(node);
}

void AVLTree::RebalanceRight(Nodeptr node) {
  auto left_child = node -> left;

  if (left_child != nullptr) {
    if (GetHeight(left_child -> right) > GetHeight(left_child -> left))
      RotateLeft(left_child);
  }

  RotateRight(node);
}

void AVLTree::Rebalance(Nodeptr node) {
  auto parent = node -> parent;

  if (GetHeight(node -> left) > GetHeight(node -> right) + 1)
    RebalanceRight(node);

  if (GetHeight(node -> right) > GetHeight(node -> left) + 1)
    RebalanceLeft(node);

  AdjustHeight(node);

  if (parent != nullptr) {
    Rebalance(parent);
  }
}

void AVLTree::Insert(int key) {
  auto p = new Node;

  p -> data = key;
  p -> height = 0;
  p -> parent = nullptr;
  p -> left = nullptr;
  p -> right = nullptr;

  if (IsEmpty()) {
    root = p;
  } else {
    auto parent = Find(key);
    p -> height = 1;

    if (key < parent -> data)
      parent -> left = p;
    else
      parent -> right = p;

    p -> parent = parent;
    Rebalance(parent);
  }
}

void AVLTree::Delete(int key) {
  auto node = Find(key);

  if (node == nullptr)
    return;

  if (node -> right == nullptr && node -> left == nullptr) {
    if (node -> parent == nullptr) {
      root = nullptr;
    } else {
      ReplaceChild(node -> parent, node, nullptr);
      Rebalance(node -> parent);
    }
  } else if (node -> left == nullptr) {
    // Replace the node with it's right child
    if (node -> parent == nullptr) {
      root = node -> right;
      node -> right -> parent = nullptr;
      Rebalance(node -> right);
    } else {
      ReplaceChild(node -> parent, node, node -> right);
      node -> right -> parent = node -> parent;
      Rebalance(node -> parent);
    }
  } else {
    // Replace the node with the maximum key from it's left child
    auto new_node = Maximum(node -> left);

    if (node -> parent == nullptr) {
      root = new_node;

      new_node -> right = node -> right;
      new_node -> left = node -> left;

      Rebalance(new_node);
    } else {
      auto parent_new_node = new_node -> parent;
      ReplaceChild(node -> parent, node, new_node);
      ReplaceChild(new_node -> parent, new_node, nullptr);

      new_node -> parent = node -> parent;
      new_node -> left = node -> left;

      if (node -> right != nullptr) {
        new_node -> right = node -> right;
        new_node -> right -> parent = new_node;
      }

      if (parent_new_node -> parent == node) {
        parent_new_node -> parent = new_node;
      }

      Rebalance(parent_new_node);
    }
  }

  delete node;
}

void AVLTree::ReplaceChild(Nodeptr parent, Nodeptr child, Nodeptr new_child) {
  if (parent -> left == child) {
    parent -> left = new_child;
  } else {
    parent -> right = new_child;
  }
}

void AVLTree::PrintInOrder(Nodeptr node) {
  if (node == nullptr)
    return;

  PrintInOrder(node -> left);
  cout << node -> data << ' ';
  PrintInOrder(node -> right);
}

void AVLTree::PrintPreOrder(Nodeptr node) {
  if (node == nullptr)
    return;

  cout << node -> data << ' ';
  PrintPreOrder(node -> left);
  PrintPreOrder(node -> right);
}

#endif /* AVLTree_h */