this is java language

can you please answer as soon as possible

In this assignment, you will use a tree-based data structure to represent set partitions. A set partition will be represented by a collection of trees. Each tree will represent one subset, and will have one node for each element of that subset.

1.1

Setting up - Create a class called SetPartition. It should have: an inner class called Node, as described above; an array of Node objects, one for each element of the set; a constructor SetPartition (int numElements). The constructor should set up the array and the Nodes to represent the partition of the set {0, 1, . . . , numElements 1} where the subsets are {0}, {1}, . . . , and {numElements 1}.

1.2

Finding roots - Add a method public int getRoot (int x) to your class, which returns the value at the root of the tree containing x. (Note that, until youve written merge(), below, the result of getRoot() wont be very interesting, as each value will be in a subset containing only itself.)

1.3

In the same subset? - Add a method public boolean inSameSubset (int x, int y) that determines whether x and y are in the same subset of the partition.

1.4

Merging subsets - Add a method public void merge (int x, int y) to your class. It should merge the subsets containing x and y into a single subset. If x and y are in the same subset already, there is nothing to do. If they are in different subsets, it should merge their trees by making xs root be the parent of ys root. Note that you dont need to change the array; just the nodes. For example, merge (4,2) should turn the first partition below ({0, 1, 3, 4} and {2, 5}) into the second one ({0, 1, 2, 3, 4, 5}). merge (5,1) should turn the first partition into the third (another representation of {0, 1, 2, 3, 4, 5}).

1.5

Depth - Write a method public int depth (int x) which returns the depth of xs node in its tree (giving each root depth zero). Write a method public int maxDepth () which returns the greatest depth of any node.

1.6

Testing the code - Write a main method that does the following. 1. Creates a SetPartition with 1 000 elements, calls merge(0,1), merge(1,2), . . . , merge(998,999) and reports the maximum node depth of the tree. 2. Creates a SetPartition with 1 000 elements, calls merge(998,999), merge(997,998), . . . , merge(0,1) and reports the maximum node depth of the tree. 3. Creates 1 000 SetPartitions each with 1 000 elements, makes 750 random merges on each one and reports the average maximum node depth of these trees. (The answer should be about 6163.)

1.7 -

Above, we remarked that the big benefit of using trees is that the data structure is very efficient if we can keep the tree shallow. In this part, we will improve our set partition data structure by making the trees shallower. To do this, make a subclass ImprovedSetPartition of SetPartition. Override the getRoot method so that, as it navigates up a tree, it does the following to each node it visits. If the nodes grandparent (i.e., its parents parent) is not null, make the nodes grandparent be its new parent. Repeat the tests from the previous part on your new subclass. You may find that the results of the first two tests dont change, but the average maximum depth of the random merges should be much lower. (In my case, it dropped by a factor of about ten, but dont worry if you get different results: the answer will depend on how you wrote the code for merge and how you interpreted the instructions in this part.)