each one searchinsertionor deletionstarting from splay tree with zero keys alsolet (idenote the number of times the entry is accessed in the splay treethat isits frequencyand let denote the total number of entries assuming that each entry is accessed at least oncethen the total running time for performing the sequence of operations is we omit the proof of this propositionbut it is not as hard to justify as one might imagine the remarkable thing is that this proposition states that the amortized running time of accessing an entry is (log( / ( )) ( , trees some data structures we discuss in this including ( , treesare multi-way search treesthat istrees with internal nodes that have two or more children thusbefore we define ( , treeslet us discuss multi-way search trees multi-way search trees recall that multi-way trees are defined so that each internal node can have many children in this sectionwe discuss how multi-way trees can be used as search trees recall that the entries that we store in search tree are pairs of the form ( , )where is the key and is the value associated with the key howeverwe do not discuss how to perform updates in multi-way search trees nowsince the details for update methods depend on additional properties we wish to maintain for multi-way treeswhich we discuss in section definition of multi-way search tree let be node of an ordered tree we say that is -node if has children we define multi-way search tree to be an ordered tree that has the following propertieswhich are illustrated in figure aeach internal node of has at least two children that iseach internal node is -node such that each internal -node of with children stores an ordered set of key-value entries ( , )( , )where << let us conventionally define and for each entry ( ,xstored at node in the subtree of rooted at ,dwe have that <= <ki