list trees and external storage hash tables heaps trees and external storage overview in binary treeeach node has one data item and can have up to two children if we allow more data items and children per nodethe result is multiway tree treesto which we devote the first part of this are multiway trees that can have up to four children and three data items per node trees are interesting for several reasons firstthey're balanced trees like red-black trees they're slightly less efficient than red-black treesbut easier to program secondand most importantlythey serve as an easy-to-understand introduction to -trees -tree is another kind of multiway tree that' particularly useful for organizing data in external storage (external means external to main memoryusually this is disk drive node in -tree can have dozens or hundreds of children we'll discuss external storage and -trees in the second part of this introduction to trees in this section we'll look at the characteristics of trees later we'll see how workshop applet models treeand how we can program tree in java we'll also look at the surprisingly close relationship between trees and red-black trees figure shows small tree each lozenge-shaped node can hold onetwoor three data items figure tree here the top three nodes have childrenand the six nodes on the bottom row are all leaf nodeswhich by definition have no children in tree all the leaf nodes are always on the same level