public class AVLTree { /* Implements a ALV tree of ints stored in a random acces
ID: 3740349 • Letter: P
Question
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
*/
public static final int CREATE = 0;
public static final int REUSE = 1;
private RandomAccessFile f;
private long root; //the address of the root node in the file
private long free; //the address in the file of the first node in the free list
private class Node {
private long left;
private long right;
private int data;
private int count;
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
}
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
root = insert(root, d);
}
private long insert(long r, int d) {
return r;
}
public int find(int d) throws IOException {
//if d is in the tree return the value of count associated with d
//otherwise return 0
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
}
}
Explanation / Answer
Hey,the question you are asking is a bit confusing.I think you are interseted in knowing about avl trees and its important functions like insertion and deletion.
I will provide you with the implementation of avl trees with two important functions-insertion and deletion.And the constructor part which you are asking will be covered as well.I hope you would like my answer.
-----------Insertion in avl tree along with implementation-----------
// Java program for insertion in AVL Tree
class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}
class AVLTree {
Node root;
// A function to get height of the tree
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
// A function to get maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// A function to right rotate subtree rooted with y
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
// Return new root
return x;
}
// A function to left rotate subtree rooted with x
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node N) {
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
//THE INSERT FUNCTION
Node insert(Node node, int key) {
/* 1. Perform the normal BST insertion */
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else // Duplicate keys not allowed
return node;
/* 2. Update height of this ancestor node */
node.height = 1 + max(height(node.left),
height(node.right));
/* 3. Get the balance factor of this ancestor
node to check whether this node became
unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then there
// are 4 cases Left Left Case
if (balance > 1 && key < node.left.key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node.right.key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
void preOrder(Node node) {
if (node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
/* Constructing tree given in the above figure */
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
/* The constructed AVL Tree would be
30
/
20 40
/
10 25 50
*/
System.out.println("Preorder traversal" +
" of constructed tree is : ");
tree.preOrder(tree.root);
}
}
Preorder traversal of the constructed AVL tree is
30 20 10 25 40 50
-----------------DELETION---------------------
All the above code will be same and two new functions will be introduced for the deletion or remove in avl tree.
/* Given a non-empty binary search tree, return the
node with minimum key value found in that tree.
Note that the entire tree does not need to be
searched. */
Node minValueNode(Node node)
{
Node current = node;
/* loop down to find the leftmost leaf */
while (current.left != null)
current = current.left;
return current;
}
Node deleteNode(Node root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == null)
return root;
// If the key to be deleted is smaller than
// the root's key, then it lies in left subtree
if (key < root.key)
root.left = deleteNode(root.left, key);
// If the key to be deleted is greater than the
// root's key, then it lies in right subtree
else if (key > root.key)
root.right = deleteNode(root.right, key);
// if key is same as root's key, then this is the node
// to be deleted
else
{
// node with only one child or no child
if ((root.left == null) || (root.right == null))
{
Node temp = null;
if (temp == root.left)
temp = root.right;
else
temp = root.left;
// No child case
if (temp == null)
{
temp = root;
root = null;
}
else // One child case
root = temp; // Copy the contents of
// the non-empty child
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
Node temp = minValueNode(root.right);
// Copy the inorder successor's data to this node
root.key = temp.key;
// Delete the inorder successor
root.right = deleteNode(root.right, temp.key);
}
}
// If the tree had only one node then return
if (root == null)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root.height = max(height(root.left), height(root.right)) + 1;
// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
// this node became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && getBalance(root.left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 && getBalance(root.left) < 0)
{
root.left = leftRotate(root.left);
return rightRotate(root);
}
// Right Right Case
if (balance < -1 && getBalance(root.right) <= 0)
return leftRotate(root);
// Right Left Case
if (balance < -1 && getBalance(root.right) > 0)
{
root.right = rightRotate(root.right);
return leftRotate(root);
}
return root;
}
I hope,my solution would have helped you.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.