Before revision: I.e. TSD construction takes with high probability {\cal O}( n \ln n) time and TSD size can be made worst case {\cal O}(n) with an expected rebuild cost of {\cal O}( 1).
After revision: I.e. TSD construction takes with high probability {\cal O}( n \ln n) time and TSD size can be made worst case {\cal O}(n) , ii) a depth of {\cal O}( 1).