trees and external storage if we take two data items per node as the average utilizationabout / of the available storage is wasted you might imagine using linked lists instead of arrays to hold the child and data referencesbut the overhead of the linked list compared with an arrayfor only three or four itemswould probably not make this worthwhile approach because they're balancedred-black trees contain few nodes that have only one childso almost all the storage for child references is used alsoevery node contains the maximum number of data itemswhich is one this makes red-black trees more efficient than trees in terms of memory usage in javawhich stores references to objects instead of the objects themselvesthis difference in storage between trees and red-black trees may not be importantand the programming is certainly simpler for trees howeverin languages that don' use references this waythe difference in storage efficiency between red-black trees and trees may be significant - trees we'll discuss - trees briefly here because they are historically important and because they are still used in many applications alsosome of the techniques used with - trees are applicable to -treeswhich we'll examine in the next section finallyit' interesting to see how small change in the number of children per node can cause large change in the tree' algorithms - trees are similar to trees except thatas you might have guessed from the namethey hold one less data item and have one less child they were the first multiway treeinvented by hopcroft in -trees (of which the tree is special casewere not invented until in many respects the operation of - trees is similar to that of trees nodes can hold one or two data items and can have zeroonetwoor three children otherwisethe arrangement of the key values of the parent and its children is the same inserting data item into node is potentially simplified because fewer comparisons and moves are potentially necessary as in treesall insertions are made into leaf nodesand all leaf nodes are on the bottom level node splits searching for an existing data item is handled just as it is in tree except for the number of data items and children you might guess that insertion is also similar to treebut there is surprising difference in the way splits are handled here' why the splits are so different in either kind of tree node split requires three data itemsone to be kept in the node being splitone to move right into the new