Show Menu
Cheatography

Binary Search Tree C++ Cheat Sheet by

C++ BST and AVL

BST AVL Struct

template <class T>
class TreeNode {
private:
    T _item;
    TreeNode<T>* _left;
    TreeNode<T>* _right;
    //Could include
    TreeNode<T>* _parent;
    int _height;
public:
    TreeNode(T x) {
     _left = _right = NULL;
     _item = x;
     _height = 0; };
     friend BinarySearchTree<T>;
};
_item = value
_height = height of the node ( will have to calculate )
_left , _right = default set to NULL in public constr­uctor.

Search Max,Min

template <class T>
T BinarySearchTree<T>::searchMax() {
     TreeNode<T>* current = _root;
     while (current->_right) {
           current = current->_right;
      }
      return current->_item;
}

template <class T>
T BinarySearchTree<T>::searchMin() {
      TreeNode<T>* current = _root;
      while (current->_left) {
      current = current->_left;
      }
      return current->_item;
}

Successor

template <class T>
T BinarySearchTree<T>::successor(T x){
     TreeNode<T>* root = _root;
     T succ = NULL;
     while (root != NULL) {
       if (x < root->_item){
           succ = root->_item;
           root = root->_left;
        }
        else{
           root = root->_right;
        }
    }
    return succ;
}

exist() // iterative

//Iterative
template <class T>
bool BinarySearchTree<T>::exist(T x) {
        TreeNode<T>* nd = _root;
        while (nd != NULL) {
                if (nd->_item == x) return true;
                if (nd->_item > x) nd = nd->_left;
                else nd = nd->_right;
        }
        return false;
}

exit() // Recursive

template <class T>
bool BinarySearchTree<T>::exist(TreeNode<T> Node,T x) {
         // RECURSIVE
         exists ( _root , value x )
         if (_root == null) return false;
         if (_root->_item == x) return true;
         if (_root->_item > x)
            return exists ( _root->left, x);
         else exists ( _root->right, x );
}

LR RL Rotation


//LR Rotation
template <class T>
TreeNode<T> BinarySearchTree<T>::_leftrightRotation(TreeNode<T> node)
{
node->_left = _rightRotation(node->_left);
node = _leftRotation(node);
return node;
}

//RL Rotation
template <class T>
TreeNode<T> BinarySearchTree<T>::_rightleftRotation(TreeNode<T> node) {
node->_right = _leftRotation(node->_right);
node = _rightRotation(node);
return node;
}
 

PreOrd­erPrint

template <class T>
void BinarySearchTree<T>::_preOrderPrint(TreeNode<T>* node) {
      if (!node) return;
      cout << node->_item << " ";
      _preOrderPrint(node->_left);
      _preOrderPrint(node->_right);
}

InOrde­rPrint

template <class T>
void BinarySearchTree<T> :: _inOrderPrint(TreeNode<T>* node) {
      if (!node) return;
      _inOrderPrint(node->_left);
      cout << node->_item << " ";
      _inOrderPrint(node->_right);
}

PostOr­der­Print

template <class T>
void BinarySearchTree<T>:: _postOrderPrint(TreeNode<T>* node) {
     if (!node) return;
     _postOrderPrint(node->_left);
     _postOrderPrint(node->_right);
     cout << node->_item << " ";
}

Height

template <class T>
int BinarySearchTree<T>::height(TreeNode<T>* node) {
return node == NULL ? -1 : (node->_height);
}

template <class T>
int BinarySearchTree<T>::_calheight(TreeNode<T>* node) {
   int leftHeight = -1;
   int rightHeight = -1;
   if (node != NULL) {
     if (node->_left != NULL) {
        leftHeight = _calheight(node->_left);
     }
     if (node->_right != NULL) {
      rightHeight = _calheight(node->_right);
     }
   }
   return max(leftHeight, rightHeight) + 1;
}

//Height from TA
template <class T>
void TreeNode<T>::rectifyHeight()
{
 int left = _left ? _left->_height : -1;
 int right = _right ? _right->_height : -1;
//Height Value
 _height = (left > right ? left : right) + 1;
}

Insert

//Task 1 and 6
template <class T>
TreeNode<T> BinarySearchTree<T>::_insert(TreeNode<T> current, T x) {
    if (current->_item > x) {
      if (current->_left)
        current->_left = _insert(current->_left, x);
      else {
        current->_left = new TreeNode<T>(x);
        _size++;
       }
     }
    else if (x > current->_item) {
      if (current->_right)
         current->_right = _insert(current->_right, x);
      else{
         current->_right = new TreeNode<T>(x);
         _size++;
       }
     }
     else
//item already exists, dont need do anything
      return current;
 

Code From TA// Rotation

//-1 if no children, st bf will work
int left = current->_left ? current->_left->_height : -1;

int right = current->_right ? current->_right->_height : -1;

current->_height = (left > right ? left : right) + 1;
    
  //GET DIFF IN height
  if (abs(left - right) > 1){
     
if (left > right){

       int LLH = current->_left->_left ? current->_left->_left->_height : 0;
       
       int LRH = current->_left->_right ? current->_left->_right->_height : 0;

    if (LLH < LRH){
    current->_left = _leftRotation(current->_left);
    }
    current = _rightRotation(current);

}
else {
    int RLH = current->_right->_left ? current->_right->_left->_height : 0;

    int RRH = current->_right->_right ? current->_right->_right->_height : 0;

    if (RRH < RLH){
    current->_right = _rightRotation(current->_right);
    }
    current = _leftRotation(current);

 }

}

//go through tree and rect height

   current->rectifyHeight();
   return current;

}

LL RR Rotation


//LL Rotation
template <class T>
TreeNode<T> BinarySearchTree<T>::_leftRotation(TreeNode<T> node)
{
TreeNode<T>* nd;
nd = node->_left;
node->_left = nd->_right;
nd->_right = node;

nd->_height = calheight(nd);
node->_height = calheight(node);
return nd;


/*
*
*Codes from tutorialshorizon
*copyrights to - https://algorithms.tutorialhorizon.com/avl-tree-insertion/
*
//*/
//TreeNode<T>* nd = node->_right;
//TreeNode<T>* T2 = nd->_left;
//nd->_left = node;
//node->_right = T2;
//nd->_height = calheight(nd);
//node->_height = calheight(node);
//return nd;
}

//RR Rotation
template <class T>
TreeNode<T> BinarySearchTree<T>::_rightRotation(TreeNode<T> node)
{

TreeNode<T>* nd;
nd = node->_right;
node->_right = nd->_left;
nd->_left = node;
nd->_height = calheight(nd);
node->_height = calheight(node);
return nd;

/*
*
*Codes from tutorialshorizon
*copyrights to - https://algorithms.tutorialhorizon.com/avl-tree-insertion/
*
*
//
TreeNode<T>* nd = node->_left;
TreeNode<T>* T2 = nd->_right;
nd->_right = node;
node->_left = T2;
nd->_height = calheight(nd);
node->_height = calheight(node);
return nd;*/
}

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          Numeric Formats Cheat Sheet
          C# & Unity MonoBehaviour Cheat Sheet

          More Cheat Sheets by BearTeddy