平衡二叉树是一棵特殊的二叉排序树，可以快速的实现查找，其查找时间复杂的为log2N。
平衡二叉树的特性
- 具备二叉排序树的所有特性；
- 左子树和右子树深度差的绝对值不超过1；
- 左右子树都是平衡二叉树；
在插入过程中，二叉树的平衡性可能遭到破坏，这时需要对二叉树进行调整。
LL型失衡
左子树高度减去右子树的高度大于1。
//左旋转
_proto._lRotate = function(node) {
var rc = node.rChild;
rc.pNode = node.pNode;
node.rChild = rc.lChild;
rc.lChild && (rc.lChild.pNode = node);
rc.lChild = node;
if (node == this.root) {
this.root = rc;
} else if (node.pNode) {
if (node.pNode.lChild == node) {
node.pNode.lChild = rc;
} else {
node.pNode.rChild = rc;
}
}
node.pNode = rc;
}
RR型失衡
右子树高度减去左子树的高度大于1。
//右旋转
_proto._rRotate = function(node) {
var lc = node.lChild;
lc.pNode = node.pNode;
node.lChild = lc.rChild;
lc.rChild && (lc.rChild.pNode = node);
lc.rChild = node;
if (node == this.root) {
this.root = lc;
} else if (node.pNode) {
if (node.pNode.lChild == node) {
node.pNode.lChild = lc;
} else {
node.pNode.rChild = lc;
}
}
node.pNode = lc;
}
LR型失衡
左子树高度减去右子树的高度大于1，并 lChild 的右子树高度大于 lChild 的左子树的高度。
//先右旋转，再左旋转
_proto._rlRotate = function(node) {
this._rRotate(node.rChild);
this._lRotate(node);
}
RL型失衡
右子树高度减去左子树的高度大于1，并 rChild 的左子树高度大于 rChild 的右子树的高度。
//先左旋转，再右旋转
_proto._lrRotate = function(node) {
this._lRotate(node.lChild);
this._rRotate(node);
}
平衡二叉树的删除
平衡二叉树的删除和二叉排序树的删除原则一样，如果待删除的既有左子树又有右子树，则将其与对应的叶子节点（没有左子树或者没有右子树）替换位置，再删除该叶子节点。
同样，平衡二叉树节点的删除也有可能导致二叉树失衡，其调整原则和插入节点时一致。