Java Reference
In-Depth Information
privateEfindhelp(TTNode<Key,E>root,Keyk){
if(root==null)returnnull; //valnotfound
if(k.compareTo(root.lkey())==0)returnroot.lval();
if((root.rkey()!=null)&&(k.compareTo(root.rkey())
==0))
returnroot.rval();
if(k.compareTo(root.lkey())<0) //Searchleft
returnfindhelp(root.lchild(),k);
elseif(root.rkey()==null) //Searchcenter
returnfindhelp(root.cchild(),k);
elseif(k.compareTo(root.rkey())<0)//Searchcenter
returnfindhelp(root.cchild(),k);
elsereturnfindhelp(root.rchild(),k);//Searchright
}
Figure10.11
Implementation for the 2-3 tree search method.
18
33
12
23
30
48
10
15
15
20
21
24
31
45
47
50
52
14
Figure10.12
Simple insert into the 2-3 tree of Figure 10.9. The value 14 is
inserted into the tree at the leaf node containing 15. Because there is room in the
node for a second key, it is simply added to the left position with 15 moved to the
right position.
again to search the root node. Because 15 is less than 18, the first (left) branch is
taken. At the next level, we take the second branch to the leaf node containing 15.
If the search key were 16, then upon encountering the leaf containing 15 we would
find that the search key is not in the tree. Figure 10.11 is an implementation for the
2-3 tree search method.
Insertion into a 2-3 tree is similar to insertion into a BST to the extent that the
new record is placed in the appropriate leaf node. Unlike BST insertion, a new
child is not created to hold the record being inserted, that is, the 2-3 tree does not
grow downward. The first step is to find the leaf node that would contain the record
if it were in the tree. If this leaf node contains only one value, then the new record
can be added to that node with no further modification to the tree, as illustrated in
Figure 10.12. In this example, a record with key value 14 is inserted. Searching
from the root, we come to the leaf node that stores 15. We add 14 as the left value
(pushing the record with key 15 to the rightmost position).
If we insert the new record into a leaf node L that already contains two records,
then more space must be created.
Consider the two records of node L and the
