sec - trees figure - tree are greater than or equal to the value of the first key if there is right subtree (equivalentlyif the node stores two keys)then the values of all descendants in the center subtree are less than the value of the second keywhile values in the right subtree are greater than or equal to the value of the second key to maintain these shape and search properties requires that special action be taken when nodes are inserted and deleted the - tree has the advantage over the bst in that the - tree can be kept height balanced at relatively low cost figure illustrates the - tree nodes are indicated as rectangular boxes with two key fields (these nodes actually would contain complete records or pointers to complete recordsbut the figures will show only the keys internal nodes with only two children have an empty right key field leaf nodes might contain either one or two keys figure is class declaration for the - tree node note that this sample declaration does not distinguish between leaf and internal nodes and so is space inefficientbecause leaf nodes store three pointers each the techniques of section can be applied here to implement separate internal and leaf node types from the defining rules for - trees we can derive relationships between the number of nodes in the tree and the depth of the tree - tree of height has at least - leavesbecause if every internal node has two children it degenerates to the shape of complete binary tree - tree of height has at most - leavesbecause each internal node can have at most three children searching for value in - tree is similar to searching in bst search begins at the root if the root does not contain the search key kthen the search progresses to the only subtree that can possibly contain the value(sstored in the root node determine which is the correct subtree for exampleif searching for the value in the tree of figure we begin with the root node because is between and it can only be in the middle subtree searching the middle child of the root node yields the desired record if searching for then the first step is again to search the root node because is less than the first (leftbranch is