我参考博客，自己写代码实现了AVL树，想验证一下写的是否是正确的，我采用了手动验证和自动化验证的方式，自动化验证就是，在一个死循环里一直调用AVL树的put，remove和find方法，但是会走到我设定的出错逻辑中（或者是出现栈溢出），但是不知道是哪里的问题，已经搞了一天了，这是哪里的问题呢？
出错截图如下：
代码如下，注释很全！
package com.victory.common.data_structure;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/**
* 平衡二叉树 AVL树的实现
*/
public class AVLTree<T extends Comparable<T>> {
/**
* 树的根节点
*/
private AVLNode<T> rootNode;
/**
* AVL树的结点个数
*/
private int size;
public int size() {
return size;
}
/**
* 添加元素到AVL树，不允许null 和重复元素
*
* @param value 待添加的元素
* @return 添加成功--true，否则--false
*/
public boolean put(T value) {
if (value == null) return false;
AVLNode<T> newRoot = put(this.rootNode, value);
if (newRoot == null) return false;
this.rootNode = newRoot;
return true;
}
/**
* 查找AVL树中是存在结点value
*
* @param value 待查找的结点
* @return 存在--true，不存在--false
*/
public boolean find(T value) {
if (value == null || this.rootNode == null) return false;
AVLNode<T> cur = this.rootNode;
while (cur != null) {
if (cur.data.compareTo(value) == 0) return true;
if (value.compareTo(cur.data) < 0) cur = cur.left;
else cur = cur.right;
}
return false;
}
/**
* 删除元素
*
* @param value 待删除的元素
* @return 删除成功--true，否则--false
*/
public boolean remove(T value) {
if (value == null || this.rootNode == null) return false;
RemoveResult<T> removeResult = remove(this.rootNode, value);
if (removeResult.success) this.rootNode = removeResult.retNode;
return removeResult.success;
}
/**
* 中序打印AVL树
*/
public void inOrder() {
inOrder(this.rootNode);
System.out.println();
}
private void inOrder(AVLNode<T> root) {
if (root != null) {
inOrder(root.left);
System.out.print(" " + root.data + " ");
inOrder(root.right);
}
}
/**
* 删除某棵AVL树上某个结点，因为删除可能会更换根结点，因此需要返回删除以后的根结点
*
* @param root 树根结点
* @param value 待删除的值
* @return 成功返回new RemoveResult<>(true,新的树根节点); 否则 new RemoveResult<>(false,null)
*/
private RemoveResult<T> remove(AVLNode<T> root, T value) {
//如果根为空，则直接返回删除失败
if (root == null) return new RemoveResult<T>(false);
//找到带删除的结点，删除逻辑和BST大致一样
if (root.data.compareTo(value) == 0) {
if (root.left == null || root.right == null) {
--size;
if (root.left == null) root = root.right;
else root = root.left;
} else {//当左右子树都不为空时，先从右子树找出最左的结点，作为新的根， 然后将其从右子树删除，
AVLNode<T> leftMostOfRight = mostLeft(root.right);
leftMostOfRight.left = root.left;
leftMostOfRight.right = remove(root.right, leftMostOfRight.data).retNode;
root = leftMostOfRight;
}
//如果当前结点不是要删除的，则根据大小关系，分别跳到左右子树 进行删除
} else if (value.compareTo(root.data) < 0) {
// System.out.println(value+" 小于 "+root.data+" 到左子树删除");
RemoveResult<T> removeLeft = remove(root.left, value);
if (!removeLeft.success) return removeLeft;
root.left = removeLeft.retNode;
} else {
//System.out.println(value+" 大于 "+root.data+" 到右子树删除");
RemoveResult<T> removeRight = remove(root.right, value);
if (!removeRight.success) return removeRight;
root.right = removeRight.retNode;
}
//最后需要调整高度和平衡性
updateHeight(root);
return new RemoveResult<>(true, adjustAVLTree(root));
}
/**
* 找到AVL树某个结点上最左的结点
*
* @param root 需要搜索到的树根节点
* @return root上最左的结点
*/
private AVLNode<T> mostLeft(AVLNode<T> root) {
if (root == null) return null;
AVLNode<T> cur = root;
for (; cur.left != null; cur = cur.left) ;
return cur;
}
/**
* 添加一个元素到AVL树，因为添加以后可能会改变树的根，所以返回添加后的新的根节点
*
* @param root AVL树根节点
* @param value 待添加的元素
* @return 添加后的根结点
*/
private AVLNode<T> put(AVLNode<T> root, T value) {
if (root == null) {
++this.size;
return new AVLNode<>(value);
}
// 如果找到某个元素和value相等，则不添加，返回
if (root.data.compareTo(value) == 0) return null;
if (value.compareTo(root.data) < 0) {//value小于根结点的值，则添加到左子树上，否则添加到右子树上
AVLNode<T> newLeft = put(root.left, value);
if (newLeft == null) return null;
root.left = newLeft;
} else {
AVLNode<T> newRight = put(root.right, value);
if (newRight == null) return null;
root.right = newRight;
}
//更新高度
updateHeight(root);
//调整AVL树
return adjustAVLTree(root);
}
/**
* 获取某个结点的高度
*
* @param node 需要获取其高度的结点
* @return AVL树某个结点的高度
*/
private int height(AVLNode<T> node) {
//如果树为空，则返回0，否则返回其height字段的值
return node == null ? 0 : node.height;
}
/**
* 更新某个AVL树结点的高度
*
* @param node 需要更新高度的AVL树结点
*/
private void updateHeight(AVLNode<T> node) {
//某个结点的高度是其左子树和右子树的高度的最大值 +1
if (node != null) node.height = Math.max(height(node.left), height(node.right)) + 1;
}
/**
* 获取AVL树某个结点的平衡因子
* 平衡因子是左子树的高度减去右子树的高度
*
* @param node 需要获取其平衡因子的结点
* @return AVL树某个结点的平衡因子
*/
private int balanceFactor(AVLNode<T> node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
/**
* 对AVL树的某个结点进行右旋操作
* 右旋的逻辑是，node的左指针指向其左子树的右子树，其左子树的右指针指向node，返回node的左子树
*
* @param node 需要右旋的结点
* @return 右旋操作以后的根节点
*/
private AVLNode<T> rightRotate(AVLNode<T> node) {
AVLNode<T> left = node.left;
node.left = left.right;
left.right = node;
updateHeight(node);//先更新node的高度，然后才可以更新left的高度
updateHeight(left);
return left;
}
/**
* 对AVL树的某个结点进行左旋操作
* 左旋的逻辑是，node的右指针指向其右子树的左子树，其右子树的左指针指向node，返回node的右子树
*
* @param node 需要左旋的结点
* @return 左旋操作以后的根节点
*/
private AVLNode<T> leftRotate(AVLNode<T> node) {
AVLNode<T> right = node.right;
node.right = right.left;
right.left = node;
updateHeight(node);
updateHeight(right);
return right;
}
/**
* 调整AVL树，主要是根据平衡因子进行旋转操作
*
* @param root 待调整的根节点
* @return 调整之后的根节点
*/
private AVLNode<T> adjustAVLTree(AVLNode<T> root) {
if (root == null) return null;
//判断是否平衡，如果平衡，则直接返回根节点
int balanceFactor = balanceFactor(root);
if (Math.abs(balanceFactor) <= 1) return root;
//否则根据各种不平衡的情况，采取左旋和右旋进行调整
if (balanceFactor > 1) {//当平衡因子大于1时，需要右旋解决
// 如果根的左子树的平衡因子小于0 则说明根的左子树 右重左轻 需要先对其左旋
if (balanceFactor(root.left) < 0) root.left = leftRotate(root.left);
root = rightRotate(root);
} else {//当平衡因子小于-1时，需要左旋解决
// 如果根的左右树的平衡因子大于0 则说明根的右子树 左重右轻 需要先对其右旋
if (balanceFactor(root.right) > 0) root.right = rightRotate(root.right);
root = leftRotate(root);
}
return root;
}
private static class AVLNode<T extends Comparable<T>> {
T data;
AVLNode<T> left;
AVLNode<T> right;
int height;
public AVLNode(T data) {
this.data = data;
this.height = 1;
}
}
/**
* 删除结果类
*
* @param <T>
*/
private static class RemoveResult<T extends Comparable<T>> {
boolean success; //当前删除是否成功
AVLNode<T> retNode; // 删除成功后 返回的新的根结点
public RemoveResult(boolean success, AVLNode<T> retNode) {
this.success = success;
this.retNode = retNode;
}
public RemoveResult(boolean success) {
this(success, null);
}
}
public static void main(String[] args) {
automationTest();
}
/**
* 手动测试
*/
private static void artificialTest() {
AVLTree<Integer> integerAVLTree = new AVLTree<>();
Scanner sc = new Scanner(System.in);
String command = null;
int n;
while (true) {
command = sc.next();
if ("put".equals(command)) {
n = sc.nextInt();
if (integerAVLTree.put(n)) System.out.println(n + " 插入成功");
else System.out.println(n + " 插入失败");
}
if ("remove".equals(command)) {
n = sc.nextInt();
if (integerAVLTree.remove(n)) System.out.println(n + " 删除成功");
else System.out.println(n + " 删除失败");
}
if ("print".equals(command)) {
integerAVLTree.inOrder();
}
if ("find".equals(command)) {
n = sc.nextInt();
if (integerAVLTree.find(n)) System.out.println(n + " 存在当前树中");
else System.out.println(n + " 不存在当前树中");
}
if ("size".equals(command)) System.out.println("当前树的结点个数是：" + integerAVLTree.size());
if ("exit".equals(command)) break;
}
}
private static volatile boolean runFlag = true;
/**
* 自动测试
*/
private static void automationTest() {
new Thread(() -> {
//验证的逻辑是 设置一个set集合，每次生成一个随机数number，
// 1. 测试put方法 如果set集合已经包含number的时候，说明AVLTree已经添加过这个数了，再次添加会失败，校验添加是否失败
// 如果set集合不包含number，则认为AVLTree没有添加过这个数，测试添加是否成功
//2. 测试remove方法 如果set集合已经包含number的时候，说明AVLTree已经添加过这个数了，测试remove是否成功
// 如果set集合不包含number，则认为AVLTree没有添加过这个数，测试remove是否失败
//3. 测试find 如果set集合已经包含number的时候，说明AVLTree已经添加过这个数了，测试find是否成功
// 如果set集合不包含number，则认为AVLTree没有添加过这个数，测试find是否失败
Set<Integer> integerSet = new HashSet<>();
AVLTree<Integer> integerAVLTree = new AVLTree<>();
int cnt = 0;
int command, number;
while (runFlag) {
command = (int) (Math.random() * 4) + 1;
number = (int) (Math.random() * Integer.MAX_VALUE) + 1;
switch (command) {
case 1://put
if (integerAVLTree.size() < 10000) {
boolean put = integerAVLTree.put(number);
if (integerSet.contains(number)) {
if (put) {//如果set中已经有了，但还是添加成功了，这是不正确的
System.out.println("hash表中已经包含了：" + number + " 应该添加失败，但是添加成功了");
return;
}
} else {
if (!put) {
System.out.println("hash表中没有包含：" + number + " 应该添加成功，但是添加失败了");
return;
}
integerSet.add(number);
++cnt;
}
}
break;
case 2://remove
boolean remove = integerAVLTree.remove(number);
if (integerSet.contains(number)) {
if (!remove) {
System.out.println("hash表中已经包含了：" + number + " 应该删除成功，但是删除失败了");
return;
}
--cnt;
integerSet.remove(number);
} else {
if (remove) {
System.out.println("hash表中没有包含：" + number + " 应该删除失败，但是删除成功了");
return;
}
}
break;
case 3://find
if (integerSet.contains(number)) {
boolean b = integerAVLTree.find(number);
if (!b) {
System.out.println("hash表中已经包含了：" + number + " 应该查找成功，但是查找失败了");
return;
}
}
break;
case 4://size
if (integerAVLTree.size() != cnt) {
System.out.println("size应该是:" + cnt + "，但实际上它是" + integerAVLTree.size());
return;
}
break;
}
}
}).start();
Scanner scanner = new Scanner(System.in);
String next = scanner.next();
if ("exit".equals(next)) runFlag = false;
}
}
