title: How to find the rank of a node in an AVL tree?
body: <p>I need to implement two rank queries [<code>rank(k)</code> and <code>select(r)</code>]. But before I can start on this, I need to figure out how the two functions work. </p>
  
  <p>As far as I know, <code>rank(k)</code> returns the rank of a given key <code>k</code>, and <code>select(r)</code> returns the key of a given rank <code>r</code>.</p>
  
  <p>So my questions are:</p>
  
  <p>1.) How do you calculate the rank of a node in an AVL(self balancing BST)?</p>
  
  <p>2.) Is it possible for more than one key to have the same rank? And if so, what woulud <code>select(r)</code> return?</p>
  
  <p>I'm going to include a sample AVL tree which you can refer to if it helps answer the question.</p>
  
  <p><img src="https://i.stack.imgur.com/M81oc.jpg" alt="enter image description here"></p>
  
  <p>Thanks!</p>