Index lookup in a rope built by repeated appends

A rope represents a long string as a binary tree: leaves hold short chunks of text, and each internal node stores its weight, the total length of its left subtree. index(i) walks down from the root, going left if i < weight and otherwise subtracting weight and going right. concat(a, b) allocates a new root with children a and b in O(1). A document is built from n chunks with r = concat(r, chunk) in a loop, and nothing ever rebalances the tree. What does index(i) cost on the result?

46 of 46 in Data Structures & Algorithms