概念
是特殊的BST二叉排序树
左右两个子树的高度差绝对值不超过1
当root.rightHeight() - root.leftHeight() > 1,左旋
左旋步骤
-
创建一个新节点，值为root.value,新节点的左节点为root.left
Node newNode = new Node(root.value); newNode.left = root.left -
新节点的右节点为root的右子树的左节点
newNode.right = root.right.left -
把root的值换成右子节点
root.value = root.right.value -
root的右子节点换成右子节点的右子节点
root.right = root.right.right -
root的左子树设置成新节点
root.left = newNode;
以[4,3,6,5,7,8]演示左旋，当插入8时，高度差大于1，左旋
平衡二叉树图解.png
当root.leftHeight() - root.rightHeight() > 1,右旋
左旋步骤
-
创建一个新节点，值为root.value,新节点的右节点为root.right
Node newNode = new Node(root.value); newNode.right = root.right; -
新节点的左节点为root的左子树的右节点
newNode.left = root.left.right; -
把root的值换成左子节点
root.value = root.left.value -
root的左子节点换成左子节点的左子节点
root.left = root.left.left -
root的右子树设置成新节点
root.right = newNode;
右旋同左旋，不画图了
双旋
当满足右旋时
如果（root的左子树）的右子树高度大于（root的左子树）的左子树高度，
- 先对root的左子树进行左旋操作。
- 针对root右旋
当满足左旋时 同上
如果（root的右子树）的左子树高度大于（root的右子树）的右子树高度，
- 先对root的右子树进行右旋操作。
-
对root左旋
双旋.png
添加节点代码（主要是rebalance）
public class AVLTree {
public static void main(String[] args) {
// int[] arr = {4, 3, 6, 5, 7, 8};
// int[] arr = {10, 12, 8,9,7,6};
int[] arr = {10, 11, 7, 6, 8, 9};
Tree tree = new Tree();
for (int i = 0; i < arr.length; i++) {
tree.add(new Node(arr[i]));
}
tree.infixOrder();
System.out.println(tree.root.height());
System.out.println(tree.root.leftHeight());
System.out.println(tree.root.rightHeight());
}
}
class Tree {
Node root;
void add(Node node) {
if (root == null) {
root = node;
} else {
root.add(node);
}
}
public void infixOrder() {
if (root != null) {
root.infixOrder();
}
}
}
class Node {
int value;
Node left;
Node right;
Node parent;
public Node(int value) {
this.value = value;
}
int leftHeight() {
if (left == null) {
return 0;
} else {
return left.height();
}
}
int rightHeight() {
if (right == null) {
return 0;
} else {
return right.height();
}
}
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
void leftRotate() {
// 1. 创建一个新节点，值为root.value,新节点的左节点为root.left
Node newNode = new Node(value);
newNode.left = left;
// 2. 新节点的右节点为root的右子树的左节点
newNode.right = right.left; // 不用判空，最多是null
// 3. 把root的值换成右子节点
value = right.value;
// 4. root的右子节点换成右子节点的右子节点
right = right.right;
// 5. root的左子树设置成新节点
left = newNode;
}
void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right; // 不用判空，最多是null
value = left.value;
left = left.left;
right = newNode;
}
void add(Node node) {
if (node == null) {
return;
}
if (node.value < this.value) {
if (this.left == null) {
this.left = node;
this.left.parent = this;
} else {
this.left.add(node);
}
} else {
if (this.right == null) {
this.right = node;
this.right.parent = this;
} else {
this.right.add(node);
}
}
// 当添加完一个节点后，如果右子树-左子树高度 > 1 左旋
if (rightHeight() - leftHeight() > 1) {
// 如果（当前节点的右子树）的左子树高度大于（当前节点的右子树）的右子树高度，则先对当前节点的右子树进行右旋操作。
if(right!= null && right.leftHeight() > right.rightHeight()) {
right.rightRotate();
}
leftRotate();
return;
}
if (leftHeight() - rightHeight() > 1) {
// 如果（当前节点的左子树）的右子树高度大于（当前节点的左子树）的左子树高度，则先对当前节点的左子树进行左旋操作。
if (left != null && left.rightHeight() > left.leftHeight()) {
left.leftRotate();
}
rightRotate();
}
}
void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this.value);
if (this.right != null) {
this.right.infixOrder();
}
}
}
