trees and external storage all children in the subtree rooted at child have key values greater than key but less than key all children in the subtree rooted at child have key values greater than key this relationship is shown in figure duplicate values are not usually permitted in treesso we don' need to worry about comparing equal keys nodes with keys less than figure nodes with keys between and nodes with keys between and nodes with keys greater than keys and children refer back to the tree in figure as in all treesthe leaves are all on the same level (the bottom rowupper-level nodes are often not fullthat isthey may contain only one or two data items instead of three alsonotice that the tree is balanced it retains its balance even if you insert sequence of data in ascending (or descendingorder the tree' self-balancing capability results from the way new data items are insertedas we'll see in moment searching tree finding data item with particular key is similar to the search routine in binary tree you start at the root andunless the search key is found thereselect the link that leads to the subtree with the appropriate range of values for exampleto search for the data item with key in the tree in figure you start at the root you search the root but don' find the item because is larger than you go to child which we will represent as (remember that child is on the right because the numbering of children and links starts at on the left you don' find the data item in this node eitherso you must go to the next child herebecause is greater than but less than you go again to child this time you find the specified item in the link insertion new data items are always inserted in leaveswhich are on the bottom row of the tree if items were inserted in nodes with childrenthe number of children would need to be changed to maintain the structure of the treewhich stipulates that there should be one more child than data items in node