title: Why is my Ranked Binary search tree implementation is so slow?
body: <p>So I wrote a Ranked self-balancing Binary Search Tree instead of using std::set. I was expecting it to work faster for getting rank of elements, but it seems to take more time than using std::set and iterating through to find rank. Is there any way to speed it up?</p>
  <pre><code>#include&lt;bits/stdc++.h&gt;
  
  struct treeNode{
      int data;      
      int leftsize;  //for finding rank
      int height;    //for balancing during insertions and deletions
  
      treeNode* left;
      treeNode* right;
  
      treeNode()
      :data(NAN), leftsize(0), left(nullptr), right(nullptr){}
  
      treeNode(int val, int lsize, int ht)
      :data(val), leftsize(lsize), height(ht), left(nullptr), right(nullptr){}
  };
  
  int height(treeNode* node)
  {
      if(node == nullptr)
          return 0;
      
      return node-&gt;height;
  }
  
  int getBalance(treeNode* node)
  {
      if(node==nullptr)
          return 0;
      
      return height(node-&gt;left) - height(node-&gt;right);
  }
  
  
  int parseLeftSub(treeNode* node)
  {
      if(node == nullptr)
          return 0;
      int cnt = 1;
      cnt += parseLeftSub(node-&gt;left);
      cnt += parseLeftSub(node-&gt;right);
      
      return cnt;
  }
  
  void printNode(treeNode* node)
  {
      if(node ==  nullptr)
          return;
      
      printNode(node-&gt;left);
      std::cout &lt;&lt; node-&gt;data &lt;&lt; &quot;  &quot; &lt;&lt; node-&gt;leftsize &lt;&lt; std::endl;
      printNode(node-&gt;right);
  }
  
  treeNode* createNode(int val)
  {
      treeNode* node = new treeNode(val, 1, 1);
      return node;
  }
  
  treeNode* createTree(std::vector&lt;int&gt;&amp; a, int start, int end)
  {
      if(start&gt;end)
          return nullptr;
  
      int mid = (start + end)/2;
  
      treeNode* node = createNode(a[mid]);
      node-&gt;left = createTree(a, start, mid-1);
      node-&gt;right = createTree(a, mid+1, end);
  
      node-&gt;leftsize += parseLeftSub(node-&gt;left);
  
      return node;
  }
  
  treeNode* rightRotate(treeNode* y)  
  {  
      treeNode* x = y-&gt;left;
      treeNode* T2 = x-&gt;right;
    
      // Perform rotation  
      x-&gt;right = y;  
      y-&gt;left = T2;  
    
      // Update heights  
      y-&gt;height = std::max(height(y-&gt;left), 
                      height(y-&gt;right)) + 1;  
      x-&gt;height = std::max(height(x-&gt;left), 
                      height(x-&gt;right)) + 1;  
    
      // Return new root
      y-&gt;leftsize = parseLeftSub(y-&gt;left) + 1;
      return x;  
  }
  
  treeNode* leftRotate(treeNode* x)  
  {  
      treeNode* y = x-&gt;right;  
      treeNode* T2 = y-&gt;left;  
    
      // Perform rotation  
      y-&gt;left = x;  
      x-&gt;right = T2;  
    
      // Update heights  
      x-&gt;height = std::max(height(x-&gt;left),     
                      height(x-&gt;right)) + 1;  
      y-&gt;height = std::max(height(y-&gt;left),  
                      height(y-&gt;right)) + 1;  
    
      // Return new root
      y-&gt;leftsize = parseLeftSub(y-&gt;left) + 1; 
      return y;  
  }  
  
  treeNode* insertNode(int val, treeNode* node)
  {
      if(node == nullptr)
          return createNode(val);
  
      if(val &lt; node-&gt;data)
          node-&gt;left = insertNode(val, node-&gt;left);
      else if(val &gt; node-&gt;data)
          node-&gt;right = insertNode(val, node-&gt;right);
      else
          return node;
      
      node-&gt;height = 1 + std::max(height(node-&gt;left), height(node-&gt;right));
      node-&gt;leftsize = parseLeftSub(node-&gt;left) + 1;
      
      int balance = getBalance(node);
  
      if(balance &gt; 1 &amp;&amp; val &lt; node-&gt;left-&gt;data)
          return rightRotate(node);
      
      else if(balance &lt; -1 &amp;&amp; val &gt; node-&gt;right-&gt;data)
          return leftRotate(node);
      
      else if(balance &gt; 1 &amp;&amp; val &gt; node-&gt;left-&gt;data)
      {
          node-&gt;left = leftRotate(node-&gt;left);
          return rightRotate(node);
      }
      
      else if(balance &lt; -1 &amp;&amp; val &lt; node-&gt;right-&gt;data)
      {
          node-&gt;right = rightRotate(node-&gt;right);
          return leftRotate(node);
      }
  
      return node;
  }
  
  treeNode* searchNode(int val, treeNode* node)
  {
      if(node == nullptr)
          return nullptr;
      
      treeNode* foundNode = nullptr;
      if(val == node-&gt;data)
          return node;
  
      else if(val &lt; node-&gt;data)
          foundNode = searchNode(val, node-&gt;left);
      else
          foundNode = searchNode(val, node-&gt;right);
      
      return foundNode;
  }
  
  treeNode* findLowerBound(int val, treeNode* node)
  {
      if(node == nullptr)
          return nullptr;
      
      if(val == node-&gt;data)
          return node;
  
      else if(val&gt;node-&gt;data)
      {
          return(findLowerBound(val, node-&gt;right));
      }
  
      treeNode* temp = findLowerBound(val, node-&gt;left);
      if(temp != nullptr &amp;&amp; temp-&gt;data &gt;= val)
          return temp;
      else
          return node; 
  }
  
  treeNode* findUpperBound(int val, treeNode* node)
  {
      if(node == nullptr)
          return nullptr;
      
      if(val == node-&gt;data)
          return node;
  
      else if(val&lt;node-&gt;data)
      {
          return(findUpperBound(val, node-&gt;left));
      }
  
      treeNode* temp = findUpperBound(val, node-&gt;right);
      if(temp != nullptr &amp;&amp; temp-&gt;data &lt;= val)
          return temp;
      else
          return node; 
  }
  
  treeNode* findMinNode(treeNode* node)
  {
      if(node-&gt;left == nullptr)
          return node;
      return (findMinNode(node-&gt;left));
  }
  
  treeNode* deleteNode(int val, treeNode*&amp; node)
  {
      if(node == nullptr)
          return nullptr;
  
      if(node-&gt;data &gt; val)
          node-&gt;left = deleteNode(val, node-&gt;left);
      else if(node-&gt;data &lt; val)
          node-&gt;right = deleteNode(val, node-&gt;right);
      else
      {
          if(node-&gt;left==nullptr &amp;&amp; node-&gt;right==nullptr)
          {
              delete node;
              node = nullptr;
          }
  
          else if(node-&gt;left==nullptr)
          {
              treeNode* temp = node;
              node = node-&gt;right;
              delete temp;
          }
          else if(node-&gt;right==nullptr)
          {
              treeNode* temp = node;
              node = node-&gt;left;
              delete temp;
          }
          else
          {
              treeNode* temp = findMinNode(node-&gt;right);
              node-&gt;data  = temp-&gt;data;
              node-&gt;right = deleteNode(temp-&gt;data, node-&gt;right);
          }
      }    
  
      if (node == NULL)  
          return node;
      
      node-&gt;leftsize = parseLeftSub(node-&gt;left) + 1;
      node-&gt;height = 1 + std::max(height(node-&gt;left),  
                             height(node-&gt;right));  
  
      int balance = getBalance(node);  
    
      if (balance &gt; 1 &amp;&amp;  
          getBalance(node-&gt;left) &gt;= 0)  
          return rightRotate(node);  
    
      if (balance &gt; 1 &amp;&amp;  
          getBalance(node-&gt;left) &lt; 0)  
      {  
          node-&gt;left = leftRotate(node-&gt;left);  
          return rightRotate(node);  
      }  
  
      if (balance &lt; -1 &amp;&amp;  
          getBalance(node-&gt;right) &lt;= 0)  
          return leftRotate(node);  
  
      if (balance &lt; -1 &amp;&amp;  
          getBalance(node-&gt;right) &gt; 0)  
      {  
          node-&gt;right = rightRotate(node-&gt;right);  
          return leftRotate(node);  
      }  
      
      return node;
  }
  
  int findRank(int val, treeNode* node)
  {
      int rank = node-&gt;leftsize;
      if(node==nullptr)
      {
          return -1;
      }
  
      if(val&lt;node-&gt;data)
      {
          rank -= node-&gt;leftsize;
          rank += findRank(val, node-&gt;left);
      }
      else if(val&gt;node-&gt;data)
      {
          rank += findRank(val, node-&gt;right);
      }
  
      return rank;    
  }
  </code></pre>
  <p>I know its quite a lot. Also can any other stl containers be used to find rank, insert and delete efficiently</p>