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.