总结平衡二叉树概念、插入（旋转）对应java实现

一、定义及原理

平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

定义平衡二叉树：

public class BalancedTree {
private Integer iData;
private Double dData;
private BalancedTree leftNode;
private BalancedTree rightNode;
private Integer height = 1;
public BalancedTree(Integer data, BalancedTree left, BalancedTree right) {
this.iData = data;
this.leftNode = left;
this.rightNode = right;
}
public BalancedTree(Integer data) {
this(data, null, null);
}
/**
* 判断是否为叶子结点
*
* @return
*/
public boolean isLeaf() {
return this.leftNode == null && this.rightNode == null;
}
/**
* 计算节点深度
*
* @param node
* @return
*/
public int height(BalancedTree node) {
if (node == null) {
return 0;
} else {
int l = height(node.leftNode);
int r = height(node.rightNode);
return (l > r) ? (l + 1) : (r + 1);//返回并加上当前层
}
}
// ...
}

二、结点插入

1、插入原理

根据二叉平衡树的定义，一定保持左右子树深度绝对值小于1.在平衡二叉树插入工作一定考虑深度差，在AVL树进行插入工作时候，困难在于可能破坏AVL树的平衡属性。

针对此类问题，需要根据树的实际结构进行几种简单的旋转（rotation）操作就可以让树恢复AVL树的平衡性质。

2、旋转问题

对于一个平衡的节点，由于任意节点最多有两个儿子，因此高度不平衡时，此节点的两颗子树的高度差2.容易看出，这种不平衡出现在下面四种情况：

• 6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。
• 6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。
• 2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左。
• 2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右。

从图2中可以可以看出，1和4两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，我们称之为单旋转。2和3两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，我们称之为双旋转。

3、旋转操作

单旋转

单旋转是针对于左左和右右这两种情况的解决方案，这两种情况是对称的，只要解决了左左这种情况，右右就很好办了。图3是左左情况的解决方案，节点k2不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的左子树X子树，所以属于左左情况。

为使树恢复平衡，我们把k2变成这棵树的根节点，因为k2大于k1，把k2置于k1的右子树上，而原本在k1右子树的Y大于k1，小于k2，就把Y置于k2的左子树上，这样既满足了二叉查找树的性质，又满足了平衡二叉树的性质。

这样的操作只需要一部分指针改变，结果我们得到另外一颗二叉查找树，它是一棵AVL树，因为X向上一移动了一层，Y还停留在原来的层面上，Z向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同，插入操作使得X高度长高了。因此，由于这颗子树高度没有变化，所以通往根节点的路径就不需要继续旋转了。

对于左左情况：进行右旋转=顺时针旋转，旋转轴的右子节点移动到父节点（失衡点）的左子节点。

对于右右情况：进行左旋转=逆时针旋转，旋转轴的左子节点移动到父节点（失衡点）的右子节点。

以左左情况为例，找到失衡点w，它的左子节点x变为父节点，而w则变为x的右子节点。

单旋转代码实现：

/**
* 左左单旋转(LL旋转)，w变为根节点，x变为w的右子树
*
* @param x
* @return
*/
private BalancedTree singleRotateLeft(BalancedTree x) {
/**
* 左左情况（x的左右相差2，w的左大于右），进行一次向右旋转
* x
* / \
* w c
* / \
* A B
* /
* m
*
*/
//把w结点旋转为根结点
BalancedTree w = x.leftNode;
//同时w的右子树变为x的左子树
x.leftNode = w.rightNode;
//x变为w的右子树
w.rightNode = x;
//返回新的根结点
return w;
}

右右情况则完全相反，找到失衡点w，它的右子节点x变为父节点，而w则变为x的左子节点。

单旋转代码实现：

/**
* 右右单旋转(RR旋转)，x变为w的根节点，w变为x的左子树
*
* @param w
* @return
*/
private BalancedTree singleRotateRight(BalancedTree w) {
/**
* 右右情况（x的左右相差2，w的左大于右），进行一次向右旋转
* W
* / \
* A X
* / \
* B C
* \
* m
*
*/
BalancedTree x = w.rightNode;
w.rightNode = x.leftNode;
x.leftNode = w;
//返回新的根结点
return x;
}

双旋转

对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。双旋转是针对于这两种情况的解决方案，同样的，这样两种情况也是对称的，只要解决了左右这种情况，右左就很好办了。图4是左右情况的解决方案，节点k3不满足平衡特性，因为它的左子树k1比右子树Z深2层，而且k1子树中，更深的一层的是k1的右子树k2子树，所以属于左右情况。

为使树恢复平衡，我们需要进行两步，第一步，把k1作为根，进行一次z左旋转，旋转之后就变成了左左情况，所以第二步再进行一次右旋转，最后得到了一棵以k2为根的平衡二叉树树。

双旋转代码实现：

/**
* 左右旋转（LR旋转） x（根） w y 节点 经过旋转把y变成根节点
* @param x 失衡点
* @return
*/
private BalancedTree doubleRotateWithLeft(BalancedTree x){
/**
* 左右情况，需要二次旋转，失衡点x的左子节点w，也是一个失衡点
* 需要将y变为整棵树的根节点，以达到平衡；图示可看成以y为轴进行两次旋转
*
* x
* / \
* w D
* / \
* A y
* / \
* B C
*
*
*/
// w是x的左节点
x.leftNode=singleRotateRight(x.leftNode);
return singleRotateLeft(x);
}
/**
* 右左旋转（RL旋转） x（根） w y 节点，经过旋转把y变为根节点
* @param x
* @return
*/
private BalancedTree doubleRotateWithRight(BalancedTree x){
/**
* 右左情况，需要二次旋转，失衡点为x和w，因为x的左右节点深度差-2（右大于左），w的左节点深度大于右节点
* 需要针对失衡点进行二次旋转,先是w左旋（顺时针），再x右旋（逆时针）
* x
* / \
* A w
* / \
* y D
* / \
* B C
*
*
*/
// w是x的右节点
x.rightNode=singleRotateLeft(x.rightNode);
return singleRotateRight(x);
}

能够触发旋转操作的，就是平衡二叉树的插入和删除了。

4、节点插入实现

与BST（二叉查找树）的插入实现原理一样，使用递归算法，根据值大小查找到插入位置，然后进行插入操作，插入完成后，我们需要进行平衡判断，评估子树是否需要进行平衡修复，需要则利用上述的四种情景套入代码即可，最后要记得重新计算插入结点路径上的高度。代码实现如下：

/**
* 插入节点
*
* @param data
* @param pNode 平衡节点/插入目标节点
* @return
*/
public BalancedTree insert(Integer data, BalancedTree pNode) {
if (pNode == null) {
pNode = new BalancedTree(data);
} else if (data.compareTo(pNode.getData()) <0) {
// 向左子树寻找插入位置
pNode.leftNode = insert(data, pNode.leftNode);
//插入完成后计算子树的高度，大于1则需要重新恢复平衡，由于是左边插入，左子树的高度肯定大于等于右子树的高度
if (height(pNode.leftNode) - height(pNode.rightNode) > 1) {
//判断data是插入点的左孩子还是右孩子
if (data.compareTo(pNode.leftNode.getData()) <0) {
// 进行LL旋转
pNode = singleRotateLeft(pNode);
} else {
// LR
pNode = doubleRotateWithLeft(pNode);
}
}
} else if (data.compareTo(pNode.getData()) > 0) {
// 向右子树寻找插入位置
pNode.rightNode = insert(data, pNode.rightNode);
if (height(pNode.rightNode) - height(pNode.leftNode) > 1) {
if (data.compareTo(pNode.rightNode.getData()) <0) {
pNode = doubleRotateWithRight(pNode);
} else {
pNode = singleRotateRight(pNode);
}
}
} else {
}
//重新计算各个结点的高度
pNode.height = Math.max(height(pNode.leftNode), height(pNode.rightNode)) + 1;
return pNode;
}

5、节点删除实现

 关于平衡二叉树的删除，我们这里给出一种递归的实现方案，和二叉查找树中删除方法的实现类似，但是在移除结点后需要进行平衡检测，以便判断是否需要进行平衡修复，主要明白的是，这种实现方式在删除时效率并不高，不过我们并不打算过多讨论它，更复杂的删除操作过程将放在以后进行讨论。下面给出实现代码：

/**
* 删除节点
*
* @param data 期望删除的节点值
* @param pNode 平衡节点/删除目标节点
* @return
*/
public BalancedTree remove(Integer data, BalancedTree pNode) {
if (pNode == null) {
return null;
}
int result = data.compareTo(pNode.getData());
//从左子树寻找需要删除的元素
if (result <0) {
pNode.leftNode = remove(data, pNode.leftNode);
// 检测是否平衡
if (height(pNode.rightNode) - height(pNode.leftNode) > 1) {
BalancedTree currentNode = pNode;
// 判断需要哪种旋转
if (height(currentNode.leftNode) // RR
pNode= singleRotateRight(currentNode);
} else {
// RL
pNode= doubleRotateWithRight(currentNode);
}
}
} else if (result > 0) {
pNode.rightNode = remove(data, pNode.rightNode);
//检测是否平衡
if (height(pNode.leftNode) - height(pNode.rightNode) > 1) {
BalancedTree currentNode = pNode;
// 判断需要哪种旋转
if (height(currentNode.rightNode) // LL
pNode = singleRotateLeft(currentNode);
} else {
// RL
pNode = doubleRotateWithLeft(currentNode);
}
}
} else if (pNode.rightNode != null && pNode.leftNode != null) {
//已找到需要删除的元素,并且要删除的结点拥有两个子节点
//寻找替换结点值、保留当前节点的左右子树(根据二叉树节点删除后替换逻辑）
pNode.data = findMin(pNode.rightNode).data;
//移除用于替换的结点 ；由于从右子树中找到了替换的节点值，并保存到了data中，因此需要将右子树中对应的替换节点删除
pNode.rightNode = remove(pNode.data, pNode.rightNode);
} else {
//只有一个孩子结点或者只是叶子结点的情况
pNode = (pNode.leftNode != null) ? pNode.leftNode : pNode.rightNode;
}
//更新高度值
if (pNode != null)
pNode.height = Math.max(height(pNode.leftNode), height(pNode.rightNode)) + 1;
return pNode;
}
private BalancedTree findMin(BalancedTree pNode) {
if (pNode == null)//结束条件
return null;
else if (pNode.leftNode == null)//如果没有左结点,那么pNode就是最小的
return pNode;
return findMin(pNode.leftNode);
}

注意，二叉树删除逻辑：

对于二叉树来说，删除是一种比较麻烦的操作，因为涉及到了多种情况（设要删除的结点为q，其父母结点为p）：

• 如果要删除的结点q恰好是叶子结点，那么它可以立即被删除
• 如果要删除的结点q拥有一个孩子结点，则应该调整要被删除的父结点(p.left 或 p.right)指向被删除结点的孩子结点（q.left 或 q.right）
• 如果要删除的结点q拥有两个孩子结点，则删除策略是用q的右子树的最小的数据替代要被删除结点的数据，并递归删除用于替换的结点(此时该结点已为空)，此时二叉查找树的结构并不会被打乱，其特性仍旧生效。采用这样策略的主要原因是右子树的最小结点的数据替换要被删除的结点后可以满足维持二叉查找树的结构和特性，又因为右子树最小结点不可能有左孩子，删除起来也相对简单些。
   

其中第三点，示例如下：

删除节点12后，从右子树14中遍历寻找左子树13，直到找到左子树为空的节点13，即为可替换节点。替换完成后，需要从右子树14中将该节点删除。

测试功能代码：

// 测试节点的插入导致旋转、删除导致旋转
BalancedTree root = new BalancedTree(12);
root = root.insert(10, root);
root = root.insert(13, root);
root = root.insert(15, root);
root = root.insert(16, root);
root = root.insert(17, root);
//root = root.remove(17, root);
//root = root.remove(16, root);
root = root.remove(12, root);
root = root.remove(13, root);
root = root.remove(10, root);
System.out.println("end");
// 测试删除过程中需要遍历子节点进行替换的逻辑
BalancedTree root = new BalancedTree(15);
root = root.insert(12, root);
root = root.insert(16, root);
root = root.insert(17, root);
root = root.insert(10, root);
root = root.insert(14, root);
root = root.insert(13, root);
root = root.remove(12, root);
System.out.println("end");
// 以上伪代码，验证时自行调整

参考：（本文涉及以下文章摘录，代码部分有经过测试后调整逻辑）

http://www.cnblogs.com/polly333/p/4798944.html

https://blog.csdn.net/pacosonswjtu/article/details/50522677（按图示理解旋转方式）

https://blog.csdn.net/javazejian/article/details/53892797#右右单旋转rr情景④分析（理解旋转实现）