notes examplehere is portion of -tree with order (nodes have at least keys and pointersnodes are delimited with [square bracketsthe keys are city namesand are kept sorted in each node on either side of every key are pointers linking the key to subsequent nodesstart here chicago hoboken ++ aptos boston denver detroit san-jose seattle to find the key "dallas"we begin searching at the top "rootnode "dallasis not in the node but sorts between "chicagoand "hoboken"so we follow the middle pointer to the next node again"dallasis not in the node but sorts before "denver"so we follow that node' first pointer down to the next node (marked with an " "eventuallywe will either locate the keyor encounter "leafnode at the bottom level of the -tree with no pointers to any lower nodes and without the key we wantindicating the key is nowhere in the -tree below is another fragment of an order -tree (nodes have at least key and pointerssearching for the key "chicagobegins at "marin"follows the first pointer to "aptos(since chicago sorts before marin)then follows that node' second pointer down to the next level (since chicago sorts after aptos)as marked with an "xv marin +--+--- aptos seattle searching -tree for key always begins at the root node and follows pointers from node to node until either the key is located or the search fails because leaf node is reached and there are no more pointers to follow -trees grow when new keys are inserted since the root node initially begins with just one keythe root node is special exception and the only node allowed to have less than keys in an order -tree here is an order -tree with integer keys except for the special root nodeorder requires every node to have from to keys and to pointers empty slots are marked with "showing where future keys have not yet been stored in the nodes ++ ++++ [ [ [ [ [ [ lovely professional university