we are using it to support the biggerprimary data structure we denote the dictionary stored at node of as (vthe entries we store in (vwill allow us to find which child node to move to next during search operation specificallyfor each node of twith children , and entries ( , )( - , - )we store in the dictionary (vthe entries ( ( ))( ( ))( - ( ))(phv )that isan entry ( ( , )of dictionary (vhas key and value ( note that the last entry stores the special key with the realization of the multi-way search tree aboveprocessing -node while searching for an entry of with key can be done by performing search operation to find the entry ( ,( , )in (vwith smallest key greater than or equal to we distinguish two casesif then we continue the search by processing child (note that if the special key is returnedthen is greater than all the keys stored at node vand we continue the search processing child otherwise ( = )then the search terminates successfully consider the space requirement for the above realization of multi-way search tree storing entries by proposition using any of the common realizations of ordered dictionaries (for the secondary structures of the nodes of tthe overall space requirement for is (nconsider next the time spent answering search in the time spent at -node of during search depends on how we realize the secondary data structure (vif (vis realized with sorted array (that isan ordered search table)then we can process in (logdtime if instead (vis realized using an unsorted list insteadthen processing takes (dtime let dmax denote the maximum number of children of any node of tand let denote the height of the search time in multi-way search tree is either (hd max or (hlogd max )depending on the specific implementation of the secondary structures at the nodes of (the dictionaries ( )if max is constantthe running time for performing search is ( )irrespective of the implementation of the secondary structures thusthe primary efficiency goal for multi-way search tree is to keep the height as small as possiblethat iswe want to be logarithmic function of nthe total number of entries stored in the dictionary search tree with logarithmic heightsuch as thisis called balanced search tree we discuss balanced search tree that caps max at next definition of ( , tree