ABSTRACT
In this section we characterize the complexity of the update and query operations with respect to each of the following time measures: worst-case, amortized, and randomized. We begin by considering the case of paths and defer the extension to trees till the next section.
