构建二叉平衡树时怎么旋转（二叉平衡树AVLTree）
构建二叉平衡树时怎么旋转（二叉平衡树AVLTree）伪代码：(a)LL的旋转，步骤如下：AVL树插入的第一步其实跟二叉查找树一样，但是插入数据后，可能会导致树失去平衡，那么这时就需要对子树进行旋转了。通过选择来使得树继续保持平衡。树失去平衡会有四种情况：AVL树失去平衡之后，可以通过旋转使其恢复平衡。四种失去平衡的情况下对应的旋转方法分别如下：
前言在《一文彻底掌握二叉查找树，非史上最全总结（多图，附代码） 》我们讲了二叉查找树，在文章的最后我们也提到了，二叉查找树查找的效率受到树的深度的影响，最坏情况是O(N)。而二叉查找树的深度是根据数据插入的顺序不同而表现出不同的。那么有没有可能让树的深度尽可能低，从而提高我们查询的效率呢？答案就是今天要讲的平衡二叉树（AVL树）。
定义AVL树是二叉查找树的一个特例，所以上一篇文章说到的二叉查找树的定义是AVL树定义的前提。在这个前提之下，AVL树再提出了写更加严格的定义。那就是，树的任意节点的子树的高度差都小于等于1。
树的操作由于AVL树比普通的二叉查找树有个更加苛刻的要求，要求子树的高度差小于等于1。那么在树的插入、删除等操作时将会比普通的二叉查找树更加麻烦。
插入
AVL树插入的第一步其实跟二叉查找树一样，但是插入数据后，可能会导致树失去平衡，那么这时就需要对子树进行旋转了。通过选择来使得树继续保持平衡。
树失去平衡会有四种情况：
- 节点的左儿子的左子树插入节点，导致左子树比右子树高（LL），如下图树插入节点1之后，6的左子树高度比右子树高2。
- 节点的右儿子的右子树插入节点，导致右子树比左子树高（RR）
- 节点的左儿子的右子树插入节点，导致左子树比右子树高（LR）
- 节点的右儿子的左子树插入节点，导致左子树比右子树高（RL）
AVL树失去平衡之后，可以通过旋转使其恢复平衡。四种失去平衡的情况下对应的旋转方法分别如下：
(a)LL的旋转，步骤如下：
- 将根节点的左孩子作为新根节点。
- 将新根节点的右孩子作为原根节点的左孩子。
- 将原根节点作为新根节点的右孩子。
伪代码：
// 要旋转的节点为node，其父节点是parent
Node temp = node.left;
node.left = temp.right;
temp.right = node;
parent.left = temp;
LL 旋转示意图如下：
(b)RR的旋转，旋转方法与LL旋转对称，步骤如下：
- 将根节点的右孩子作为新根节点。
- 将新根节点的左孩子作为原根节点的右孩子。
- 将原根节点作为新根节点的左孩子。
RR旋转示意图如下：
（c)LR的旋转：
LR失去平衡的情况，单旋转不能解决问题，需要进行两次旋转，步骤如下：
- 根节点的左孩子做一次RR旋转。
- 根节点做一次LL旋转。
LR的旋转示意图如下：
(d)RL的旋转：
RL旋转方法与LR旋转对称，步骤如下：
- 根节点的右孩子做一次LL旋转。
- 根节点做一次RR旋转。
RL的旋转示意图如下：
删除
平衡二叉树的节点删除操作会比较复杂，我们可以这么分析，左子树上节点的删除相当于我们在右子树上插入了一个新节点，右子树上节点的删除相当于在左子树上插入了一个新节点。我们可以根据这一点进行判断并采取对应的平衡调整操作。
具体做法需要从当前节点判断树是否失去平衡，通过计算左右子树的高度差，判断是哪种失衡。然后运用旋转，将树调整为平衡树。
- 排序二叉树的删除
- 判断左右子树高度差是否小于2，判断结点是否失衡
- 当前结点失衡，将删除视为另一侧的插入，依照插入的旋转思想进行旋转
- 如此反复直至根节点
查询
由于AVL树本身就是一颗二叉查找树，所以其节点查询与普通的二叉树没什么两样，这里就不赘述了。如果有不清楚的同学，可以翻看我的上篇文章。
代码代码我在上篇文章的基础上进行修改，Node类上加入字段height标识子树的高度，比在insert、delete方法上加上判断结构和旋转
public class AVLTree {
private Node root;
public void insert(int value) {
root = insert(root value);
}
private Node insert(Node x int value) {
if (x == null) {// 首次插入
return new Node(value 1);
}
int xVal = x.value;
if (value < xVal) {
x.left = insert(x.left value);
if (getHeight(x.left) - getHeight(x.right) > 1) {// left
if (getHeight(x.left.left) > getHeight(x.left.right)) {// left
x = leftLeftRotation(x);
} else {
x = leftRightRotation(x);
}
}
} else if (value > xVal) {
x.right = insert(x.right value);
if (getHeight(x.right) - getHeight(x.left) > 1) {// right
if (getHeight(x.right.right) > getHeight(x.right.left)) {// right
x = rightRightRotation(x);
} else {
x = rightLeftRotation(x);
}
}
} else {
// 重复数据 do nothing
}
x.height = reCalcHeight(x);
return x;
}
public Node select(int value) {
return select(root value);// work when BST is empty
}
private Node select(Node x int value) {
if (x == null)
return null;
int xVal = x.value;
if (value < xVal)
return select(x.left value);
else if (value > xVal)
return select(x.right value);
else
return x;
}
public void delete(int value) {
root = delete(root value);
}
private Node delete(Node x int value) {
if (x == null) {
return null;
}
int xVal = x.value;
if (value < xVal)
x.left = delete(x.left value);// 左子树
else if (value > xVal)
x.right = delete(x.right value);// 右子树
else {
if (x.right == null) {
return x.left;
}
if (x.left == null) {
return x.right;
}
Node temp = x;// 要被删除的节点，先拿着
x = min(temp.right); // 获取右子树最小的节点
x.right = deleteMin(temp.right);// 删除右子树最小节点，并将删除后的树作为x的右子树
x.left = temp.left;// 原来的左子树保持，作为新根节点的左子树
}
// 删除完成，调整平衡性
x.height = reCalcHeight(x);
// 失衡
if (getHeight(x.left) - getHeight(x.right) >= 2) {
// 删除发生在右子树，模拟插入发生在左子树
if (getHeight(x.left.left) > getHeight(x.left.right)) {
// 插入发生在左子树，LL旋转
return leftLeftRotation(x);
} else {
// LR旋转
return leftRightRotation(x);
}
} else if (getHeight(x.left) - getHeight(x.right) <= -2) {
// 删除发生在左子树，模拟插入发生在右子树
if (getHeight(x.right.left) > getHeight(x.right.right)) {
// RL旋转
return rightLeftRotation(x);
} else {
// RR旋转
return rightRightRotation(x);
}
}
// 未失衡，不做操作
return x;
}
private Node min(Node x) {
if (x.left == null)
return x;
return min(x.left);
}
private Node deleteMin(Node x) {
if (x.left == null)
return x.right;
x.left = deleteMin(x.left);
return x;
}
private int getHeight(Node n) {
if (n == null) {
return 0;
}
return n.height;
}
private int reCalcHeight(Node x) {
return Math.max(getHeight(x.left) getHeight(x.right)) 1;
}
private Node leftLeftRotation(Node x) {// LL旋转
Node left = x.left;
x.left = left.right;
left.right = x;
x.height = reCalcHeight(x);// 挂了新的子节点，重新计算高度
left.height = reCalcHeight(left);// 挂了新的子节点，重新计算高度
return left;
}
private Node rightRightRotation(Node x) {// RR旋转
Node right = x.right;
x.right = right.left;
right.left = x;
x.height = reCalcHeight(x);// 挂了新的子节点，重新计算高度
right.height = reCalcHeight(right);// 挂了新的子节点，重新计算高度
return right;
}
private Node leftRightRotation(Node x) {// LR旋转，先将左儿子RR旋转，再将根节点LL旋转
x.left = rightRightRotation(x.left);
return leftLeftRotation(x);
}
private Node rightLeftRotation(Node x) {// RL旋转，先将右儿子LL旋转，再将根节点RR旋转
x.right = leftLeftRotation(x.right);
return rightRightRotation(x);
}
private class Node {
private int value;
private Node left;
private Node right;
private int height;
public Node(int value int height) {
super();
this.height = height;
this.value = value;
left = right = null;
}
@Override
public String toString() {
return value "=>{" left " " right "}";
}
}
}
分析
平衡二叉树是一种完美的平衡树，它的查询效率非常的高，为O(N)。但是我们也看到其追求完美代价，那就是各种旋转带来的性能损耗。特别是在写频繁的场景下，树的很多性能消耗在了旋转上，如果读频率不是很高的话，那就得不偿失了。那么有没有没那么完美的二叉树，既兼顾了平衡又在插入删除时没那么复杂的树呢？答案就是红黑树，鉴于篇幅的关系，改天再跟大家分享吧。
喜欢我就关注我吧，如果你觉得这篇文章帮助到你了，还请帮忙转发，让更多人看到吧。
