好吧，这个 java 代码可以帮助你，它扩展了 Michael Goodrich 的 BST：
要查看完整的数据结构，请转到此处
AVLTree.java（链接不再可用）
import java.util.Comparator;
/**
* AVLTree class - implements an AVL Tree by extending a binary
* search tree.
*
* @author Michael Goodrich, Roberto Tamassia, Eric Zamore
*/
//begin#fragment AVLTree
public class AVLTree extends BinarySearchTree implements Dictionary {
public AVLTree(Comparator c) { super(c); }
public AVLTree() { super(); }
/** Nested class for the nodes of an AVL tree. */
protected static class AVLNode extends BTNode {
protected int height; // we add a height field to a BTNode
AVLNode() {/* default constructor */}
/** Preferred constructor */
AVLNode(Object element, BTPosition parent,
BTPosition left, BTPosition right) {
super(element, parent, left, right);
height = 0;
if (left != null)
height = Math.max(height, 1 + ((AVLNode) left).getHeight());
if (right != null)
height = Math.max(height, 1 + ((AVLNode) right).getHeight());
} // we assume that the parent will revise its height if needed
public void setHeight(int h) { height = h; }
public int getHeight() { return height; }
}
/** Creates a new binary search tree node (overrides super's version). */
protected BTPosition createNode(Object element, BTPosition parent,
BTPosition left, BTPosition right) {
return new AVLNode(element,parent,left,right); // now use AVL nodes
}
/** Returns the height of a node (call back to an AVLNode). */
protected int height(Position p) {
return ((AVLNode) p).getHeight();
}
/** Sets the height of an internal node (call back to an AVLNode). */
protected void setHeight(Position p) { // called only if p is internal
((AVLNode) p).setHeight(1+Math.max(height(left(p)), height(right(p))));
}
/** Returns whether a node has balance factor between -1 and 1. */
protected boolean isBalanced(Position p) {
int bf = height(left(p)) - height(right(p));
return ((-1 <= bf) && (bf <= 1));
}
//end#fragment AVLTree
//begin#fragment AVLTree2
/** Returns a child of p with height no smaller than that of the other child */
//end#fragment AVLTree2
/**
* Return a child of p with height no smaller than that of the
* other child.
*/
//begin#fragment AVLTree2
protected Position tallerChild(Position p) {
if (height(left(p)) > height(right(p))) return left(p);
else if (height(left(p)) < height(right(p))) return right(p);
// equal height children - break tie using parent's type
if (isRoot(p)) return left(p);
if (p == left(parent(p))) return left(p);
else return right(p);
}
/**
* Rebalance method called by insert and remove. Traverses the path from
* zPos to the root. For each node encountered, we recompute its height
* and perform a trinode restructuring if it's unbalanced.
*/
protected void rebalance(Position zPos) {
if(isInternal(zPos))
setHeight(zPos);
while (!isRoot(zPos)) { // traverse up the tree towards the root
zPos = parent(zPos);
setHeight(zPos);
if (!isBalanced(zPos)) {
// perform a trinode restructuring at zPos's tallest grandchild
Position xPos = tallerChild(tallerChild(zPos));
zPos = restructure(xPos); // tri-node restructure (from parent class)
setHeight(left(zPos)); // recompute heights
setHeight(right(zPos));
setHeight(zPos);
}
}
}
// overridden methods of the dictionary ADT
//end#fragment AVLTree2
/**
* Inserts an item into the dictionary and returns the newly created
* entry.
*/
//begin#fragment AVLTree2
public Entry insert(Object k, Object v) throws InvalidKeyException {
Entry toReturn = super.insert(k, v); // calls our new createNode method
rebalance(actionPos); // rebalance up from the insertion position
return toReturn;
}
//end#fragment AVLTree2
/** Removes and returns an entry from the dictionary. */
//begin#fragment AVLTree2
public Entry remove(Entry ent) throws InvalidEntryException {
Entry toReturn = super.remove(ent);
if (toReturn != null) // we actually removed something
rebalance(actionPos); // rebalance up the tree
return toReturn;
}
} // end of AVLTree class
//end#fragment AVLTree2
BTNode.java
public class BTNode implements BTPosition {
private Object element; // element stored at this node
private BTPosition left, right, parent; // adjacent nodes
//end#fragment BTNode
/** Default constructor */
public BTNode() { }
//begin#fragment BTNode
/** Main constructor */
public BTNode(Object element, BTPosition parent,
BTPosition left, BTPosition right) {
setElement(element);
setParent(parent);
setLeft(left);
setRight(right);
}
public Object element() { return element; }
public void setElement(Object o) {
element=o;
}
public BTPosition getLeft() { return left; }
public void setLeft(BTPosition v) {
left=v;
}
public BTPosition getRight() { return right; }
public void setRight(BTPosition v) {
right=v;
}
public BTPosition getParent() { return parent; }
public void setParent(BTPosition v) {
parent=v;
}
}
BTPosition.java
public interface BTPosition extends Position { // inherits element()
public void setElement(Object o);
public BTPosition getLeft();
public void setLeft(BTPosition v);
public BTPosition getRight();
public void setRight(BTPosition v);
public BTPosition getParent();
public void setParent(BTPosition v);
}