Skip to content

Instantly share code, notes, and snippets.

@chris373

chris373/avlTree.java

Last active August 19, 2016 14:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save chris373/6e1e07d3947b2791dff4 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save chris373/6e1e07d3947b2791dff4 to your computer and use it in GitHub Desktop.
Download ZIP
AVL Tree
Raw
avlTree.java
/* ------------- needed modifications : -----------------------
* store the the balance factor at each node
* must be entirely independan
* do the function parameters make sense ?
* improve readability
*/
import java.util.*;
import java.io.*;
class node {
String name;
String number;
node left;
node right;
int leftBal;
int rightBal;
node(String na, String num) {
name = na;
number = num;
left = null;
right = null;
}
}
class tree {
node root;
// a node used for searching
node searchParent;
// dummy constructor
tree() {}
tree(node rt) {
root = rt;
}
// fromFile specifies if the user is typing in a new entry
// or the method was called while building the tree from a file.
void insert(node newNode, boolean fromFile) {
node curNode = root;
// the list is empty
if(curNode == null)
root = newNode;
// try to find where to put the new entry
while(curNode != null) {
// already in the list ?
if(newNode.name.compareTo(curNode.name) == 0) {
// if the user entered it in, tell them the person
// was already in the list
if(fromFile == false)
System.out.print("That person is already in the list");
// break out of the function
return;
}
// goes to left of the current ?
else if(newNode.name.compareTo(curNode.name) < 0) {
// if the position is empty, put it ther
if(curNode.left == null) {
curNode.left = newNode;
return;
}
// otherwise keep going left
else
curNode = curNode.left;
}
else if(newNode.name.compareTo(curNode.name) > 0) {
if(curNode.right == null) {
curNode.right = newNode;
return;
}
else
curNode = curNode.right;
}
}
}
// call balance, passing the root twice for intial values
public void balance() { balance(root, root); }
// recieves the root node of the subtree, and parent of that root
public void balance(node rt, node rtParent) {
// recursively call to balance all of the subtrees starting from the bottom
if (rt.left == null && rt.right == null) {
return;
}
// left kid ?
if (rt.left != null) {
balance(rt.left, rt);
}
if (rt.right != null) {
balance(rt.right, rt);
}
// save the heights of the left and right subtrees
int rightSubHeight = Height(rt.right);
int leftSubHeight = Height(rt.left);
// test if the subtree is balances
if (Math.abs(leftSubHeight - rightSubHeight) > 1) {
// is it a right heavy tree ?
if (rightSubHeight > leftSubHeight) {
// is the right sub tree left heavy ? Left of right case
if (Height(rt.right.left) > Height(rt.right.right)) {
RightRotation(rt.right, rt);
LeftRotation(rt, rtParent);
}
// otherwise it's a right of right case
else
LeftRotation(rt, rtParent);
}
// is it a left heavy tree ?
else if (leftSubHeight > rightSubHeight) {
// is the left sub tree right heavy ? Right of left case
if (Height(rt.left.right) > Height(rt.left.left)) {
LeftRotation(rt.left, rt);
RightRotation(rt, rtParent);
}
// otherwise it's a left of left case
else
RightRotation(rt, rtParent);
}
}
}
// rt is the root of the subtree
// rtParent is the parent node of the subtree
// newroot is the node that will become the root of the subtree
void RightRotation(node rt, node rtParent) {
node newRoot = rt.left;
rt.left = newRoot.right;
newRoot.right = rt;
//if rt has a parent node
if(rt != root) {
// make the newRoot the root of the subtree by connecting the parent to it
// test if the newRoot is to the left, or right of it's parent
if(newRoot.name.compareTo(rtParent.name) < 0)
rtParent.left = newRoot;
else
rtParent.right = newRoot;
}
// otherwise newRoot becomes the root of the tree
else
root = newRoot;
}
void LeftRotation(node rt, node rtParent) {
node newRoot = rt.right;
rt.right = newRoot.left;
newRoot.left = rt;
// if rt has a parent node
if(rt != root) {
// make the newRoot the root of the subtree by connecting the parent to it
// test if the newRoot is to the left, or right of the it's parent
if(newRoot.name.compareTo(rtParent.name) < 0)
rtParent.left = newRoot;
else
rtParent.right = newRoot;
}
// otherwise newRoot becomes the root of the tree
else
root = newRoot;
}
int Height(node root) {
if (root == null) {
return 0;
}
int hl = Height(root.left) + 1;
int hr = Height(root.right) + 1;
if (hl > hr) {
return hl;
}
return hr;
}
// call search passing the initial values
node search(String key) { return search(key, root, root); }
node search(String key, node rt, node rtParent) {
// rt is null ?
if(rt == null) {
// the node was not found, return null
System.out.println("the entry was not found");
return null;
}
// found the key ?
else if(key.compareTo(rt.name) == 0){
// save the parent of the node in "searchParent"
searchParent = rtParent;
return rt;
}
// go to the left ?
else if(key.compareTo(rt.name) < 0)
return search(key, rt.left, rt);
else if(key.compareTo(rt.name) > 0)
return search(key, rt.right, rt);
else
return null;
}
// returns true if the node was sucessfully deleted
boolean delete(String key) {
node delNode = search(key);
// is the node in the list ?
if(delNode != null) {
// is the curernt node to the right of the parent ?
// save if it's to the left in a boolean
boolean isLeft = false;
if(delNode.name.compareTo(searchParent.name) < 0)
isLeft = true;
// is the node to be deleted a leaf node ?
if(delNode.left == null && delNode.right == null) {
// reset the parents child pointer to null
if(isLeft)
searchParent.left = null;
else
searchParent.right = null;
// sucessfully deleted the node, return true
return true;
}
// does the node only have one left kid ?
else if(delNode.left != null && delNode.right == null) {
// reset the parents child pointer
// to the child pointer of the node to be deleted
if(isLeft)
searchParent.left = delNode.left;
else
searchParent.right = delNode.left;
// sucessfully deleted the node, return true
return true;
}
// does the node only have one right kid ?
else if(delNode.right != null && delNode.left == null) {
// reset the parents child pointer
// to the child pointer of the node to be deleted
if(isLeft)
searchParent.left = delNode.right;
else
searchParent.right = delNode.right;
// sucessfully deleted the node, return true
return true;
}
// does it have 2 kids ?
else if (delNode.right != null && delNode.left != null) {
// change delNode's name and number
// to that of the least node in the right subtree
node searchNode = delNode.right;
searchParent = delNode;
// search for the least node in the right subtree
while(searchNode.left != null) {
searchNode = searchNode.left;
searchParent = searchNode;
}
// move the the values into the node being deleted
String newName = searchNode.name;
String newNumber = searchNode.number;
// delete the least node in the right subtree
delete(searchNode.name);
// change the values in the node that was deleted
delNode.name = newName;
delNode.number = newNumber;
// sucessfully deleted the node, return true
return true;
}
}
// node was not found, return false
return false;
}
// print the tree in bill-of-materials format
// pass the printTree function the initial values
void printTree() { printTree(root, root, "", 1); }
void printTree(node root, node rootParent, String indent, int level) {
if (root == null) {
if(rootParent.left != null || rootParent.right != null)
System.out.println(indent + level + ". " + '-');
return;
}
System.out.println(indent + level + ". " + root.name + '(' + root.number + ')');
printTree(root.left, root, indent + " ", level +1);
printTree(root.right, root, indent + " ", level +1);
}
// print the phone book in alphabetical order. (using in-order traversal)
void printBook() { printBook(root); }
void printBook(node rt) {
if (rt == null)
return;
else if(rt.left != null)
printBook(rt.left);
System.out.println(rt.name + " : " + rt.number);
if(rt.right != null)
printBook(rt.right);
}
}
class main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// build and balance the tree
tree phoneBookTree = buildTree();
phoneBookTree.balance();
String option = "";
do {
System.out.println("1. insert a new entry ");
System.out.println("2. search the list ");
System.out.println("3. delete an entry ");
System.out.println("4. print the list ");
System.out.println("5. print the tree in bill-of-materials format ");
System.out.println("X. exit the program");
option = in.next();
switch(option.charAt(0)) {
case '1':
System.out.println();
System.out.println("enter the name : ");
String name = in.next();
System.out.println("enter their number : ");
String number = in.next();
System.out.println();
node newNode = new node(name, number);
// the false indicates the user typed in the entry
phoneBookTree.insert(newNode, false);
// balance the tree
phoneBookTree.balance();
break;
case '2':
System.out.println();
System.out.println("enter a name to search for");
String key = in.next();
node searchNode = phoneBookTree.search(key);
if(searchNode != null)
System.out.println(key + "'s number is : " + searchNode.name);
System.out.println();
break;
case '3':
System.out.println();
System.out.println("Enter the name of the person to delete from the list");
String delKey = in.next();
// if the node was successfully deleted
if(phoneBookTree.delete(delKey))
System.out.println("the node was deleted successfully");
// balance the tree
phoneBookTree.balance();
System.out.println();
break;
case '4':
System.out.println();
phoneBookTree.printBook();
System.out.println();
break;
case '5':
System.out.println();
phoneBookTree.printTree();
System.out.println();
break;
case 'x' : case 'X' :
break;
default:
System.out.println("not a valid option");
}
}while(option.charAt(0)!= 'x' && option.charAt(0)!= 'X');
}
static tree buildTree() {
Scanner in = new Scanner(System.in);
// ask the user for the name of the file to read from
// Where the names and numbers are in the "name(number)" format
System.out.println("enter a file to read from");
String source = in.next();
tree tree1 = new tree();
try {
BufferedReader br = new BufferedReader(new FileReader(source));
String curLine;
// read in the first line to create the root of the tree
if ((curLine = br.readLine()) != null) {
// find the '(' character that seperates the name and number
int parenPos = curLine.indexOf('(');
// create a node to become the root node, passing the first name and number
node rootNode = new node(
curLine.substring(0, parenPos), curLine.substring(parenPos + 1, curLine.indexOf(')')));
// create the tree passing the root node
tree1 = new tree(rootNode);
// read in the rest of the lines of the file
while ((curLine = br.readLine()) != null) {
parenPos = curLine.indexOf('(');
// create the new node passing a name and number
node newNode = new node(
curLine.substring(0, parenPos), curLine.substring(parenPos + 1, curLine.indexOf(')')));
tree1.insert(newNode, true);
}
// balance the tree
tree1.balance(tree1.root, tree1.root);
}
else
System.out.println("the file is blank");
}
catch (IOException ioe) {
System.out.println("file not find");
}
// return the tree
return tree1;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment