( , )-tree operations multiway search tree that keeps the secondary data structures stored at each node small and also keeps the primary multiway 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 multiway 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 secondary map stored at each internal node using an unordered list or an ordered arrayand still achieve ( )-time performance for all operations (since dmax the depth propertyon the other handenforces an important bound on the height of ( tree proposition the height of ( tree storing items is (log njustificationlet be the height of ( tree storing items we justify the proposition by showing the claim log( < <log( ( to justify this claim note first thatby the size propertywe can have at most nodes at depth at most nodes at depth and so on thusthe number of external nodes in is at most likewiseby the depth property and the definition