Question

In: Computer Science

AVL Group assignment POST ANSWER IN JAVA PLS Populate a tree via a text file (input.txt)...

AVL Group assignment

POST ANSWER IN JAVA PLS

Populate a tree via a text file (input.txt) Make sure that after every insert, the tree is balanced. At the end, display the tree in level format. Make sure to include the height and the balance factor of every node in your output. Redirect the display to an output file (output.txt)

Hint:

//I will not accept any other algorithm

//This is not a recursive algorithm

node * rebalance(node *node){

node->height = max(height(node->left), height(node->right)) + 1;

int balance = getBalance(node); //node->left - node->right

/*do rotations as necessary

If Left heavy outside : return rightRotate(node);

If right heavy outside: return leftRotate(node);

If left heavy inside: left rotation first, right rotation 2nd, return top node

node->left = leftRotate(node->left);

return rightRotate(node);

if right heavy inside: right rotation first, left rotation 2nd, return top node

node->right = rightRotate(node->right);

return leftRotate(node);

if no rotation, return node

*/

}

//non-tail recursive algorithm because of rebalance

node* insert(node* node, int key)

{

//recursive Code for inserting a node

//When insert happens set height to 0 for the node

if (node == NULL)

return(newNode(key));

if (key < node->key)

node->left = insert(node->left, key);

else

node->right = insert(node->right, key);

node=rebalance(node); //update heights and rebalance

return node;

}

node *leftRotate(node *x){

struct node *y=x->right;

//add more code to rotate to the left, update heights for x and y

//return y

}

node *rightRotate(node *x){

struct node *y=x->left;

//add more code to rotate to the right, update heights for x and y

//return y

}

POST ANSWER IN JAVA PLS

Expert Solution

Assuming that the data is present in a text file "data.txt".

```
class SBBSTNodes
```
```
{
```
```
    SBBSTNodes left, right;
```
```
    int        data;
```
```
    int        height;
```
```
 
```
```
    public SBBSTNodes()
```
```
    {
```
```
        left = null;
```
```
        right = null;
```
```
        data = 0;
```
```
        height = 0;
```
```
    }
```
```
 
```
```
    public SBBSTNodes(int n)
```
```
    {
```
```
 
```
```
        left = null;
```
```
        right = null;
```
```
        data = n;
```
```
        height = 0;
```
```
    }
```
```
}
```
```
 
```
```
class SelfBalancingBinarySearchTrees
```
```
{
```
```
    private SBBSTNodes root;
```
```
 
```

    public SelfBalancingBinarySearchTrees()

```
    {
```
```
        root = null;
```
```
    }
```
```
 
```
```
    public boolean isEmpty()
```
```
    {
```
```
        return root == null;
```
```
    }
```
```
 
```
```
    public void clear()
```
```
    {
```
```
        root = null;
```
```
    }
```

static void printLevelOrder(SBBSTNodes root)

{

int h = height(root);

int i;

for (i=1; i<=h; i++)

{

printGivenLevel(root, i,i);

System.out.println();

}

/* Print nodes at a given level */

void printGivenLevel(SBBSTNodes root, int level, int height)

{

if (root == null)

return;

if (level == 1){

System.out.println(root.data);

System.out.println("height is"+ height);}

else if (level > 1)

{

printGivenLevel(root.left, level-1,height);

printGivenLevel(root.right, level-1,height);

}

public level_order_traversal(){
printlevelorder(root);
}
```
    public void insert(int data)
```
```
    {
```
```
        root = insert(data, root);
```
```
    }
```
```
 
```
```
    private int height(SBBSTNodes t)
```
```
    {
```
```
 
```

        return t == null ? -1 : t.height;

```
    }
```
```
 
```
```
    private int max(int lhs, int rhs)
```
```
    {
```
```
        return lhs > rhs ? lhs : rhs;
```
```
    }
```
```
 
```

    private SBBSTNodes insert(int x, SBBSTNodes t)

```
    {
```
```
        if (t == null)
```
```
            t = new SBBSTNodes(x);
```
```
        else if (x < t.data)
```
```
        {
```
```
            t.left = insert(x, t.left);
```

            if (height(t.left) - height(t.right) == 2)

```
                if (x < t.left.data)
```

                    t = rotateWithLeftChild(t);

```
                else
```

                    t = doubleWithLeftChild(t);

```
        } else if (x > t.data)
```
```
        {
```

            t.right = insert(x, t.right);

            if (height(t.right) - height(t.left) == 2)

```
                if (x > t.right.data)
```

                    t = rotateWithRightChild(t);

```
                else
```

                    t = doubleWithRightChild(t);

```
        } else
```
```
            ;
```

        t.height = max(height(t.left), height(t.right)) + 1;

```
        return t;
```
```
    }
```
```
 
```

    private SBBSTNodes rotateWithLeftChild(SBBSTNodes k2)

```
    {
```
```
        SBBSTNodes k1 = k2.left;
```
```
        k2.left = k1.right;
```
```
        k1.right = k2;
```

        k2.height = max(height(k2.left), height(k2.right)) + 1;

        k1.height = max(height(k1.left), k2.height) + 1;

```
        return k1;
```
```
    }
```
```
 
```

    private SBBSTNodes rotateWithRightChild(SBBSTNodes k1)

```
    {
```
```
        SBBSTNodes k2 = k1.right;
```
```
        k1.right = k2.left;
```
```
        k2.left = k1;
```

        k1.height = max(height(k1.left), height(k1.right)) + 1;

        k2.height = max(height(k2.right), k1.height) + 1;

```
        return k2;
```
```
    }
```
```
 
```

    private SBBSTNodes doubleWithLeftChild(SBBSTNodes k3)

```
    {
```

        k3.left = rotateWithRightChild(k3.left);

```
        return rotateWithLeftChild(k3);
```
```
    }
```
```
 
```

    private SBBSTNodes doubleWithRightChild(SBBSTNodes k1)

```
    {
```

        k1.right = rotateWithLeftChild(k1.right);

        return rotateWithRightChild(k1);

```
    }
```
```
 
```
```
    public int countNodes()
```
```
    {
```
```
        return countNodes(root);
```
```
    }
```
```
 
```

    private int countNodes(SBBSTNodes r)

```
    {
```
```
        if (r == null)
```
```
            return 0;
```
```
        else
```
```
        {
```
```
            int l = 1;
```
```
            l += countNodes(r.left);
```
```
            l += countNodes(r.right);
```
```
            return l;
```
```
        }
```
```
    }
```
```
 
```
```
    public boolean search(int val)
```
```
    {
```
```
        return search(root, val);
```
```
    }
```
```
 
```

    private boolean search(SBBSTNodes r, int val)

```
    {
```
```
        boolean found = false;
```
```
        while ((r != null) && !found)
```
```
        {
```
```
            int rval = r.data;
```
```
            if (val < rval)
```
```
                r = r.left;
```
```
            else if (val > rval)
```
```
                r = r.right;
```
```
            else
```
```
            {
```
```
                found = true;
```
```
                break;
```
```
            }
```
```
            found = search(r, val);
```
```
        }
```
```
        return found;
```
```
    }   
```
```
public class Balanced_B_Tree
```
```
{
```

    public static void main(String[] args)

```
    {
```
Scanner scanner = new Scanner(new File("data.txt"))

        SelfBalancingBinarySearchTrees sbbst = new SelfBalancingBinarySearchTrees();

        System.out.println("Self Balancing Tree\n");         

        while(scanner.hasNextInt()){

              sbbst.insert(scan.nextInt());

}

        scan.close();
        sbbst.level_order_traversal();

venereology answered 6 months ago

Write a program in Java that reads an input text file (named: input.txt) that has several...

Write a program in Java that reads an input text file (named: input.txt) that has several lines of text and put those line in a data structure, make all lowercase letters to uppercase and all uppercase letters to lowercase and writes the new lines to a file (named: output.txt).

For c language. I want to read a text file called input.txt for example, the file...

For c language. I want to read a text file called input.txt for example, the file has the form. 4 hello goodbye hihi goodnight where the first number indicates the n number of words while other words are separated by newlines. I want to store these words into a 2D array so I can further work on these. and there are fewer words in the word file than specified by the number in the first line of the file, then...

AVL tree; Insert and Range Minimum operation in Java code.

Write a non recursive method to insert into an AVL tree in Java

How do you implement an AVL tree for strings in Java?

AVL trees in Java For a given adjacency matrix of a rooted tree you need to...

AVL trees in Java For a given adjacency matrix of a rooted tree you need to decide whether this tree can be labeled to become an avl tree. Vertices of the tree do not have keys but numbered from 0 to n − 1 in order to write the adjacency matrix. INPUT format: The input consists of blocks. Blocks are written one after another without empty lines between them. Every block starts with a new line and consists of several...

using java, parse a text file to answer the following question: -list sentences with the maximum...

using java, parse a text file to answer the following question: -list sentences with the maximum number of occurences of the word “the” in the whole file and also list the corresponding frequency. (cannot use hash maps) example output: the:3:The day had came to leave before the storm. What hit the back bumper of the car before the window cracked? The classroom doors where shut closed before the students open the project.

Allow the main process to generate a text file containing the text of this assignment. The...

Allow the main process to generate a text file containing the text of this assignment. The main process will then create two other processes and pass to them the name of the file and two codes (code1 and code2) using a pipe() system call. The codes are two different alphabetic letters such as “a” and “k”. The child processes should search the file for the character in the interval received, compute their frequencies and return them through a separate pipe...

Write a java program: Write a program that creates a text file. Write to the file...

Write a java program: Write a program that creates a text file. Write to the file three lines each line having a person's name. In the same program Append to the file one line of 'Kean University'. In the same program then Read the file and print the four lines without lines between.

Java - Text File to Arrays and output ------------------------------------------------------------------------------ I need to have a java program...

Java - Text File to Arrays and output ------------------------------------------------------------------------------ I need to have a java program read an "input.txt" file (like below) and store the information in an respective arrays. This input.txt file will look like below and will be stored in the same directory as the java file. The top line of the text represents the number of people in the group for example. the lines below it each represent the respective persons preferences in regards to the other...