AVL树的特点
- 每个节点的平衡因子只可能是 -1、 0、 1 （绝对值 < 1,如果大于一，则称之失衡）
- 每个节点的左右两端的高度差不超过1
- 添加 搜索 删除 的时间复杂度是O(log n)
- 平衡因子：某节点的左右子树的高度差
- AVL树：被称之为 平衡二叉搜索树
添加
- 在二叉搜索树节点添加之后，维护该二叉树遵守AVL树的性质（AVL树继承二叉搜索树）
protected void afterAdd(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {
// 更新高度
((AVLNode<E>)node).updateHeight();
} else {
// 恢复平衡
rebalance(node);
// 整棵树恢复平衡
break;
}
}
}
- 循环查看 被添加节点所有祖先节点的的平衡因子 （从被添加节点的父节点开始），如果没有失衡就更新该节点的高度，失衡了就回复平衡。（我的理解是 被添加节点的父节点都不会失衡 跟新 父节点高度之后 从祖父节点开始都可能失衡）
更新节点高度
public void updateHeight() {
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
height = 1 + Math.max(leftHeight, rightHeight);
}
恢复平衡
/**
* 恢复平衡
* @param grand 高度最低的那个不平衡节点
*/
private void rebalance(Node<E> grand) {
//获取失衡节点的儿子节点（左右子节点比较高的那个）
Node<E> parent = ((AVLNode<E>)grand).tallerChild();
//获取失衡节点的孙子节点
Node<E> node = ((AVLNode<E>)parent).tallerChild();
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
rotateRight(grand);
} else { // LR
rotateLeft(parent);
rotateRight(grand);
}
} else { // R
if (node.isLeftChild()) { // RL
rotateRight(parent);
rotateLeft(grand);
} else { // RR
rotateLeft(grand);
}
}
}
- parent节点在grand节点的left边 node节点在parent 的left边 只需要对 grand 进行 right旋转，即可恢复该失衡节点的平衡
- parent节点在grand节点的left边 node节点在parent 的rigth边 则需要先对parent进行left 旋转 grand进行right旋转，即可恢复该失衡节点的平衡
- parent节点在grand节点的right边 node节点在parent 的right边 只需要对 grand 进行 left旋转，即可恢复该失衡节点的平衡
- parent节点在grand节点的right边 node节点在parent 的left边 则需要先对parent进行right 旋转 grand进行left旋转，即可恢复该失衡节点的平衡
旋转
protected void rotateLeft(Node<E> grand) {
//对谁进行左旋转 谁就被认为是祖父节点
//找到 parent 节点
Node<E> parent = grand.right;
//找到child 节点
Node<E> child = parent.left;
//左旋转时
// grang 下来 pareng.left = grand;
// grang.right = child
grand.right = child;
parent.left = grand;
// 改变了 树中的 两条线 所以得维护三个节点的父节点属性 与 原来指向grang 改为指向 parent
afterRotate(grand, parent, child);
}
protected void rotateRight(Node<E> grand) {
Node<E> parent = grand.left;
Node<E> child = parent.right;
grand.left = child;
parent.right = grand;
afterRotate(grand, parent, child);
}
protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
// 让parent称为子树的根节点
parent.parent = grand.parent;
//原来指向garent的那条线 指向 parent
if (grand.isLeftChild()) {
grand.parent.left = parent;
} else if (grand.isRightChild()) {
grand.parent.right = parent;
} else { // grand是root节点
root = parent;
}
// 更新child的parent
if (child != null) {
child.parent = grand;
}
// 更新grand的parent
grand.parent = parent;
}
删除
protected void afterRemove(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {
// 更新高度
updateHeight(node);
} else {
// 恢复平衡
rebalance(node);
}
}
}
- 删除逻辑和添加相似 从被删除节点开始 往上查失衡节点 恢复平衡
- 真正删除的节点都是 度 为 1或0 的节点
- AVL树被删除的节点 都是在倒数两层内的 要么是 叶子节点 要么事 倒数第二层度为一的节点
- 在二叉树删除中 删除度为1的节点时 afterRemove（node） node 传的是用以替换被节点的节点 （这个在二叉搜索树的删除方法里能看到）（不影响AVL 树的删除 是为了红黑树删除搞得 因为 AVL树 就是从删除节点往上找失衡节点恢复平衡的）
