Description
An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree.
The capabilities of a binary search tree are:
- Create an empty binary search tree.
- Create a binary search tree containing a single item.
- Add an item to the binary search tree.
- Remove an item from the binary search tree.
- Iterate over the items in the binary search tree in in-order sequence.
BinarySearchTree.java
package com.meritmix.blog.algo.tree;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* <h4>ADT BinarySearchTree</h4>
* <p>A <code>BinarySearchTree</code> is a binary tree where each node has a <code>Comparable</code> key
* (and an associated value) and satisfies the restriction that the key in any node is larger than the
* keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's
* right subtree.</p>
* <p>Note: This definition means duplicate items are <em>NOT</em> allowed in a binary search tree.</p>
* <p>The capabilities of a binary search tree are:</p>
* <ol>
* <li>Create an empty binary search tree.</li>
* <li>Create a binary search tree containing a single item.</li>
* <li>Add an item to the binary search tree.</li>
* <li>Remove an item from the binary search tree.</li>
* <li>Iterate over the items in the binary search tree in in-order sequence.</li>
* </ol>
*/
public interface BinarySearchTree<T extends Comparable<T>> {
/**
* Add an item to the tree.
*
* @param item the <code>Comparable</code> to be added.
* @throws DuplicateElementException if an item to be added is equivalent to one that is already in the tree.
*/
public void add(T item) throws DuplicateElementException;
// Precondition: The item must not exist in the tree.
// Postcondition: The item is inserted into the tree.
// Throws: DuplicateElementException if the item duplicates one already in the tree.
/**
* Obtain an iterator for the tree.
*
* @return An <code>Iterator<Comparable></code> that visits the items in the tree using an in-order traversal.
* @throws ConcurrentModificationException in the face of concurrent modification.
* @throws UnsupportedOperationException if the <code>remove()</code> method is used.
*/
public Iterator<T> iterator() throws ConcurrentModificationException,
UnsupportedOperationException;
// Precondition: None.
// Postcondition: An object that implements the Iterator ADT for the items (in-order sequence) in the tree is returned.
// Throws: None.
/**
* Remove an item from the tree.
*
* @param item the <code>Comparable</code> to be removed.
* @throws NoSuchElementException if the item does not exist in the tree.
*/
public void remove(T item) throws NoSuchElementException;
// Precondition: The item must exist in the tree.
// Postcondition: The item is removed from the tree.
// Throws: NoSuchElementException if the item does not exist in the tree.
}
BalancedBinaryTree.java
package com.meritmix.blog.algo.tree;
import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
/**
* <h4> BalancedBinaryTree</h4>
* <p>
* A <code>BalancedBinaryTree</code> implements the <code>BinarySearchTree</code> ADT. After each
* add or remove, this implementation re-balances the tree if necessary.
* </p>
* <p>The implementation of this class is Assignment 4 for COMP251 students.</p>
*/
public class BalancedBinaryTree<T extends Comparable<T>> implements BinarySearchTree<T> {
//--------------------------------------------------------------------------------------------------------------------
// Static definitions
//--------------------------------------------------------------------------------------------------------------------
// The number of spaces to indent per level of the tree (used by toString(Node, int)).
private static final int INDENT_PER_LEVEL = 25;
//--------------------------------------------------------------------------------------------------------------------
// Class instance definitions
//--------------------------------------------------------------------------------------------------------------------
private Node root; // The root of the binary search tree.
/**
* Create an empty <code>BinarySearchTree</code>.
*/
public BalancedBinaryTree() {
// TODO Default constructor stub.
}
/**
* Create a <code>BinarySearchTree</code> that consists of a single item.
*
* @param item the <code>Comparable</code> that is the single item in the tree.
*/
public BalancedBinaryTree(T item) {
root = add(item, root);
}
@Override
public void add(T item) throws DuplicateElementException {
root = add(item, root);
}
@Override
public Iterator<T> iterator() throws ConcurrentModificationException, UnsupportedOperationException {
return new MyIterator();
}
@Override
public void remove(T item) throws NoSuchElementException {
root = remove(item, root);
}
public Node remove(T x, Node t) {
if (t==null) {
throw new NoSuchElementException("Sorry but you're mistaken, " + t + " doesn't exist in this tree :)\n");
}
//System.out.println("Remove starts... " + t.item + " and " + x);
if (x.compareTo(t.item) < 0 ) {
t.left = remove(x,t.left);
int l = t.left != null ? t.left.height : 0;
if((t.right != null) && (t.right.height - l >= 2)) {
int rightHeight = t.right.right != null ? t.right.right.height : -1;
int leftHeight = t.right.left != null ? t.right.left.height : -1;
if(rightHeight >= leftHeight)
t = rotateWithLeftChild(t);
else
t = doubleWithRightChild(t);
}
}
else if (x.compareTo(t.item) > 0) {
t.right = remove(x,t.right);
int r = t.right != null ? t.right.height : -1;
if((t.left != null) && (t.left.height - r >= 2)) {
int leftHeight = t.left.left != null ? t.left.left.height : -1;
int rightHeight = t.left.right != null ? t.left.right.height : -1;
if(leftHeight >= rightHeight)
t = rotateWithRightChild(t);
else
t = doubleWithLeftChild(t);
}
}
/*
Here, we have ended up when we are node which shall be removed.
Check if there is a left-hand node, if so pick out the largest element out, and move down to the root.
*/
else if(t.left != null) {
t.item = findMax(t.left).item;
t.left = remove(t.item, t.left);
if((t.right != null) && (t.right.height - t.left.height >= 2)) {
int rightHeight = t.right.right != null ? t.right.right.height : -1;
int leftHeight = t.right.left != null ? t.right.left.height : -1;
if(rightHeight >= leftHeight)
t = rotateWithLeftChild(t);
else
t = doubleWithRightChild(t);
}
}
else
t = (t.left != null) ? t.left : t.right;
if(t != null) {
int leftHeight = t.left != null ? t.left.height : -1;
int rightHeight = t.right!= null ? t.right.height : -1;
t.height = Math.max(leftHeight,rightHeight) + 1;
}
return t;
} //End of remove...
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public T findMin( )
{
if( isEmpty( ) ) return null;
return findMin( root ).item;
}
/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public T findMax( )
{
if( isEmpty( ) ) return null;
return findMax( root ).item;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
private Node findMin(Node t)
{
if( t == null )
return t;
while( t.left != null )
t = t.left;
return t;
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private Node findMax(Node t )
{
if( t == null )
return t;
while( t.right != null )
t = t.right;
return t;
}
/**
* Create a string representation for a binary search tree.
*
* @return A <code>String</code> that, if printed, will be in the shape of a tree
* with the root node at the left; the right subtree entirely above the root and
* to its right; and, the left subtree entirely below the root and to its right.
* The balance factors for each node are shown in parentheses beside the node.
*/
public String toString() {
return toString(this.root, 0).toString();
}
/**
* Create a string representation for a subtree of a binary search tree.
*
* @param node The <code>Node</code> at the root of the subtree.
* @param level The depth (in the entire tree) for the root of this subtree.
* @return A diagram, as a <code>StringBuilder</code>, that represents this subtree.
*/
private StringBuilder toString(Node node, int depth) {
StringBuilder sb = new StringBuilder();
if (node == null) return sb;
// Simple check to avoid an infinite loop if the tree pointers are in error.
// Can be removed if you need to process a tree that has a height > 5.
if (depth > 5) {
return sb.append("Probable error. Tree height exceeds 5. Node.item = ").append(node.item);
}
// First, create a diagram for the right subtree.
sb.append(toString(node.right, depth + 1));
// Next, prepare the representation for the current node and indent it according to its depth (level).
int endingOffset = depth * INDENT_PER_LEVEL + sb.length();
while (sb.length() < endingOffset) sb.append(' ');
sb.append(node.item.toString()).append('(').append(node.getBalanceFactor()).append(")\n");
// Finally, create a diagram for the left subtree.
sb.append(toString(node.left, depth + 1));
return sb;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Make the tree logically empty */
public void clear()
{
root = null;
}
/* Function to get height of node */
private int height(Node t )
{
return t == null ? -1 : t.height;
}
/* Function to max of left/right node */
private int max(int lhs, int rhs)
{
return lhs > rhs ? lhs : rhs;
}
/* Function to insert data recursively */
private Node add(T x, Node t)
{
if (t == null)
t = new Node(x);
else if (x.compareTo(t.item) < 0)
{
t.left = add( x, t.left );
if (height( t.left ) - height( t.right ) == 2)
if (x.compareTo(t.left.item) < 0)
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
}
else if (x.compareTo(t.item) >0)
{
t.right = add( x, t.right );
if (height( t.right ) - height( t.left ) == 2)
if (x.compareTo(t.right.item) > 0)
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
}
else
throw new DuplicateElementException(); // Duplicate; throw exception
t.height = max( height( t.left ), height( t.right ) ) + 1;
return t;
}
/* Rotate binary tree node with left child */
private Node rotateWithLeftChild(Node k2)
{
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = max( height( k1.left ), k2.height ) + 1;
return k1;
}
/* Rotate binary tree node with right child */
private Node rotateWithRightChild(Node k1)
{
Node k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = max( height( k2.right ), k1.height ) + 1;
return k2;
}
/**
* Double rotate binary tree node: first left child
* with its right child; then node k3 with new left child */
private Node doubleWithLeftChild(Node k3)
{
k3.left = rotateWithRightChild( k3.left );
return rotateWithLeftChild( k3 );
}
/**
* Double rotate binary tree node: first right child
* with its left child; then node k1 with new right child */
private Node doubleWithRightChild(Node k1)
{
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}
/* Functions to count number of nodes */
public int countNodes()
{
return countNodes(root);
}
private int countNodes(Node r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.left);
l += countNodes(r.right);
return l;
}
}
//--------------------------------------------------------------------------------------------------------------------
// Inner-class definitions
//--------------------------------------------------------------------------------------------------------------------
/**
* Define the data structure for a node in a balanced binary search tree.
*/
private class Node {
public T item; // The data item.
public Node left; // The root of the left subtree.
public Node right; // The root of the right subtree.
public int height;
/**
* Determine the balance factor for this node.
*
* @return The difference between the height of the right subtree and the height
* of the left subtree.
*/
private int getBalanceFactor() {
return height;
}
/* Constructor */
public Node()
{
left = null;
right = null;
item = null;
height = 0;
}
/* Constructor */
public Node(T n)
{
left = null;
right = null;
item = n;
height = 0;
}
}
//----------------------------------------------------------------------------------
// Iterator
//-----------------------------------------------------------------------------
private class MyIterator implements Iterator<T>{
private List<T> items = new ArrayList<T>();
public MyIterator() {
inorder(root);
}
private void inorder(Node r)
{
if (r != null)
{
inorder(r.left);
items.add(r.item);
inorder(r.right);
}
}
@Override
public boolean hasNext() {
return !items.isEmpty();
}
@Override
public T next() {
return items.remove(0);
}
@Override
public void remove() {
}
}
}
DuplicateElementException.java
package com.meritmix.blog.algo.tree;
/**
* Defines the the condition of detecting a duplicate element in a collection.
*/
public class DuplicateElementException extends RuntimeException {
//--------------------------------------------------------------------------------------------------------------------
// Static definitions
//--------------------------------------------------------------------------------------------------------------------
/** Necessary for serialization. */
private static final long serialVersionUID = 1L;
}
Code Title
package com.meritmix.blog.algo.tree;
import java.util.Iterator;
/**
* <h4>COMP251_Assignment4_Driver</h4>
* The main driver program that performs several operations on a balanced binary search tree
* and prints the results.
* <p>NOTE: Before you run this program and pass in your results, make sure you have changed
* the assignment for <code>NAME from "Your Name" to your name.</p>
*
*/
public class TestBalancedBinaryTree {
//--------------------------------------------------------------------------------------------------------------------
// Static definitions
//--------------------------------------------------------------------------------------------------------------------
// Change this next line to your name.
private static final String NAME = "Your Name";
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
BinarySearchTree<String> tree = new BalancedBinaryTree<>();
System.out.println("COMP251 Assignment 4: " + NAME);
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
tree.add("Eve");
tree.add("Pam");
tree.add("Zoe");
tree.add("Cam");
tree.add("Lee");
tree.add("Joy");
System.out.println("\nBinary search tree after add: Eve Pam Zoe Cam Lee Joy");
System.out.print("\n" + tree.toString());
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
tree.add("Ivy");
tree.add("Abe");
tree.add("Fay");
System.out.println("\nBinary search tree after add: Ivy Abe Fay");
System.out.print("\n" + tree.toString());
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
System.out.println("\nIterator output\n");
for (Iterator<String> it = tree.iterator(); it.hasNext();) {
System.out.print(it.next() + " ");
}
System.out.println("\n\n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
tree.remove("Lee");
tree.remove("Cam");
tree.remove("Abe");
System.out.println("\nBinary search tree after remove: Lee Cam Abe");
System.out.print("\n" + tree.toString());
System.out.println("= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =");
}
}
No comments:
Post a Comment