我正在编写一个 AVL 树类，我的教授已经对我们的代码进行了一些测试。除了三个之外，我已经通过了所有测试，而我没有通过的三个测试似乎表明，当元素被添加到树中或从树中删除时，树在必要时不会自我平衡。我一直在尝试调试它，但我似乎无法找到错误。有人可以指出我缺少什么吗？
编辑： 失败的测试： RemoveRoot - 删除 AVL 树的根并用它的继任者替换它。AddManySingle - 添加几个元素并强制单次旋转。AddManyDouble - 添加几个元素并强制双旋转。
private int count, height;
private AVLNode < E > root;
public AVLTree() {
root = null;
count = 0;
height = 0;
}
//the private inner Node class
private class AVLNode < E > {
private int height, bf;
private E data;
private AVLNode < E > left, right;
public AVLNode() {
data = null;
left = right = null;
bf = 0;
height = 0;
}
public AVLNode(E data) {
this.data = data;
left = right = null;
bf = 0;
height = 0;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public AVLNode < E > getLeft() {
return left;
}
public void setLeft(AVLNode < E > left) {
this.left = left;
}
public AVLNode < E > getRight() {
return right;
}
public void setRight(AVLNode < E > right) {
this.right = right;
}
public int getBF() {
return bf;
}
public void setBF() {
if (right == null && left == null) {
bf = 0;
} else if (right == null) {
bf = this.getLeft().getHeight();
} else if (left == null) {
bf = 0 - this.getRight().getHeight();
} else {
this.bf = this.getLeft().getHeight() - this.getRight().getHeight();
}
}
public void setBF(int theBalanceFactor) {
bf = theBalanceFactor;
}
/**
* The getHeight method computes the height of an AVL tree.
* @return The height of the AVL tree.
*/
public int getHeight() {
return this == null ? -1 : this.height;
}
public void setHeight() {
int leftHeight = (left == null) ? -1 : left.getHeight();
int rightHeight = (right == null) ? -1 : right.getHeight();
height = 1 + Math.max(leftHeight, rightHeight);
}
public void setHeight(int theHeight) {
height = theHeight;
}
}
//the private inner Iterator class
private class AVLIterator implements Iterator < E > {
private AVLNode < E > nextNode;
private Stack < AVLNode < E >> stack;
public AVLIterator() {
nextNode = root;
stack = new Stack < AVLNode < E >> ();
while (root != null) {
stack.push(root);
root = root.getLeft();
}
}
//Returns true if the iteration has more datas.
@Override
public boolean hasNext() {
return !stack.isEmpty();
}
//Returns the next data in the iteration.
@Override
public E next() {
if (!hasNext()) {
throw new NoSuchElementException("No next element.");
}
AVLNode < E > node = stack.pop();
E result = node.data;
if (node.right != null) {
node = node.right;
while (node != null) {
stack.push(node);
node = node.left;
}
}
return result;
}
//Removes the last data in the iteration.
@Override
public void remove() {
throw new UnsupportedOperationException("Invalid operation for support list.");
}
}
/**
* Rotate binary tree node that has a right child.
* Update heights, then return new root.
* n1 is the imbalanced node
*/
private AVLNode < E > rotateWithRightChild(AVLNode < E > n1) {
AVLNode < E > n2 = n1.right;
n1.right = n2.left;
n2.left = n1;
return n2;
}
/**
* Rotate binary tree node that has a left child.
* Update heights, then return new root.
*/
private AVLNode < E > rotateWithLeftChild(AVLNode < E > n2) {
AVLNode < E > n1 = n2.left;
n2.left = n1.right;
n1.right = n2;
return n1;
}
/**
* Double rotate binary tree node: first left child
* with its right child; then node n3 with new left child.
* Update heights, then return new root.
*/
private AVLNode < E > doubleWithLeftChild(AVLNode < E > n3) {
n3.left = rotateWithRightChild(n3.left);
return rotateWithLeftChild(n3);
}
/**
* Double rotate binary tree node: first right child
* with its left child; then node n1 with new right child.
* Update heights, then return new root.
*/
private AVLNode < E > doubleWithRightChild(AVLNode < E > n1) {
n1.right = rotateWithLeftChild(n1.right);
return rotateWithRightChild(n1);
}
//updates height and balance factor
private void updateHeightAndBF(AVLNode < E > node) {
int leftHeight, rightHeight, bf = 0, height = 0;
if (node != null) {
if (node.getLeft() == null) {
leftHeight = -1;
} else {
leftHeight = node.left.height;
}
if (node.getRight() == null) {
rightHeight = -1;
} else {
rightHeight = node.right.height;
}
/*if (leftHeight >= rightHeight) {
height = leftHeight + 1;
} else if (rightHeight >= leftHeight) {
height = rightHeight + 1;
}*/
height = Math.max(leftHeight, rightHeight) + 1;
bf = leftHeight - rightHeight;
node.setHeight(height);
node.setBF(bf);
} else {
height = -1;
}
}
/**
* private helper method.
* Balances a node by updating balance
* factor when a node is removed from
* or added to the AVL tree.
*
* @param node the node that is being balanced
*/
private AVLNode < E > balance(AVLNode < E > node) {
int hLeft, hRight;
if (node == null) {
return node;
}
if (node.bf == 2) {
if (node.left.bf == 1) {
node.left = rotateWithLeftChild(node);
} else if (node.left.bf == -1) {
node.left = doubleWithLeftChild(node);
}
} else if (node.bf == -2) {
if (node.right.bf < 0) {
node.right = rotateWithRightChild(node);
} else if (node.right.bf == -1) {
node.right = doubleWithRightChild(node);
}
}
return node;
}
/**
* Adds the item to the tree. Duplicate items and null items should not be added. O(log n)
*
* @param item the item to add
* @return true if item added, false if it was not
*/
@Override
public boolean add(E item) { // TODO
int theSize = size();
if (root == null && item != null) { //null check here for item
root = new AVLNode < E > (item);
count++;
return true;
} else if (item == null) {
return false;
} else {
add(root, item);
root = balance(root);
}
return (count != theSize);
}
/**
* private helper method for the add() method.
* Adds the item to the tree. Duplicate items and null items should not be added.
* Runs in O(log n) expected time, may be linear time in worst case
*
* @param value the item to add
* @return true if item added, false if it was not
*/
private boolean add(AVLNode < E > node, E value) { // TODO
if (value.equals(node.getData()) || value == null) {
//if it's a duplicate or null
return false;
}
if (value.compareTo(node.data) < 0) {
AVLNode < E > left = node.left;
if (left == null) {
node.left = new AVLNode < E > (value);
count++;
updateHeightAndBF(node);
balance(node);
return true;
} else updateHeightAndBF(node);
balance(node);
return add(left, value);
} else if (value.compareTo(node.data) > 0) {
AVLNode < E > right = node.right;
if (right == null) {
node.right = new AVLNode < E > (value);
count++;
updateHeightAndBF(node);
balance(node);
return true;
} else {
updateHeightAndBF(node);
balance(node);
return add(right, value);
}
}
return false;
}
/**
* returns the maximum data held in the tree. null if tree is empty.
* runs in O(log n) expected, may be linear in worst case
*
* @return maximum item or null if empty
*/
@Override
public E max() {
if (isEmpty()) {
return null;
}
return max(root).data;
}
/**
* a private helper method for the max() method.
*
* @return maximum Node or null if empty
*/
private AVLNode < E > max(AVLNode < E > x) {
if (x.getRight() == null) { //the rightmost node from the root
//is larger than the root, which is larger than the leftmost
//node from the root. so, if the rightmost node is null,
// that means the root node is the maximum data in the tree
return x;
} else {
return max(x.getRight());
}
}
/**
* returns the number of items in the tree O(1) with variable
*
* @return the number of items in the tree
*/
@Override
public int size() {
return count;
}
/**
* O(1)
* @return true if tree has no datas, false if tree has anything in it.
*/
@Override
public boolean isEmpty() {
return size() == 0;
}
/**
* runs in O(n) worst case, and O(log n) average case.
* @return the minimum data in the tree or null if empty
*/
@Override
public E min() {
if (isEmpty()) {
return null;
}
return min(root).data;
}
/**
* private helper method for the min() method
*
* @return the minimum Node in the tree or null if empty
*/
private AVLNode < E > min(AVLNode < E > y) {
if (y == null) {
return null;
} else if (y.left == null) { //the leftmost node from the root
//is smaller than the root, which is smaller than the rightmost
//node. so, if the leftmost node is null,
// that means the root node is the minimum data in the tree
return y;
} else {
return min(y.left);
}
}
/**
* Checks for the given item in the tree. O(log n)
*
* @param item the item to look for
* @return true if item is in tree, false otherwise
*/
@Override
public boolean contains(E item) {
return contains(root, item);
}
/**
* private helper method for the contains() methods
* Checks for the given item in the tree.
* runs in O(log n) expected, may be linear in worst case
*
* @param root the starting point
* @param item the item to look for
* @return true if item is in tree, false otherwise
*/
private boolean contains(AVLNode < E > root, E item) {
if (root == null || isEmpty()) {
return false;
}
if (item.compareTo(root.getData()) == 0) { //if item is
//equal to the data in the root Node, return true
return true;
} else {
if (item.compareTo(root.getData()) < 0) { //if item is less than data
AVLNode < E > left = root.getLeft(); //go to the left node
return (contains(left, item)); //call contains() method with the left node
} else if (item.compareTo(root.getData()) > 0) { //if item is more than data
AVLNode < E > right = root.getRight(); //go to the right node
return (contains(right, item)); //call contains() method with the right node
} else {
return true;
}
}
}
/**
* removes the given item from the tree O(log n). if the item is found
* and removed, balance the tree
*
* @param item the item to remove
* @return true if item removed, false if item not found
*/
@Override
public boolean remove(E item) {
int theSize = size();
root = remove(root, item);
return (count != theSize);
}
/**
* private helper method for the remove() method
* removes the given item from the tree
* runs in O(log n) expected, may be linear in worst case
* uses in-order successor
*
* @param node the starting point
* @param item the item to remove
* @return the node if the specified is node in the tree, null otherwise
*/
private AVLNode < E > remove(AVLNode < E > node, E item) { //TODO
if (node == null || item == null) {
return null;
}
if (root == null) {
return root;
}
if (item.compareTo(node.data) < 0) {
updateHeightAndBF(node);
balance(node);
node.left = remove(node.left, item);
} else if (item.compareTo(node.data) > 0) {
updateHeightAndBF(node);
balance(node);
node.right = remove(node.right, item);
} else if (node.left != null && node.right != null) { //two child nodes
AVLNode < E > succ = min(node.right);
node.data = succ.data;
updateHeightAndBF(node);
balance(node);
node.right = remove(node.right, node.data);
} else {
node = (node.left != null) ? node.left : node.right;
count--;
updateHeightAndBF(node);
return balance(node);
}
return node;
}
/**
* Runs in linear time, O(n)
* @return a list of the data in post-order traversal order
*/
@Override
public List < E > getPostOrder() {
List < E > postOrderList = new ArrayList < E > (size());
recPostOrder(root, postOrderList);
return postOrderList;
}
/**
* private helper method for the getPostOrder() method
* Runs in linear time, O(n)
*/
private void recPostOrder(AVLNode < E > theRoot, List < E > theList) {
if (theRoot != null) {
recPostOrder(theRoot.left, theList);
recPostOrder(theRoot.right, theList);
theList.add(theRoot.data);
}
}
/**
* Runs in linear time, O(n)
* @return a list of the data in pre-order traversal order
*/
@Override
public List < E > getPreOrder() {
List < E > preOrderList = new ArrayList < E > (size());
recPreOrder(root, preOrderList);
return preOrderList;
}
/**
* private helper method for the getPreOrder() method
* Runs in linear time, O(n)
*
*/
private void recPreOrder(AVLNode < E > theRoot, List < E > theList) {
if (theRoot != null) {
theList.add(theRoot.getData());
recPreOrder(theRoot.getLeft(), theList);
recPreOrder(theRoot.getRight(), theList);
}
}
/**
* Runs in linear time
* @return a list of the data in pre-order traversal order
*/
public List < E > getInOrder() {
List < E > inOrderList = new ArrayList < E > (size());
recInOrder(root, inOrderList);
return inOrderList;
}
/**
*
* private helper method for the getInOrder() method
* Runs in linear time
*
*/
private void recInOrder(AVLNode < E > theRoot, List < E > theList) {
if (theRoot != null) {
recInOrder(theRoot.left, theList);
theList.add(theRoot.data);
recInOrder(theRoot.right, theList);
}
}
/**
* Runs in linear time, O(n)
* @return a list of the data in level-order traversal order
*/
@Override
public List < E > getLevelOrder() {
List < E > data = new ArrayList < E > ();
Queue < AVLNode < E >> queue = new LinkedList < AVLNode < E >> ();
if (this.isEmpty()) {
return data;
} else {
queue.add(root);
}
while (!queue.isEmpty()) {
AVLNode < E > x = queue.remove();
if (x != null) {
data.add(x.getData());
if (x.getLeft() != null) {
queue.add(x.getLeft());
}
if (x.getRight() != null) {
queue.add(x.getRight());
}
}
}
return data;
}
/**
* O(1) [ignore garbage collection costs]
*
* Removes all the datas from this tree
*/
@Override
public void clear() {
root = null;
count = 0;
}
/**
* returns an iterator over this collection
* iterator is based on an in-order traversal
*/
@Override
public Iterator < E > iterator() {
return new AVLIterator();
}
}