package changsheng.datastructure;
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x (unimplemented)
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
/**
* Implements an AVL tree. Note that all "matching" is based on the compareTo
* method.
*/
public class AVLTree<E extends Comparable<? super E>> {
/**
* Construct the tree.
*/
public AVLTree() {
root = null;
}
/**
* Insert into the tree; duplicates are ignored.
*
* @param x
* the item to insert.
*/
public void insert(E x) {
root = insert(x, root);
}
/**
* Remove from the tree. Nothing is done if x is not found.
*
* @param x
* the item to remove.
*/
public void remove(E x) {
System.out.println("Sorry, remove unimplemented");
}
/**
* Find the smallest item in the tree.
*
* @return smallest item or null if empty.
*/
public E findMin() {
return elementAt(findMin(root));
}
/**
* Find the largest item in the tree.
*
* @return the largest item of null if empty.
*/
public E findMax() {
return elementAt(findMax(root));
}
/**
* Find an item in the tree.
*
* @param x
* the item to search for.
* @return the matching item or null if not found.
*/
public E find(E x) {
return elementAt(find(x, root));
}
/**
* Make the tree logically empty.
*/
public void makeEmpty() {
root = null;
}
/**
* Test if the tree is logically empty.
*
* @return true if empty, false otherwise.
*/
public boolean isEmpty() {
return root == null;
}
/**
* Print the tree contents in sorted order.
*/
public void printTree() {
if (isEmpty())
System.out.println("Empty tree");
else
printTree(root);
}
/**
* Internal method to get element field.
*
* @param t
* the node.
* @return the element field or null if t is null.
*/
private E elementAt(AVLNode<E> t) {
return t == null ? null : t.element;
}
/**
* Internal method to insert into a subtree.
*
* @param x
* the item to insert.
* @param t
* the node that roots the tree.
* @return the new root.
*/
private AVLNode<E> insert(E x, AVLNode<E> t) {
if (t == null)
t = new AVLNode<E>(x, null, null);
else if (x.compareTo(t.element) < 0) { // 插入到左子树
t.left = insert(x, t.left);
/* 插入完成后检测是否平衡 */
if (height(t.left) - height(t.right) == 2) {/*左右子树不平衡*/
if (x.compareTo(t.left.element) < 0)
t = rotateWithLeftChild(t);/*左左情况 -- 单旋转*/
else
t = doubleWithLeftChild(t);/*左右情况 -- 双旋转*/
}
} else if (x.compareTo(t.element) > 0) { // 插入到右子树
t.right = insert(x, t.right);
/* 插入完成后检测是否平衡 */
if (height(t.right) - height(t.left) == 2) {/*左右子树不平衡*/
if (x.compareTo(t.right.element) > 0)
t = rotateWithRightChild(t);/*右右情况 -- 单旋转*/
else
t = doubleWithRightChild(t);/*右左情况 -- 双旋转*/
}
} else
; // Duplicate; do nothing
t.height = max(height(t.left), height(t.right)) + 1;
return t;
}
/**
* 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 AVLNode<E> findMin(AVLNode<E> 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 AVLNode<E> findMax(AVLNode<E> t) {
if (t == null)
return t;
while (t.right != null)
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
*
* @param x
* is item to search for.
* @param t
* the node that roots the tree.
* @return node containing the matched item.
*/
private AVLNode<E> find(E x, AVLNode<E> t) {
while (t != null)
if (x.compareTo(t.element) < 0)
t = t.left;
else if (x.compareTo(t.element) > 0)
t = t.right;
else
return t; // Match
return null; // No match
}
/**
* Internal method to print a subtree in sorted order.
*
* @param t
* the node that roots the tree.
*/
private void printTree(AVLNode<E> t) {
if (t != null) {
printTree(t.left);
System.out.println(t.element);
printTree(t.right);
}
}
/**
* Return the height of node t, or -1, if null.
*/
private static <E extends Comparable<? super E>> int height(AVLNode<E> t) {
return t == null ? -1 : t.height;
}
/**
* Return maximum of lhs and rhs.
*/
private static int max(int lhs, int rhs) {
return lhs > rhs ? lhs : rhs;
}
/**
* Rotate binary tree node with left child. For AVL trees, this is a single
* rotation for case 1. Update heights, then return new root.
*/
private static <E extends Comparable<? super E>> AVLNode<E> rotateWithLeftChild(
AVLNode<E> k2) {
AVLNode<E> 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. For AVL trees, this is a single
* rotation for case 4. Update heights, then return new root.
*/
private static <E extends Comparable<? super E>> AVLNode<E> rotateWithRightChild(
AVLNode<E> k1) {
AVLNode<E> 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. For AVL trees, this is a double
* rotation for case 2. Update heights, then return new root.
*/
private static <E extends Comparable<? super E>> AVLNode<E> doubleWithLeftChild(
AVLNode<E> 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. For AVL trees, this is a double
* rotation for case 3. Update heights, then return new root.
*/
private static <E extends Comparable<? super E>> AVLNode<E> doubleWithRightChild(
AVLNode<E> k1) {
k1.right = rotateWithLeftChild(k1.right);
return rotateWithRightChild(k1);
}
/** The tree root. */
private AVLNode<E> root;
// Test program
@SuppressWarnings("unused")
public static void main(String[] args) {
AVLTree<Integer> t = new AVLTree<Integer>();
final int NUMS = 4000;
final int GAP = 37;
System.out.println("Checking... (no more output means success)");
for (int i = GAP; i != 0; i = (i + GAP) % NUMS)
t.insert(new Integer(i));
if (NUMS < 40)
t.printTree();
if (((Integer) (t.findMin())).intValue() != 1
|| ((Integer) (t.findMax())).intValue() != NUMS - 1)
System.out.println("FindMin or FindMax error!");
for (int i = 1; i < NUMS; i++)
if (((Integer) (t.find(new Integer(i)))).intValue() != i)
System.out.println("Find error1!");
}
}
package changsheng.datastructure;
// Basic node stored in AVL trees
// Note that this class is not accessible outside
// of package DataStructures
class AVLNode<E extends Comparable< ? super E>> {
// Constructors
AVLNode(E theElement) {
this(theElement, null, null);
}
AVLNode(E theElement, AVLNode<E> lt, AVLNode<E> rt) {
element = theElement;
left = lt;
right = rt;
height = 0;
}
// Friendly data; accessible by other package routines
E element; // The data in the node
AVLNode<E> left; // Left child
AVLNode<E> right; // Right child
int height; // Height
}
