title: Insertion and deletion of nodes in Splay Trees
body: <p>I have 2 questions regarding splay trees:</p>
  
  <p><strong>1. Deletion of a node</strong></p>
  
  <p>The book I am using says the following: ''When deleting a key k, we splay the parent of the node w that gets removed. Example deletion of 8:</p>
  
  <p><img src="https://i.stack.imgur.com/UCyOr.jpg" alt="http://i.imgur.com/20ZnygP.jpg?1"></p>
  
  <p>However, what I am doing is this: If the deleted node is not the root, I splay it (to the root), delete it, and splay the right-most node of the left-subtree. But since in this case, the deleted node is the root, I simply remove it and splay the right-most node of the left subtree immediately. Like this:</p>
  
  <p><img src="https://i.stack.imgur.com/mEtgR.jpg" alt="http://i.imgur.com/24jBDda.jpg?1"></p>
  
  <p>Is this way also correct? Notice that it is totally different (like my root is 7 not 6 like my book says).</p>
  
  <p><strong>2. In which order are the values in a splay tree inserted?</strong></p>
  
  <p>Is it possible to ''get'' the order of the values that are inserted in the left tree example above? In other words, how is this tree made (in which order are the nodes inserted to generate the following tree). Is there a way to figure this out?</p>