sentences:  Since all auxiliary tree searches are unsuccessful except the last one (we stop once a search is successful, naturally), we search formula_5 auxiliary trees.Each search takes formula_1, because an auxiliary tree's size is bounded by formula_7, the height of the reference tree.The update cost fits within this bound as well, because we only have to perform one "cut" and one "join" for every visited auxiliary tree.