title: Red-Black tree: Split/Concatenate in log(n) time
body: <p>According to Ron Wein your able to do split and concatenation of red-black tree's in O(log(n)) time. See his artikle: <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.109.4875&amp;rep=rep1&amp;type=pdf" rel="nofollow">Efficient Implementation of Red-Black Trees with Split and Catenate Operations</a></p>
  
  <p>However I'm still not convinced that the running time of split really is true.</p>
  
  <p>The idea is that split uses worst-case log(n) concatenatations. These concat's is done fast as we can find the node, p, by remembering the p, from last concatenate.</p>
  
  <p>The problem is that concatenation starts the fix-up (balancing) algorithm, which as far as I know takes O(log n) (see step 5 in the pseudo-code for concatenation). 
  This gives me a running time of log(n)*log(n), as split will make worst-case log(n) concatenations.</p>
  
  <p>Ron Wein, does not take the fix-up algorithm into count in his argumentation. What have i missed in my analysis, or is the algorithm wrong?</p>