|
l) {
return 0;
}
return height(node.left) - height(node.right);
}
// 右旋转操作
private Node rotateRight(Node y) {
Node x = y.left;
Node T2 = x.right;
// 执行旋转
x.right = y;
y.left = T2;
// 更新节点高度
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
// 左旋转操作
private Node rotateLeft(Node x) {
Node y = x.right;
Node T2 = y.left;
// 执行旋转
y.left = x;
x.right = T2;
// 更新节点高度
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
// 插入节点
public void insert(int val) {
root = insertNode(root, val);
}
private Node insertNode(Node node, int val) {
// 执行标准的BST插入
if (node == null) {
return new Node(val);
}
if (val < node.val) {
node.left = insertNode(node.left, val);
} else if (val > node.val) {
node.right = insertNode(node.right, val);
} else { // 如果值相等，不允许重复插入
return node;
}
// 更新节点的高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
// 计算平衡因子
int balance = balanceFactor(node);
// 进行平衡调整
// 左子树不平衡，右旋转
if (balance > 1 && val < node.left.val) {
return rotateRight(node);
}
// 右子树不平衡，左旋转
if (balance < -1 && val > node.right.val) {
return rotateLeft(node);
}
// 左子树不平衡，先左旋转后右旋转
if (balance > 1 && val > node.left.val) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
// 右子树不平衡，先右旋转后左旋转
if (balance < -1 && val < node.right.val) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
// 中序遍历
public void inorderTraversal() {
inorderHelper(root);
}
private void inorderHelper(Node node) {
if (node == null) {
return;
}
inorderHelper(node.left);
System.out.print(node.val + " ");
inorderHelper(node.right);
}
public static void main(String[] args) {
// 创建平衡二叉树对象
AVLTree avlTree = new AVLTree();
// 插入节点
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
avlTree.insert(40);
avlTree.insert(50);
avlTree.insert(25);
// 中序遍历并输出节点值
System.out.print("中序遍历结果：");
avlTree.inorderTraversal(); // 输出：10 20 25 30 40 50
}
}
|