これは、テキストを解析し、すべての一意の単語、単語が出現する行番号、および出現回数を出力するために使用している 3 つのツリーの 1 つです。私はすでにハッシュとツリーマップを使用しており、両方とも正しく機能しています。私のインストラクターは、3 番目のマップには AVL ツリーを使用する必要があると言って、コードを提供してくれました。ここはどこに行こうか迷うところです。AVL マップと AVL マップ クラスを作成/塗りつぶすメソッドを含めます。さらにコードが必要な場合は、喜んで含めます。
public void avlMap(String fileName){
//try/catch block to check for invalid file name
try{
//creates new bufferedreader object for input file
BufferedReader inFile = new BufferedReader(new FileReader(fileName));
//creates new treeMap object named avlMap
Map avlMap = new AvlMap();
String oneLine;
//Read the words and add them to the avlMap
for (int lineNum = 1; (oneLine = inFile.readLine()) != null; lineNum++){
String delims = " !@#$%{}[]/^&*,.()-;:\'\"\t";
StringTokenizer st = new StringTokenizer(oneLine, delims);
while (st.hasMoreTokens()){
String word = st.nextToken();
WordStats stats = (WordStats) avlMap.get(word);
//if WordStats is empty/doesnt exist,
//if exists, adds line numbers into a WordStats in the value
//...field for the int's respective key
if (stats == null){
stats = new WordStats();
avlMap.put(word, stats);
}
//WordStats already exists for the word
//calls addOccurrence method and adds the line number
stats.addOccurrence(new Integer(lineNum));
}
}
//creates a new iterator object to iterate entries
Iterator itr = avlMap.entrySet().iterator();
//runs printEntry for each key in the treeMap
while (itr.hasNext()){
printEntry((Map.Entry) itr.next());
}
}
//the file name used wasn't able to be reached
catch(IOException e){
e.printStackTrace();
}
}
AvlMap クラス。非常に長いことは承知していますが、メソッドは、私が使用してきた他のマップ クラスとほぼ同じようです。
public class AvlMap <AnyType extends Comparable<? super AnyType>> implements Map
{
//construct the tree
public AvlMap( ){
root = null;
}
//inserts object into the map
public void insert( AnyType x, AnyType y ){
root = insert( x, y, root );
}
//removes the key from the map
public void remove( AnyType x ){
root = remove( x, root );
}
//internal method to remove from a subtree
private AvlNode<AnyType> remove( AnyType x, AvlNode<AnyType> t ){
if( t == null )
return t; // Item not found; do nothing
int compareResult = x.compareTo( t.key );
if( compareResult < 0 )
t.left = remove( x, t.left );
else if( compareResult > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.key = findMin( t.right ).key;
t.right = remove( t.key, t.right );
}
else
t = ( t.left != null ) ? t.left : t.right;
return balance( t );
}
//returns the smallest item in the tree
public AnyType findMin( ){
if( isEmpty( ) )
throw new UnderflowException("Error" );
return findMin( root ).key;
}
//returns the largest item in the tree
public AnyType findMax( ){
if( isEmpty( ) )
throw new UnderflowException("Error" );
return findMax( root ).key;
}
//finds the provided item in the tree
public boolean contains( AnyType key ){
return contains( key, root );
}
//make the tree empty
public void makeEmpty( ){
root = null;
}
//tests if the tree is empty
public boolean isEmpty( ){
return root == null;
}
//prints the tree in sorted order
public void printTree( ){
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}
private static final int ALLOWED_IMBALANCE = 1;
// Assume t is either balanced or within one of being balanced
private AvlNode<AnyType> balance( AvlNode<AnyType> t )
{
if( t == null )
return t;
if( height( t.left ) - height( t.right ) > ALLOWED_IMBALANCE )
if( height( t.left.left ) >= height( t.left.right ) )
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
else
if( height( t.right ) - height( t.left ) > ALLOWED_IMBALANCE )
if( height( t.right.right ) >= height( t.right.left ) )
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
return t;
}
//checks the trees balance
public void checkBalance( ){
checkBalance( root );
}
//driver for checking the trees balance
private int checkBalance( AvlNode<AnyType> t ){
if( t == null )
return -1;
if( t != null )
{
int hl = checkBalance( t.left );
int hr = checkBalance( t.right );
if( Math.abs( height( t.left ) - height( t.right ) ) > 1 ||
height( t.left ) != hl || height( t.right ) != hr )
System.out.println( "OOPS!!" );
}
return height( t );
}
//method to insert into a subtree
private AvlNode<AnyType> insert( AnyType key, AnyType value, AvlNode<AnyType> t ){
if( t == null )
return new AvlNode<>( key, value, null, null );
int compareResult = key.compareTo( t.key );
if( compareResult < 0 )
t.left = insert( key, value,t.left );
else if( compareResult > 0 )
t.right = insert( key, value, t.right );
else
; // Duplicate; do nothing
return balance( t );
}
//returns the smallest item in a subtree
private AvlNode<AnyType> findMin( AvlNode<AnyType> t )
{
if( t == null )
return t;
while( t.left != null )
t = t.left;
return t;
}
//finds the largest item in a subtree
private AvlNode<AnyType> findMax( AvlNode<AnyType> t ){
if( t == null )
return t;
while( t.right != null )
t = t.right;
return t;
}
//finds an item in a subtree
private boolean contains( AnyType x, AvlNode<AnyType> t ){
while( t != null ){
int compareResult = x.compareTo( t.key );
if( compareResult < 0 )
t = t.left;
else if( compareResult > 0 )
t = t.right;
else
return true; // Match
}
return false; // No match
}
//prints the subtree in sorted order
private void printTree( AvlNode<AnyType> t ){
if( t != null ){
printTree( t.left );
System.out.println( t.key + " " + t.value );
printTree( t.right );
}
}
//returns the height of node t or -1 if null
private int height( AvlNode<AnyType> t ){
return t == null ? -1 : t.height;
}
//rotates tree node with left child
private AvlNode<AnyType> rotateWithLeftChild( AvlNode<AnyType> k2 ){
AvlNode<AnyType> k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = Math.max( height( k1.left ), k2.height ) + 1;
return k1;
}
//rotates tree node with right child
private AvlNode<AnyType> rotateWithRightChild( AvlNode<AnyType> k1 ){
AvlNode<AnyType> k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = Math.max( height( k2.right ), k1.height ) + 1;
return k2;
}
//double rotates tree node. first left child with its right child, then
//...node k3 with new left child.
private AvlNode<AnyType> doubleWithLeftChild( AvlNode<AnyType> k3 ){
k3.left = rotateWithRightChild( k3.left );
return rotateWithLeftChild( k3 );
}
//double rotates tree node. first right child with its left child, then
//...node k1 with new right child
private AvlNode<AnyType> doubleWithRightChild( AvlNode<AnyType> k1 ){
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}
private static class AvlNode<AnyType>{
// Constructors
@SuppressWarnings("unused")
AvlNode( AnyType theKey, AnyType theValue ){
this( theKey, theValue, null, null );
}
AvlNode( AnyType theKey, AnyType theValue, AvlNode<AnyType> lt, AvlNode<AnyType> rt ){
key = theKey;
value = theValue;
left = lt;
right = rt;
height = 0;
}
AnyType key; // The data in the node
AnyType value;
AvlNode<AnyType> left; // Left child
AvlNode<AnyType> right; // Right child
int height; // Height
}
//trees root
private AvlNode<AnyType> root;
//implemented methods for AvlTreeMap
@Override
public void clear() {
makeEmpty();
}
@SuppressWarnings("unchecked")
@Override
public boolean containsKey(Object key) {
contains ((AnyType)key);
return false;
}
@SuppressWarnings("unchecked")
@Override
public boolean containsValue(Object value) {
contains ((AnyType)value);
return false;
}
@Override
public Set entrySet() {
return null;
}
@Override
public Object get(Object key) {
return key;
}
@Override
public Set keySet() {
return null;
}
@SuppressWarnings("unchecked")
@Override
public Object put(Object key, Object value) {
insert ((AnyType)key, (AnyType) value);
return true;
}
@Override
public void putAll(Map m) {
}
@SuppressWarnings("unchecked")
@Override
public Object remove(Object key) {
remove ((AnyType)key);
return null;
}
@Override
public int size() {
return 0;
}
@Override
public Collection values() {
return null;
}
}
すべてをセットに保存し、発生を保持する WordStats クラスを次に示します。
import java.util.SortedSet;
import java.util.TreeSet;
public class WordStats {
private int occurrences;
private SortedSet<Integer> lineNumbers = new TreeSet<Integer>();
public void addOccurrence(int lineNumber){
occurrences++;
lineNumbers.add(lineNumber);
}
public int getOccurrences(){
return occurrences;
}
public SortedSet<Integer> getLines(){
return lineNumbers;
}
}
プログラムを実行すると、次のエラーが表示されます。
スレッド「メイン」での例外
java.lang.ClassCastException:
java.lang.StringにキャストできませんWordStatsで
driver1.avlMap(driver1.java:182)で
driver1.main(driver1.java:36)
あなたが提供できる洞察を前もって感謝します。また、コンパイル エラーもありません。