title: How to implement BST functions insert() and split() based upon rank?
body: <p>I am trying to figure out how to implement code to the functions of insert() (which inserts an element into the tree), split() (which splits the tree on rank r into two trees of L and R. L containing ranks &lt; r and R containing ranks &gt;= r. For this assignment, I am dumbfounded. I believe I have the code for my insert correct for it works:</p>
  <pre><code>Node *insert(Node *T, int v, int r)
  {
      if(T == nullptr)
      {
          return new Node(v);
      }
      int rank = T-&gt;left ? T-&gt;left-&gt;size : 0;
      
      if (r &lt;= rank)
      {
          T -&gt; left = insert(T -&gt; left, v, rank);
      }
      else
      {
          T -&gt; left = insert(T -&gt; left, v, r - rank - 1);
      }
      fix_size(T);
      return T;
  }
  </code></pre>
  <p>For my split() function, I barely have anything that works. Can someone explain the algorithm of how to complete these two functions? Thank you!</p>