AVL Tree C++

 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) 

 // // 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 */