Java Reference
In-Depth Information
/ ** BinarySearchTreeimplementationforDictionaryADT * /
classBST<KeyextendsComparable<?superKey>,E>
implementsDictionary<Key,E>{
privateBSTNode<Key,E>root;//RootoftheBST
privateintnodecount; //NumberofnodesintheBST
/ ** Constructor * /
BST(){root=null;nodecount=0;}
/ ** Reinitializetree * /
publicvoidclear(){root=null;nodecount=0;}
/ ** Insertarecordintothetree.
@paramkKeyvalueoftherecord.
@parameTherecordtoinsert. * /
publicvoidinsert(Keyk,Ee){
root=inserthelp(root,k,e);
nodecount++;
}
/ ** Removearecordfromthetree.
@paramkKeyvalueofrecordtoremove.
@returnTherecordremoved,nullifthereisnone. * /
publicEremove(Keyk){
Etemp=findhelp(root,k); //Firstfindit
if(temp!=null){
root=removehelp(root,k);//Nowremoveit
nodecount--;
}
returntemp;
}
/ ** Removeandreturntherootnodefromthedictionary.
@returnTherecordremoved,nulliftreeisempty. * /
publicEremoveAny(){
if(root==null)returnnull;
Etemp=root.element();
root=removehelp(root,root.key());
nodecount--;
returntemp;
}
/ ** @returnRecordwithkeyvaluek,nullifnoneexist.
@paramkThekeyvaluetofind. * /
publicEfind(Keyk){returnfindhelp(root,k);}
/ ** @returnThenumberofrecordsinthedictionary. * /
publicintsize(){returnnodecount;}
}
Figure5.14 The binary search tree implementation.
Search WWH ::




Custom Search