Indexing - Data Structures and Algorithm Analysis - page 356

/ ** Addanewkey/valuepairtothenode.Theremightbea
subtreeassociatedwiththerecordbeingadded.This
informationcomesintheformofa2-3treenodewith
onekeyanda(possiblynull)subtreethroughthe
centerpointerfield. * /
publicTTNode<Key,E>add(TTNode<Key,E>it){
if(rkey==null){//Onlyonekey,addhere
if(lkey.compareTo(it.lkey())<0){
rkey=it.lkey();rval=it.lval();
right=center;center=it.cchild();

}
else{
rkey=lkey;rval=lval;right=center;
lkey=it.lkey();lval=it.lval();
center=it.cchild();

}
returnthis;

}
elseif(lkey.compareTo(it.lkey())>=0){//Addleft
center=newTTNode<Key,E>(rkey,rval,null,null,
center,right,null);
rkey=null;rval=null;right=null;
it.setLeftChild(left);left=it;
returnthis;

}
elseif(rkey.compareTo(it.lkey())<0){//Addcenter
it.setCenterChild(newTTNode<Key,E>(rkey,rval,null,
null,it.cchild(),right,null));
it.setLeftChild(this);
rkey=null;rval=null;right=null;
returnit;

}
else{//Addright
TTNode<Key,E>N1=newTTNode<Key,E>(rkey,rval,null,
null,this,it,null);

it.setLeftChild(right);
right=null;rkey=null;rval=null;
returnN1;

}

}

Figure10.16 The 2-3 tree node add method.