Question

**Write code in java**

Implement a method to build an AVL tree out of a sorted
(ascending order) array of *unique* integers, with the
fastest possible big O running time. You may implement private
helper methods as necessary. If your code builds a tree that is
other than an AVL tree, you will not get any credit. If your code
builds an AVL tree, but is not the fastest big O implementation,
you will get at most 12 points. You may use any of the
**Math** class methods (max, min, abs, etc.) as
needed.

**Hint**: Given that the input array is sorted,
think of how you might build the tree without doing any
rotations.

public class AVLTreeNode {

public int key;

public AVLTreeNode left, right;

public char balanceFactor; // ‘/’, ‘\’, or ‘-‘

public AVLTreeNode(key, left, right) {

this.key = key;

this.left = left;

this.right = right;

height = 0;

balanceFactor = ‘-‘;

}

}

// builds an AVL tree out of a sorted array of integer keys,

// returns the root of the tree, null if array is empty

public static AVLTreeNode buildAVLTree(int[] arr) {

// COMPLETE THIS METHOD

}

Answer #1

ANSWERI

have used **O(n)** approach.

AVLTreeNode buildHelper(int[] arr, int start, int end) { if (start > end) { return null; } /* Get the middle element and make it root */ int mid = (start + end) / 2; /* left subtree */ AVLTreeNode left = buildHelper(arr, start, mid - 1); /* right subtree */ AVLTreeNode right = buildHelper(arr, mid + 1, end); AVLTreeNode node = new AVLTreeNode(arr[mid],left,right); return node; } public static AVLTreeNode buildAVLTree(int[] arr) { int n = arr.length; if(n == 0) { return null; } else { return buildHelper(arr,0,n-1); } }

Take a look at the file GenericMethods.java.
There are three methods you must implement:
·public static <T extends
Comparable<T>> int findMin(T[] arr): Iterate through the
array to find the index of the smallest element in the array. If
there are two elements with the smallest value, the method should
return the index of the first one. The method should run in
O(n).
·public static <T extends
Comparable<T>> int findMinRecursive(T[] arr): Should
behave just like findMin, but should be implemented
recursively....

IN JAVA!!
You may be working with a programming language that has arrays,
but not nodes. In this case you will need to save your BST in a two
dimensional array. In this lab you will write a program to create a
BST modelled as a two-dimensional array. The output from your
program will be a two-dimensional array.
THEN: practice creating another array-based BST using integers
of your choice.
Once you have figured out your algorithm you will be able...

Finish the code wherever it says TODO
/**
* Node type for this list. Each node holds a maximum
of nodeSize elements in an
* array. Empty slots are null.
*/
private class Node {
/**
* Array of actual data
elements.
*/
// Unchecked warning
unavoidable.
public E[] data = (E[]) new
Comparable[nodeSize];
/**
* Link to next node.
...

In this lab, you will write a program that creates a binary
search tree based on user input. Then, the user will indicate what
order to print the values in. **Please write in C code**
Start with the bst.h and bst.c base code provided to you. You
will need to modify the source and header file to complete this
lab.
bst.h:
#ifndef BST_H
#define BST_H
typedef struct BSTNode
{
int value;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
BSTNode*...

Do a theta analysis and count the
number of computations it performed in each
function/method of the following code:
import java.io.*;
import java.util.Scanner;
class sort
{
int a[];
int n;
long endTime ;
long totalTime;
long startTime;
static BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
public sort(int nn) // Constructor
{
a = new int[nn];
n = nn;
endTime= 0;
totalTime =0;
startTime =0;
}
public static void main(String args[]) throws IOException
{
System.out.print("\nEnter number of students: ");
int nn =...

C++
***Please include makefile***
Requirements: You should name your Prority Queue class as PQ.
The queue must be able to hold unlimited number of integers. It has
two key operations: Push and Pop, which should have the time
complexity of O(logn). Files to turn in: You need to turn in four
files: makefile, main.C, PQ.C, PQ.h. You should have a main.C that
reads in or generates some integers, pushes them into the PQ one by
one, and pops and prints...

Create an add method for the BST (Binary Search Tree) class.
add(self, new_value: object) -> None:
"""This method adds new value to the tree, maintaining BST
property. Duplicates must be allowed and placed in the right
subtree."""
Example #1: tree = BST()
print(tree) tree.add(10)
tree.add(15)
tree.add(5)
print(tree)
tree.add(15)
tree.add(15)
print(tree)
tree.add(5)
print(tree)
Output:
TREE in order { }
TREE in order { 5, 10, 15 }
TREE in order { 5, 10, 15, 15, 15 }
TREE in order {...

This is the java code that I have, but i cannot get the output
that I want out of it. i want my output to print the full String
Form i stead of just the first letter, and and also print what
character is at the specific index instead of leaving it empty. and
at the end for Replaced String i want to print both string form one
and two with the replaced letters instead if just printing the
first...

Write a method that returns the sum of all the elements in a
specified column in a 3 x 4 matrix using the following header:
public static double sumColumn(double[][] m, int
columnIndex)
The program should be broken down into methods, menu-driven, and
check for proper input, etc.
The problem I'm having is I'm trying to get my menu to execute
the runProgram method. I'm not sure what should be in the
parentheses to direct choice "1" to the method. I'm...

This laboratory assignment involves implementing a data
structure called a map. A map associates objects called
keys with other objects called values. It is
implemented as a Java class that uses arrays internally.
1. Theory.
A map is a set of key-value pairs. Each key is
said to be associated with its corresponding value, so
there is at most one pair in the set with a given key. You can
perform the following operations on maps.
You can test if...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 8 minutes ago

asked 8 minutes ago

asked 24 minutes ago

asked 31 minutes ago

asked 32 minutes ago

asked 36 minutes ago

asked 37 minutes ago

asked 47 minutes ago

asked 55 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago