search tree figure illustrates two searchesone that is successful and one that is not the search operation for the - tree is implemented in listing listing searching - tree class tree map def searchsubtreetarget )if we encounter null pointerthe target is not in the tree if subtree is none return none see if the node contains the key if soreturn the data elif subtree hashkeytarget return subtree getdatatarget otherwisetake the appropriate branch else branch subtree getbranchtarget return searchbranchtarget null (asuccessful search for key (bunsuccessful search for key figure searching - tree insertions the process of inserting key into - tree is similar to that of binary search treealthough it' more complicated the first step is to search for the key as if it were in the tree as we saw in the previous sectionthe search for non-existent key will lead us to leaf node the next step is to determine if there is space in the leaf for the new key if the leaf contains single keywe can easily insert the key into the node consider the partial - tree illustrated in figure and suppose we want to insert key value in searching for we end up at the node containing value since there is space in this node can be added as the node' second key but what if the new key is less than the key stored in the leaf nodesuppose we want to add key to the treeas shown in figure the search leads us to the leaf node containing value when the new key is smaller than the existing keythe new key is inserted as the first key and the existing one is moved to become the second key