node small and also keeps the primary multi-way tree balanced is the ( , treewhich is sometimes called - tree or tree this data structure achieves these goals by maintaining two simple properties (see figure )size propertyevery internal node has at most four children depth propertyall the external nodes have the same depth figure ( , tree againwe assume that external nodes are empty andfor the sake of simplicitywe describe our search and update methods assuming that external nodes are real nodesalthough this latter requirement is not strictly needed enforcing the size property for ( , trees keeps the nodes in the multi-way search tree simple it also gives rise to the alternative name tree,since it implies that each internal node in the tree has or children another implication of this rule is that we can represent the dictionary (vstored at each internal node using an unordered list or an ordered arrayand still achieve ( )-time performance for all operations (since max the depth propertyon the other handenforces an important bound on the height of ( , tree proposition the height of ( , tree storing entries is (log njustificationlet be the height of ( , tree storing entries we justify the proposition by showing that the claims / log( + )<= ( and