Add a remove method to the AVL tree class. Use a graphical user interface that a
ID: 660671 • Letter: A
Question
Add a remove method to the AVL tree class. Use a graphical user interface that allows
a user to work interactively with the AVL tree, adding and removing items as desired.
Extend the AVL tree class presented by adding a method that takes a value, locates it in
the AVL tree, and displays its level. Do this by extending the list of commands supported by the
program to include commands of the form level value. For example, if the user types in
level 12
the program displays the level of a node containing 12. The program should display -1 if the user
types a value not in the tree. If there is more than one instance of the value in the tree, the program
displays the level of any one of them.
Explanation / Answer
import java.io.*;
import java.util.*;
class BNode {
String data;
BNode left,right,parent;
int hi;
public BNode(){
this(null,null,null,null,0);
}
public BNode(String e,BNode p,BNode l,BNode r,int h){
data=e;
left=l; right=r; parent=p;
hi=h;
}
}
class LinkedBST {
BNode root=new BNode();
BNode currentNode;
int size=0;
int level;
public LinkedBST(){
root.data=null; root.hi=0;
size=0;
level = 0;
}
public LinkedBST(String a){
root.data=a;
root.hi=1;
BNode Left=new BNode(); BNode Right=new BNode();
root.left=Left; root.right=Right;
Left.parent=root; Right.parent=root;
size++;
}
boolean IsExternal(BNode n){
return (n.left==null && n.right==null);
}
int SubTreeSize(BNode n){
if (IsExternal(n)) return 0;
else return 1+SubTreeSize(n.left)+SubTreeSize(n.right);
}
boolean op(String a,String b){
int x=a.compareTo(b) ;
if (x<0) return true;
else return false;
}
BNode search(String o){
currentNode=root;
level = 0;
while (!IsExternal(currentNode)){
if (o.compareTo(currentNode.data)==0) { System.out.println("Successfully Found The Desired Result"); return currentNode; }
else if (op(o,currentNode.data)) { currentNode=currentNode.left; }
else { currentNode=currentNode.right; }
level++;
}
if (currentNode.data!=o) { System.out.println("sorry!!! this is not here."); return null; }
else return currentNode;
}
int height(BNode x){ if (x==null) return 0; return x.hi; }
void updatehieght(BNode x) { if (x==null) return; else x.hi=Math.max(height(x.left),height(x.right))+1; }
int mod(int x){ if (x<0) return -1*x; else return 1*x; }
boolean Imbalance(BNode b){ if (mod(b.left.hi-b.right.hi)>=2) return true; else return false; }
BNode taller(BNode m){ return (height(m.right)<height(m.left))?m.left:m.right; }
void rotate(BNode z){
BNode y=taller(z);
BNode x=taller(y);
if (z.right==y && y.right==x) {
BNode temp=y.left;
if (z.parent==null){
root=y;
y.parent=null;
y.left=z;
z.parent=y;
z.right=temp;
temp.parent=z;
updatehieght(z);
updatehieght(x);
updatehieght(y);
}
else{
if (z.parent.right==z) z.parent.right=y;
else if (z.parent.left==z) z.parent.left=y;
y.parent=z.parent;
y.left=z;
z.parent=y;
z.right=temp;
temp.parent=z;
updatehieght(z);
updatehieght(x);
updatehieght(y);
updatehieght(y.parent);
}
}
else if (z.left==y && y.left==x) {
BNode temp=y.right;
if (z.parent==null){
root=y;
y.parent=null;
y.right=z;
z.parent=y;
z.left=temp;
temp.parent=z;
updatehieght(z);
updatehieght(x);
updatehieght(y);
}
else {
if (z.parent.right==z) z.parent.right=y;
else if(z.parent.left==z) z.parent.left=y;
y.parent=z.parent;
y.right=z;
z.parent=y;
z.left=temp;
temp.parent=z;
updatehieght(z);
updatehieght(x);
updatehieght(y);
updatehieght(y.parent);
}
}
else if (z.right==y && y.left==x){
BNode temp1=x.left;
BNode temp2=x.right;
if (z.parent==null){
root=x;
x.parent=null;
x.left=z;
z.parent=x;
x.right=y;
y.parent=x;
z.right=temp1;
temp1.parent=z;
y.left=temp2;
temp2.parent=y;
updatehieght(z);
updatehieght(y);
updatehieght(x);
}
else{
if (z.parent.right==z) z.parent.right=x;
else if (z.parent.left==z) z.parent.left=x;
x.parent=z.parent;
x.left=z;
z.parent=x;
x.right=y;
y.parent=x;
z.right=temp1;
temp1.parent=z;
y.left=temp2;
temp2.parent=y;
updatehieght(z);
updatehieght(y);
updatehieght(x);
updatehieght(x.parent);
}
}
else if (z.left==y && y.right==x){
BNode temp1=x.left;
BNode temp2=x.right;
if (z.parent==null){
root=x;
x.parent=null;
x.left=y;
y.parent=x;
x.right=z;
z.parent=x;
y.right=temp1;
temp1.parent=y;
z.left=temp2;
temp2.parent=z;
updatehieght(y);
updatehieght(z);
updatehieght(x);
}
else {
if (z.parent.left==z) z.parent.left=x;
else if (z.parent.right==z) z.parent.right=x;
x.parent=z.parent;
x.left=y;
y.parent=x;
x.right=z;
z.parent=x;
y.right=temp1;
temp1.parent=y;
z.left=temp2;
temp2.parent=z;
updatehieght(z);
updatehieght(y);
updatehieght(x);
updatehieght(x.parent);
}
}
}
void insert(String n){
BNode temp=new BNode();
temp=root;
while (!IsExternal(temp)){
if (op(n,temp.data)) temp=temp.left;
else temp=temp.right;
}
temp.data=n;
temp.hi=1;
BNode left=new BNode(); BNode right=new BNode();
temp.left=left; temp.right=right;
left.parent=temp; right.parent=temp;
size++;
BNode r=temp;
while (temp.parent!=null){
updatehieght(temp.parent);
temp=temp.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
void delete1(BNode b) {
BNode r=b.parent;
size--;
if (b.left.data==null && b.right.data==null) {
b.data=null;
b.left=null;
b.right=null;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
else if (!IsExternal(b.right) && b.left.data==null) {
b.right.parent=b.parent;
if (b.parent.right==b) b.parent.right=b.right;
else b.parent.left=b.right;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
else if (!IsExternal(b.left) && b.left.data==null) {
b.left.parent=b.parent;
if (b.parent.left==b) b.parent.left=b.left;
else b.parent.right=b.left;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
}
void delete(String m) {
if (search(m)==null) { System.out.println("fuck off"); }
else {
BNode b=search(m);
BNode r=b.parent;
size--;
if (b.left.data==null && b.right.data==null) {
b.data=null;
b.left=null;
b.right=null;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
else if (!IsExternal(b.right) && b.left.data==null) {
b.right.parent=b.parent;
if (b.parent.right==b) b.parent.right=b.right;
else b.parent.left=b.right;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
else if (!IsExternal(b.left) && b.left.data==null) {
b.left.parent=b.parent;
if (b.parent.left==b) b.parent.left=b.left;
else b.parent.right=b.left;
while (b.parent!=null) {
updatehieght(b.parent);
b=b.parent;
}
while (r!=null){
if (Imbalance(r)==true){
rotate(r);
break;
}
r=r.parent;
}
}
else {
size++;
BNode currentNode1=b.left;
while(!IsExternal(currentNode1)){
currentNode1=currentNode1.right;
}
String t=currentNode1.parent.data;
currentNode1.parent.data=b.data;
b.data=t;
delete1(currentNode1.parent);
}
System.out.println("Successfully Deleted the Desired Result");
}
}
void printtree(BNode n){
if (!IsExternal(n)){
printtree(n.left);
System.out.print("the element is "+n.data+"----");
System.out.println("its hieght is "+n.hi);
printtree(n.right);
}
}
}
class run{
public static void main(String[] args) throws IOException{
InputStreamReader sr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(sr);
System.out.println("select the root of the tree");
String r=br.readLine();
LinkedBST bt=new LinkedBST(r);
System.out.println("Enter the file name:");
String input=br.readLine();
try{
BufferedReader filereader=new BufferedReader(new FileReader(input));
String b=filereader.readLine();
while (b!=null){
bt.insert(b);
b=filereader.readLine();
}
filereader.close();
}catch(FileNotFoundException e){ System.out.println("there is no file");}
while(true){
InputStreamReader sr1=new InputStreamReader(System.in);
BufferedReader br1=new BufferedReader(sr1);
System.out.println("Select any key for the Operation to do:");
System.out.println("for inserting something : 0");
System.out.println("for searching something : 1");
System.out.println("for Delete something : 2");
System.out.println("for print the tree : 3");
System.out.println("To know the level of a Node : 4");
System.out.println("For Quit : 5");
int option=Integer.parseInt(br1.readLine());
if (option==0){
System.out.println("Select the name to be insert");
String option1=br1.readLine();
bt.insert(option1);
}
else if (option==1){
System.out.println("Select the name to be search:");
String option1=br1.readLine();
bt.search(option1);
}
else if (option==2){
System.out.println("Select the integer to be delete:");
String option1=br1.readLine();
bt.delete(option1);
}
else if (option==3) { bt.printtree(bt.root); System.out.println("The Current Size of the Tree is: "+bt.size); }
else if (option == 4){
System.out.print("Enter The name whose level to be found : ");
String option1=br1.readLine();
if (bt.search(option1) == null){
System.out.println(-1);
}
else{
System.out.println("Level is " + bt.level);
}
}
else break;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.