Implement an AVL tree of ints stored in a random access file

The format of the file is shown on the next slide

The methods you must implement are shown on the

following slides.

Duplicates can be entered in the tree and will be recorded with a count value like we did in class

Your 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 to the file.

You must create a main method to test your code. I will create my own test driver.

REPRESENTATION OF AVL TREE

//The first Number is the address, followed by the Data, Count, Height, Left, Right

Address Contents

Root 0 128

FREE 8 72

16 150 3 1 296 212

44 184

72 240

100 10 1 0 0 0

128 80 2 3 324 268

156 300 4 0 0 0

184 0

212 175 2 0 0 0

240 44

268 200 1 2 16 156

296 125 3 0 0 0

324 50 2 1 100 0

SKELETON CODE

import java.io.*;

import java.util.*;

public class AVLTree { /* * Implements a ALV tree of ints stored in a random access file. Duplicates * are recorded by a count field associated with the int */ final int CREATE = 0; final int REUSE = 1; private RandomAccessFile f; long root; // the address of the root node in the file long free; // the address in the file of the first node in the free list

private class Node { private long left; private int data; private int count; private long right; private int height;

private Node(long L, int d, long r) { // 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 mode) throws IOException { // if mode is CREATE a new empty file is created // if mode is CREATE and a file with file name fname exists the file // with // fname must be deleted before the new empty file is created // if mode is REUSE an existing file is used if it exists otherwise a // new empty // file is created }

public void insert(int d) throws IOException {

// insert d into the tree // if d is in the tree increment the count field associated with d }

public int find(int d) throws IOException { return d; // if d is in the tree return the value of count associated with d // //otherwise return 0 }

public void removeOne(int d) throws IOException { // remove one copy of d // from the tree // if the copy is the last copy remove d from the tree //if d is not in // the tree the method has no effect }

public void removeAll(int d) throws IOException { // remove d from the tree // if d is not in the tree the method has no effect }

public void close() { // close the random access file // before closing update the values of root and free if necessary } }

SIDE NOTE ABOUT FREE LIST

When a node is removed from the tree the space for that node must be added to the free list