trees is sometimes known as -tree survey of the different types of -trees is presented in [ empirical results of the various schemes are reported in [ analysis of - trees and -trees can be found in [ ][ ]and [ exercise is deceptively difficult solution can be found in [ exercise is from [ information on *-treesdescribed in exercise can be found in [ exercise is from [ solution to exercise using rotations is given in [ using threadsa la exercise was first proposed in [ - treeswhich handle multidimensional datawere first proposed in [ and are discussed in other popular balanced search trees are red-black trees [ and weight-balanced trees [ more balanced-tree schemes can be found in the books [ and [ adelson-velskii and landis"an algorithm for the organization of information,soviet mat doklady ( ) - ahoj hopcroftand ullmanthe design and analysis of computer algorithmsaddison-wesleyreadingmass allen and munro"self organizing search trees,journal of the acm ( ) - baeza-yates"expected behaviour of -trees under random insertions,acta informatica ( ) - baeza-yates" trivial algorithm whose analysis isn'ta continuation,bit ( ) - bayer and mccreight"organization and maintenance of large ordered indices,acta informatica ( ) - bentley"multidimensional binary search trees used for associative searching,communications of the acm ( ) - bitner"heuristics that dynamically organize data structures,siam journal on computing ( ) - comer"the ubiquitous -tree,computing surveys ( ) - culberson and munro"explaining the behavior of binary search trees under prolonged updatesa model and simulations,computer journal ( ) - culberson and munro"analysis of the standard deletion algorithms in exact fit domain binary search trees,algorithmica ( ) - culikt ottmanand wood"dense multiway trees,acm transactions on database systems ( ) - eisenbathn zivianag gonnetk melhornand wood"the theory of fringe analysis and its application to - trees and -trees,information and control ( ) - eppinger"an empirical study of insertion and deletion in binary search trees,communications of the acm ( ) - flajolet and odlyzko"the average height of binary trees and other simple trees,journal of computer and system sciences ( ) - gonnet and baeza-yateshandbook of algorithms and data structures ed addison-wesleyreadingmass gudes and tsur"experiments with -tree reorganization,proceedings of acm sigmod symposium on management of data ( ) -