35 Augmenting Trees

35.1 Augmentation of Trees . . . . . . . . . .

35.2 Balanced BSTs . . . . . . . . . . . . . . .

35.2.1 Rotations . . . . . . . . . . . . . .

35.2.2 Implementation . . . . . . . . . . .

35.3 Order-Statistic Trees: Trees as Sequences

35.4 Augmented Spatial Trees