Q4: Write a Java program that uses the AVL Tree properties to create and insert

Question

Q4: Write a Java program that uses the AVL Tree properties to create and insert 15 nodes at a created AVL tree. Each node contains an integer value as a key. Your tasks: 1- Create the AVL tree. 2- Insert the nodes. 3- Print and search for a given key inside the tree nodes. 4- Print the whole tree. 5- Delete a given node then maintain the AVL properties inside the tree. 6- Display the results after deletion. 7- Submit the code & printed copy along with the results and documentations. Note: Submit on papers a graphical representation of the tree.

Explanation / Answer

import java.util.Scanner;

public class AVL {

Node root;

class Node {

Node parent, l, r;
int height = 0;
int key;

public Node(int key, Node l, Node r, Node parent) {
this.key = key;
this.l = l;
this.r = r;
this.parent = parent;
}

public String toString() {
return "key = " + key + " height = " + height;
}
}

public void insert(Node toInsert, Node node) {
if (root == null) {
root = toInsert;
return;
}

if (toInsert.key < node.key) {
if (node.l != null) {
insert(toInsert, node.l);
return;
} else {
toInsert.parent = node;
node.l = toInsert;
}
} else if (toInsert.key >= node.key) {
if (node.r != null) {
insert(toInsert, node.r);
return;
} else {
toInsert.parent = node;
node.r = toInsert;
}
}
BalanceHeight(toInsert);
balance(toInsert);
}

public Node findNode(Node findNode, Node node) {
if (root == null) {
return null;
}

if (findNode.key < node.key) {
if (node.l != null) {
return findNode(findNode, node.l);
}
} else if (findNode.key > node.key) {
if (node.r != null) {
return findNode(findNode, node.r);
}
} else if (findNode.key == node.key) {
return node;
}
return null;
}

public boolean deleteNode(Node deleteNode, Node node) {
if (root == null) {
return false;
} else if (root.key == deleteNode.key) {
if (root.l == null && root.r == null) {
root = null;
} else if (root.l == null) {
root = root.r;
root.parent = null;
} else if (root.r == null) {
root = root.l;
root.parent = null;
} else {
Node min = root.r;
//min element has no l or r child.
if (min.l == null && min.r == null) {
root.key = min.key;
root.r = null;
BalanceHeight(root);
balance(root);
return true;
}
while (min.l != null) {
min = min.l;
}
root.key = min.key;
if (min.r != null) {
min.r.parent = min.parent;
}
if (min.parent != root) {
min.parent.l = min.r;
} else {
min.parent.r = min.r;
}
BalanceHeight(min.parent);
balance(min.parent);
}
return true;
} else {
Node locatedNode = findNode(deleteNode, root);
if (locatedNode != null) {
deleteHelper(locatedNode);
} else {
return false;
}
}
return true;
}

private void deleteHelper(Node locatedNode) {
boolean l = (locatedNode.parent.l == locatedNode);
if (locatedNode.r == null && locatedNode.l == null) {
if (l) {
locatedNode.parent.l = null;
} else {
locatedNode.parent.r = null;
}
} else if (locatedNode.l != null && locatedNode.r == null) {
locatedNode.l.parent = locatedNode.parent;
if (l) {
locatedNode.parent.l = locatedNode.l;
} else {
locatedNode.parent.r = locatedNode.l;
}
} else if (locatedNode.l == null && locatedNode.r != null) {
locatedNode.r.parent = locatedNode.parent;
if (l) {
locatedNode.parent.l = locatedNode.r;
} else {
locatedNode.parent.r = locatedNode.r;
}
} else if (locatedNode.l != null && locatedNode.r != null) {
Node min = locatedNode.r;
//min element has no l or r child.
if (min.l == null && min.r == null) {
locatedNode.key = min.key;
locatedNode.r = null;
return;
}
while (min.l != null) {
//Min element has l child.
min = min.l;
}
locatedNode.key = min.key;
if (min.r != null) {
min.r.parent = min.parent;
}
//Min element has no l child but has r child.
if (min.parent != locatedNode) {
min.parent.l = min.r;
} else {
min.parent.r = min.r;
}
BalanceHeight(min.parent);
balance(min.parent);
return;
}
BalanceHeight(locatedNode.parent);
balance(locatedNode.parent);
}

public void deleteTree() {
root = null;
}

public void printTree(Node node) {
if (node == null) {
return;
}
printTree(node.l);
System.out.print(node + " ");
printTree(node.r);
}

public void printMenu() {
Scanner scan = new Scanner(System.in);
while (true) {
System.out.println(" 1.- Insert items "
+ "2.- Delete items "
+ "3.- Find items "
+ "4.- Print tree "
+ "5.- Delete tree ");
int choice = scan.nextInt();

int item;
Node node;
switch (choice) {
case 1:
item = scan.nextInt();
while (item != -999) {
node = new Node(item, null, null, null);
insert(node, root);
item = scan.nextInt();
}
printTree(root);
break;
case 2:
item = scan.nextInt();
while (item != -999) {
node = new Node(item, null, null, null);
System.out.print(" Deleting item " + item);
if (deleteNode(node, root)) {
System.out.print(": deleted!");
} else {
System.out.print(": does not exist!");
}
item = scan.nextInt();
}
System.out.println();
printTree(root);
break;
case 3:
item = scan.nextInt();
while (item != -999) {
node = new Node(item, null, null, null);
System.out.println((findNode(node, root) != null) ? "found" : "not found");
item = scan.nextInt();
}
break;
case 4:
printTree(root);
break;
case 5:
deleteTree();
System.out.println("Tree deleted!");
break;
}
}
}
  

private void BalanceHeight(Node node) {
if (node == null) {
return;
}
int l = -1, r = -1;
if (node.l != null) {
l = node.l.height;
}
if (node.r != null) {
r = node.r.height;
}
node.height = Integer.max(l, r) + 1;
BalanceHeight(node.parent);
}

private int checkBalance(Node node){
int subl = -1, subr = -1;
if(node.r!=null)subr = node.r.height;
if(node.l!=null)subl = node.l.height;
int balance = subl-subr;
return balance;
}
  
private void balance(Node node) {
int balance = checkBalance(node);
if (balance < -1) {   
if(checkBalance(node.r)==1) rotateRight(node.r);
rotateLeft(node);
} else if (balance > 1) {
if(checkBalance(node.l)==-1) rotateLeft(node.l);
rotateRight(node);
}
if(node.parent!=null) balance(node.parent);
}

void rotateLeft(Node node) {
System.out.println("Need to rotate node " + node + " l!");
  
Node keepAlive = null;
if(node.l!=null) {keepAlive = node.l; System.out.println("Need to keep alive "+keepAlive.key) ; }
  
Node newNode = new Node(node.key, null, node.r.l, node);
node.l = newNode;
node.key = node.r.key;
if (node.r.l != null) node.r.l.parent = newNode;
if (node.r.r != null) node.r.r.parent = node;
  
node.r = node.r.r;
if(keepAlive!=null){ node.l.l = keepAlive; keepAlive.parent = node.l;}
BalanceHeight(newNode);
}

void rotateRight(Node node) {
System.out.println("Need to rotate node " + node + " r!");
  
Node keepAlive = null;
if(node.r!= null){ keepAlive = node.r; System.out.println("Need to keep alive "+keepAlive.key);}
  
Node newNode = new Node(node.key, node.l.r, null, node);
node.r = newNode;
node.key = node.l.key;
if (node.l.r != null) node.l.r.parent = newNode;
if (node.l.l != null) node.l.l.parent = node;
  
node.l = node.l.l;
if(keepAlive!=null){ node.r.r = keepAlive; keepAlive.parent = node.r;}
BalanceHeight(newNode);
}
  
public static void main(String[] args) {
AVL avl = new AVL();
avl.printMenu();
}
}

===========================

Output:

1.- Insert items
2.- Delete items
3.- Find items
4.- Print tree
5.- Delete tree

1
10
11
12
Need to rotate node key = 10 height = 2 l!
13
14
Need to rotate node key = 12 height = 2 l!
-999
key = 10 height = 0
key = 11 height = 2
key = 12 height = 0
key = 13 height = 1
key = 14 height = 0

1.- Insert items
2.- Delete items
3.- Find items
4.- Print tree
5.- Delete tree

2
10

Deleting item 10Need to rotate node key = 11 height = 2 l!
: deleted!

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.