# BST and AVL Trees Using Java Programming

## Question

Problem 1 (BST)
A text concordance BST is a BST of all the distinct words in a piece of text, and in this project we consider the problem of constructing one concordance for a document stored in a file. To construct such a concordance BST, we begin with an empty BST. As each word is read, we will check the list whether it is in current BST or not. If the word is a new word, it is inserted into the BST in the appropriate place. If the word you read appears in the BST already, the frequency of the word will be increased by one. Obviously, it may be necessary to insert words at any point in this BST. Each node consists of four fields, one for word, one for its frequency, and two for right/left child link (reference) fields.
Each time a word is read from a document, this BST must be searched, always beginning with the root node.
(The data type of the word field would be a string. If the word starts with non-alphabet (number or special symbol) do not insert it in the list. Also the characters of all words will be upper case only without any punctuation.)

ALGORITHM:

(* Input : A Text file (concordinput.txt)
Function : Construct a text concordance BST from a document stored in a file.
Output : A list of distinct words with their frequencies in an ascending alphabetic order. *)

Output
• The source file should be called CONCORD
• You will be expected to hand in the hard copy of your source files in a folder and output as well

Problem 2. (AVL Tree)

Write a program to maintain AVL tree.

Input: use a file, AVLinput.txt
+ 3 means inserting 3 into the current AVL tree if the new value is not in the current AVL tree.
- 5 means deleting 5 from the current AVL tree if 5 is in the AVL tree.

Output:
1. Print out the type of rotation for each insert/deleting operation, if it does.
2. Print out the final resulting AVL tree using an inorder traversal method with the height information of each node.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

public class AVL {
private Node root;

public AVL() {
root = null;
}

/**
* insert key to tree
* @param key
*/
public void insert(int key){

Node q = new Node(key);
insert(root, q);

}

/**
* insert key below node p
* @param p
* @param q
*/
public void insert(Node p, Node q){
if (p == null) {
root = q;
} else {

if (q.key < p.key ) { // go left
if (p.left == null) {
p.left = q;
q.parent = p;
System.out.println("Insert " + q.key);
recursiveBalance(p);

}else {...
\$93.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.