Caching: a useful technique for speeding up a computation that is requested repeatedly. Compute the result and save it in the header. Next time, just look it up.
Ideally, every operation that affects the cached value updates it.
Not always possible: SPLIT can't update size in constant time. When should we update size?
1. As soon as it becomes invalid, i.e. in SPLIT.
Wasteful: imagine an algorithm that does many SPLITs, but doesn't often look at the size.
2. When needed (Lazy Evaluation), i.e. when requesting size info. If size is out of date, recompute it and cache the new value. No wasted computation.
Need to a way to tell if size is up-to-date: e.g. using a boolean flag, or setting size = -1 to indicate invalid info.