Could someone help me with these Computer Science questions, please? Thank you!
*Please modify my code, and provide your own code as each question requires. Feel free to include your own code and general concepts in order to solve these problems, even if they go beyond the minimal code provided, if that would help, thank you very much!
----
I apologize if I didn't phrase things properly or if the questions are long. I thought that, since all of the questions relate to similar concepts, it would be prudent if they were all presented together since some questions require similar procedures and results from previous questions in order to solve them properly.
----
Please show all work, and improve any provided details as much as necessary, and also describing the necessary steps, and the necessary code and syntax would be greatly appreciated as well.
I would appreciate any help with this homework very much and thank you for your time and consideration. I hope that you have a wonderful day!
****
6) Give a precise expression for the minimum number of nodes in an AVL tree of height h.
What is the minimum number of nodes in an AVL tree of height h?
****
package avl;
public class AVL_Tree {
private Node root;
public class Node {
int value;
int height;
Node left_child;
Node right_child;
Node(int value) {
this.value = value;
}
}
public AVL_Tree(int value){
this.root = new Node(value);
}
}
public void inorder(){
inorder_recursive(root);
}
private void inorder_recursive(Node root){
if (root != null){
inorder_recursive(root.left_child);
System.out.print(root.value + " ");
inorder_recursive(root.right_child);
}
}
private int get_height(Node node) {
if(node == null){
return -1;
}else{
return node.height;
}
}
private void updateHeight(Node node) {
node.height = 1 + Math.max(get_height(node.left_child),
get_height(node.right_child));
}
private int getBalance(Node node) {
if(node == null){
return 0;
}else{
return get_height(node.right_child) –
get_height(node.left_child);
}
}
private Node rightRotate(Node node) {
Node left = node.left_child;// 4 node
Node right = left.right_child;//null
left.right_child = node;//5 node
node.left_child = right;// still null
updateHeight(node);
updateHeight(left);
return left;
}
private Node leftRotate(Node node) {
Node right = node.right_child;
Node left = right.left_child;
right.left_child = node;
node.right_child = left;
updateHeight(node);
updateHeight(right);
return right;
}
private Node rebalance(Node node) {
updateHeight(node);
int balance = getBalance(node);
if (balance > 1) {
if (get_height(node.right_child.right_child) >
get_height(node.right_child.left_child)) {
node = leftRotate(node); // Right Right rotation
} else {
node.right_child = rightRotate(node.right_child);//Right Left rotation
node = leftRotate(node);
}
} else if (balance < -1) {
if (get_height(node.left_child.left_child) >
get_height(node.left_child.right_child)) {
node = rightRotate(node); //Left Left
} else {
node.left_child = leftRotate(node.left_child); //Left Right
node = rightRotate(node);
}
}
return node;
}
public void insert(int value) {
root = insert(root, value);
}
private Node insert(Node node, int value) {
if (node == null) {
return new Node(value);
} else if (node.value > value) {
node.left_child = insert(node.left_child, value);
} else if (node.value < value) {
node.right_child = insert(node.right_child, value);
} else {
System.out.println("Duplicate key " + value + " not
inserted");
}
return rebalance(node);
}