in java
implement an AVL tree stored in a random access file
each node contatins an integer key, one or more fixed length character strings, one or more integers, a left child reference, a right child reference and a height
methods must be implemented in this way
duplicate keys cannot be entred in tree
implementation must not load the whole tree in memory, each operation only makes copies of the nodes it needs for that operation, modified nodes must be written back to the file
there is a test driver given
import java.io.*; import java.util.*; public class AVLTree { private RandomAccessFile f; private long root; //the address of the root node in file private long free; //the address in the file of the first node in the free list private int numStringFields; private int fieldLengths[]; private int numIntFields; private class Node { private int key; private char stringFields[][]; private int intFields[]; private long left; private long right; private int height; private Node(long l, int d, long r, char sFields[][], int iFields[]) { //Constructor for a new Node }private Node(long addr) throws IOException { //constructor for a node that exists and is stored in the file
}
private void writeNode(long addr) throws IOException { //writes the node to the file at location addr
}
public AVLTree(String fname, int stringFieldLengths[], int numIntField) throws IOException { //creates a new empty AVL Tree stored in the file fname //the number of character string fields is stringFieldLengths.length //stringFieldLengths contains the length of each string field
}
public AVLTree(String fname) throws IOException { //reuse an existing tree store in the file fname
}
public void insert(int k, char sFields[][], int iFields[]) throws IOException { //PRE: the number and lengths of the sFields and iFields match the expected number and lengths //insert k and the fields into the tree //the string fields are null ('\0') padded //if k is in the tree do nothing
}
public void print() throws IOException { //Print the contents of the nodes in the tree in ascending order of the key //do not print the null characters
}
public LinkedList intFind(int k) throws IOException { //if k is in the tree return a linked list of the integer fields associated with k //otherwise return null
}
public void remove(int k) throws IOException { //if k is in the tree remove the node with key k from the tree //otherwise do nothing
}
public void close() throws IOException { //update root and free in the file(if necessary) //close the random access file
}
AVL TESTER
import java.io.*; import java.util.*; public class AVLTest { public void test1(int nums[], int len) throws IOException { //this test does not require any rotations and only removes leaves System.out.println("Start test 1"); int i; int sFieldLens[] = {10, 15}; AVLTree a = new AVLTree("t1", sFieldLens, 2); char sFields[][] = new char[2][]; int iFields[] = new int[2]; for ( i = 0; i < len;="" i++)="" {="" sfields[0]="Arrays.copyOf((new" integer(nums[i])).tostring().tochararray(),="" 10);="" sfields[1]="Arrays.copyOf((new" integer(nums[i])).tostring().tochararray(),="" 15);="" ifields[0]="iFields[1]" =="" nums[i];="" a.insert(nums[i],="" sfields,="" ifields);="" }="" system.out.println("past="" inserts="" in="" test="" 1");="" a.print();="" system.out.println("past="" first="" print="" in="" test="" 1");="" for="" (="" i="len-1;" i=""> 2; i--) { a.remove(nums[i]); } System.out.println("Past first removes in test 1"); a.print(); System.out.println("Past second print in test 1"); a.close(); a = new AVLTree("t1"); System.out.println("Past close and reopen"); a.print(); a.remove(nums[2]); a.remove(nums[1]); a.remove(nums[0]); sFields[0] = Arrays.copyOf("Root".toCharArray(), 10); sFields[1] = Arrays.copyOf("Node Only".toCharArray(), 15); iFields[0] = iFields[1] = 999; a.insert(999, sFields, iFields); a.print(); a.close(); }public static void main(String args[]) throws IOException { AVLTest test = new AVLTest(); Scanner scan = new Scanner(System.in); System.out.print("Enter the maximum value to use for tests 1 and 2: "); int max = scan.nextInt(); System.out.print("Enter the depth of the tree for tests 1: "); int levels = scan.nextInt(); int nums[] = new int[max]; int start, increment, i; int j = 0; int divisor = 2; while (levels > 0) { start = max/divisor; increment = 2*start; for (i = start; i < max;="" i="i+increment)" {="" nums[j]="i;" j++;="" }="" divisor="divisor*2;" levels--;="" }="" as="" an="" example="" the="" data="" generated="" by="" the="" above="" code="" when="" 100="" is="" the="" max="" and="" depth="" is="" 3="" is="" 50,="" 25,="" 75,="" 12,="" 36,="" 60,="" 84="" the="" depth="" should="" be="" less="" than="" log="" max="" (log="" base="" 2)="" test.test1(nums,="">
}
}