Reputation: 189
How do we operate on Binary Search Trees
--UPDATE TWO--
balanced BST method fixed and functioning as required. The problem was that the arraylist wasn't being passed in correctly to create a new "balanced" tree. Here's my code for others to benefit. Cheers to everyone for their help!
public void balanceBST(TreeNode <E> node) {
if (node == null)
System.out.println("There is no tree to balance");
java.util.ArrayList<E> bstToArray = new java.util.ArrayList<E>();
Iterator<E> treeToArray = iterator();
while(treeToArray.hasNext()){
bstToArray.add(treeToArray.next());
}
int low = 0;
int high = bstToArray.size();
clear();
balanceHelper(bstToArray, low, high);
}
/** Helper method for the balanceBST method*/
public void balanceHelper(java.util.ArrayList<E> b, int low, int high) {
if(low == high)
return;
int midpoint = (low+high)/2;
insert(b.get(midpoint));
balanceHelper(b, midpoint+1, high);
balanceHelper(b, low, midpoint);
}
--UPDATE ONE--
I have created a balance BST method, however, I can't debug why a new BST is not being created, especially given I am using the insert method (the idea is to iterate over the tree, populate an array and then create a new BST with the sorted array recursively using the midpoint so that the new tree is sorted). I'd appreciate any help debugging this. Here's my method:-
/** Balance BST */
public void balanceBST(TreeNode <E> node) {
if (node == null)
System.out.println("There is no tree to balance");
java.util.ArrayList<E> bstToArray = new java.util.ArrayList<E>();
Iterator<E> treeToArray = iterator();
while(treeToArray.hasNext()){
bstToArray.add(treeToArray.next());
}
//System.out.println(bstToArray);
int low = 0;
int high = bstToArray.size();
balanceHelper(bstToArray, low, high);
//System.out.println(bstToArray);
}
public void balanceHelper(java.util.ArrayList<E> b, int low, int high) {
if(low == high)
return;
int midpoint = (low+high)/2;
insert(b.get(midpoint));
balanceHelper(b, midpoint+1, high);
balanceHelper(b, low, midpoint);
}
I am a beginner data structures student taking an online course (basically teaching myself) and have a number of questions related to OOP, BST's.
I have a class BST shown below which is available in the Liang, Introduction to Java, Comprehensive Edition book. However, I am working to enhance it by adding a number of methods (treeHeight, no of nodes at a given level, balance binary search tree as well as a few more).
So I wrote these methods but I am a bit lost with the different objects as well as how to call these methods in my driver/test program. Here are my questions (and plz excuse me since they might be trivial to some):-
(1) Why do we pass a node and not a tree to these methods?
(2) When I create a tree in my driver program and I try to call the treeHeight method, I get an error message which tells me that am passing the wrong parameter (tree instead of node)....am aware of the error and understand why it's there but am a bit confused here since most examples I've seen online pass a node to the treeHeight method and by inserting elements in the BST, we do have nodes but how to we call such a method then? This is a lack of understanding on my behalf on OOP here.
(3) How do I push the contents of a binary tree into an array (sorted using the inorder method) especially given an iterator inner class as shown below or do I not use that inner class? I am trying to create a method which balances the tree by pushing out the contents of the tree into an array and then iterating over the array splitting it (recursively) in half and creating a balanced BST. Since the array is sorted and a BST has the left subtree with elements less than the root and the right subtree with elements greater than the root, am able to start at the middle of the array, select root and then recursively work my way through building a Balanced BST.
Here's a snippet of my test program code:
BST<Integer> b1 = new BST<Integer>();
b1.insert(1);
b1.insert(2);
b1.insert(3);
b1.insert(4);
// How do I call the treeHeight on BST?
// I tried b1.treeHeight() but....
// and I tried treeHeight(BST) but....
// am a bit lost
And here's the BST class with my methods (please note that some of the methods might not be correct and I am still working on them...am sure once I get the fundamentals out of the way I will have them figured out) :
import java.lang.Math;
public class BST<E extends Comparable<E>> {
protected TreeNode<E> root;
protected int size = 0;
/** Create a default binary tree */
public BST() {
}
/** Create a binary tree from an array of objects */
public BST(E[] objects) {
for (int i = 0; i < objects.length; i++)
insert(objects[i]);
}
/** Returns true if the element is in the tree */
public boolean search(E e) {
TreeNode<E> current = root; // Start from the root
while (current != null) {
if (e.compareTo(current.element) < 0) {
current = current.left;
} else if (e.compareTo(current.element) > 0) {
current = current.right;
} else
// element matches current.element
return true; // Element is found
}
return false;
}
/**
* Insert element o into the binary tree Return true if the element is
* inserted successfully
*/
public boolean insert(E e) {
if (root == null)
root = createNewNode(e); // Create a new root
else {
// Locate the parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null)
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else
return false; // Duplicate node not inserted
// Create the new node and attach it to the parent node
if (e.compareTo(parent.element) < 0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true; // Element inserted
}
protected TreeNode<E> createNewNode(E e) {
return new TreeNode<E>(e);
}
/** Inorder traversal from the root */
public void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
protected void inorder(TreeNode<E> root) {
if (root == null)
return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
/** Postorder traversal from the root */
public void postorder() {
postorder(root);
}
/** Postorder traversal from a subtree */
protected void postorder(TreeNode<E> root) {
if (root == null)
return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
/** Preorder traversal from the root */
public void preorder() {
preorder(root);
}
/** Preorder traversal from a subtree */
protected void preorder(TreeNode<E> root) {
if (root == null)
return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
/**
* This inner class is static, because it does not access any instance
* members defined in its outer class
*/
public static class TreeNode<E extends Comparable<E>> {
protected E element;
protected TreeNode<E> left;
protected TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
/** Get the number of nodes in the tree */
public int getSize() {
return size;
}
/** Returns the root of the tree */
public TreeNode<E> getRoot() {
return root;
}
/** Return tree height - my own method */
public int treeHeight(TreeNode <E> node) {
// height of empty tree = ZERO
if (node == null)
return 0;
int leftHeight = treeHeight(node.left);
int rightHeight = treeHeight(node.right);
if (leftHeight > rightHeight)
return leftHeight;
else
return rightHeight;
}
/** Return the no of nodes at given level - my own method */
public int numberOfNodesAtLevel(TreeNode <E> node, int level) {
if (root == null)
return 0;
if (level == 0)
return 1;
return numberOfNodesAtLevel(node.left, level-1) + numberOfNodesAtLevel(node.right, level-1);
}
/** Return the no of nodes in binary tree - my own method */
public int numberOfNodes(TreeNode <E> node) {
if (node == null)
return 0;
return 1 + numberOfNodes(node.left) + numberOfNodes(node.right);
}
/** Calculate ACE - my own method */
public double calculateACE(TreeNode <E> node) {
int n = numberOfNodes(node);
int treeHeight = treeHeight(node);
int sum = 0;
int level = 0;
for (level=0, sum=0; level < treeHeight; level++ ) {
sum += numberOfNodesAtLevel(node, level) * (level + 1);
}
double ACE = sum / n;
return ACE;
}
/** Calculate MinACE - my own method */
public double calculateMinACE(TreeNode <E> node) {
int n = numberOfNodes(node);
int treeHeight = (int) Math.floor((Math.log(n))+1);
int sum = 0;
int level = 0;
for (level=0, sum=0; level < treeHeight; level++ ) {
sum += numberOfNodesAtLevel(node, level) * (level + 1);
}
double ACE = sum / n;
return ACE;
}
/** Calculate MaxACE - my own method */
public double calculateMaxACE(TreeNode <E> node) {
int n = numberOfNodes(node);
int treeHeight = n;
int sum = 0;
int level = 0;
for (level=0, sum=0; level < treeHeight; level++ ) {
sum += numberOfNodesAtLevel(node, level) * (level + 1);
}
double ACE = sum / n;
return ACE;
}
/** Needs Balancing - my own method */
public boolean needsBalancing(TreeNode <E> node) {
double k = 1.25;
double AceValue = calculateACE(node);
double MinAceValue = calculateMinACE(node);
if(AceValue > (MinAceValue*k))
return true;
return false;
}
/** Balance BST - my own method, not complete yet */
public void balanceBST(TreeNode <E> node) {
int size = numberOfNodes(node);
}
/** Returns a path from the root leading to the specified element */
public java.util.ArrayList<TreeNode<E>> path(E e) {
java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<TreeNode<E>>();
TreeNode<E> current = root; // Start from the root
while (current != null) {
list.add(current); // Add the node to the list
if (e.compareTo(current.element) < 0) {
current = current.left;
} else if (e.compareTo(current.element) > 0) {
current = current.right;
} else
break;
}
return list; // Return an array of nodes
}
/**
* Delete an element from the binary tree. Return true if the element is
* deleted successfully Return false if the element is not in the tree
*/
public boolean delete(E e) {
// Locate the node to be deleted and also locate its parent node
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else
break; // Element is in the tree pointed at by current
}
if (current == null)
return false; // Element is not in the tree
// Case 1: current has no left children
if (current.left == null) {
// Connect the parent with the right child of the current node
if (parent == null) {
root = current.right;
} else {
if (e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
} else {
// Case 2: The current node has a left child
// Locate the rightmost node in the left subtree of
// the current node and also its parent
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right; // Keep going to the right
}
// Replace the element in current by the element in rightMost
current.element = rightMost.element;
// Eliminate rightmost node
if (parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
// Special case: parentOfRightMost == current
parentOfRightMost.left = rightMost.left;
}
size--;
return true; // Element inserted
}
/** Obtain an iterator. Use inorder. */
public java.util.Iterator<E> iterator() {
return new InorderIterator();
}
// Inner class InorderIterator
private class InorderIterator implements java.util.Iterator<E> {
// Store the elements in a list
private java.util.ArrayList<E> list = new java.util.ArrayList<E>();
private int current = 0; // Point to the current element in list
public InorderIterator() {
inorder(); // Traverse binary tree and store elements in list
}
/** Inorder traversal from the root */
private void inorder() {
inorder(root);
}
/** Inorder traversal from a subtree */
private void inorder(TreeNode<E> root) {
if (root == null)
return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
/** More elements for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
/** Get the current element and move to the next */
public E next() {
return list.get(current++);
}
/** Remove the current element */
public void remove() {
delete(list.get(current)); // Delete the current element
list.clear(); // Clear the list
inorder(); // Rebuild the list
}
}
/** Remove all elements from the tree */
public void clear() {
root = null;
size = 0;
}
}
Upvotes: 1
Views: 2183
Answers (1)
Reputation: 53565
(1) Why do we pass a node and not a tree to these methods?
Answer:
A BST is defined by its root, you can implement the methods to accept the root or the tree - it's an arbitrary decision.
(2) ...I've seen online pass a node to the treeHeight method and by inserting elements in the BST, we do have nodes but how to we call such a method then? This is a lack of understanding on my behalf on OOP here.
Answer:
In the example you gave you should call it like this:
BST<Integer> b1 = new BST<Integer>();
b1.insert(1);
b1.insert(2);
b1.insert(3);
b1.insert(4);
int h = b1.treeHeight(b1.getRoot()); // get the height
(3) How do I push the contents of a binary tree into an array.
Answer:
I didn't debug the following code, but I'm sure it'll give you a good idea of how it's done:
int arraySize = b1.getSize();
Integer[] treeToArray = new Integer[arraySize];
iterator iter = b1.iterator();
int i=0;
while(iter.hasNext()) {
treeToArray[i++] = (Integer)iter.next();
}
(4) why doesn't treeHeight() work (always returns zero) ?
Answer:
Because it has a bug, here's how to fix it:
/** Return tree height - my own method */
public int treeHeight(TreeNode <E> node) {
// height of empty tree = ZERO
if (node == null)
return 0;
int leftHeight = treeHeight(node.left);
int rightHeight = treeHeight(node.right);
if (leftHeight > rightHeight)
return leftHeight+1; // bug was here: you should return the height of the child + 1 (yourself)
else
return rightHeight+1; // and here
}
Upvotes: 1