1温峭、基本概念
平衡因子：某個節(jié)點的左右子樹的高度差
AVL數(shù)的特點：
1、每個節(jié)點的平衡因子只可能是1字支、0凤藏、-1（絕對值1奸忽，如果超過1，稱為“失衡”）
2揖庄、每個節(jié)點的左右子樹高度差不超過1
3栗菜、搜索添加刪除的時間復雜度為O(logn)
平衡二叉樹
2、二叉樹失衡
往上面二叉樹中添加13蹄梢，會導致二叉樹失衡
最壞的情況會導致所有祖先節(jié)點失衡疙筹。
父節(jié)點、非祖先節(jié)點禁炒，都不可能失衡
3而咆、調(diào)整為平衡二叉樹的方法
3.1、LL-右旋轉（單旋）
右旋
如上圖所示通過旋轉節(jié)點g幕袱，將樹調(diào)整為右側的二叉樹暴备，讓p成為二叉樹的根節(jié)點
3.2、RR-左旋轉（單旋）
左旋
如上圖所示通過旋轉節(jié)點g们豌，將樹調(diào)整為右側的二叉樹涯捻，讓p成為二叉樹的根節(jié)點
3.3、LR-RR左旋轉玛痊，LL右旋轉（雙旋）
左旋汰瘫、右旋
如上圖所示通過旋轉節(jié)點p，將n調(diào)整為p的左子樹（如圖中間位置）擂煞。在通過旋轉g節(jié)點混弥，讓g成為n的右子樹，最終得到平衡二叉樹
3.4对省、RL-LL右旋轉蝗拿，RR左旋轉（雙旋）
右旋-左旋
如上圖所示通過旋轉節(jié)點p，將n調(diào)整為p的右子樹（如圖中間位置）蒿涎。在通過步驟2將g成為n的左子樹哀托，最終得到平衡二叉樹
3.5、統(tǒng)一旋轉操作
4劳秋、關鍵代碼實現(xiàn)
4.1仓手、分別對每種旋轉處理
// 添加每個節(jié)點后，調(diào)整二叉樹的平衡
protected void afterAdd(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {
// 更新高度
updateHeight(node);
} else {
// 恢復平衡
rebalance(node);
// 整顆樹恢復平衡
break;
}
}
}
// 恢復平衡玻淑，grand:高度最低的不平衡節(jié)點
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);
}
}
}
// 平衡因子 <= 1
private boolean isBalanced(Node<E> node) {
return Math.abs(((AVLNode<E>)node).balanceFactor()) <= 1;
}
private void rotateLeft(Node<E> grand) {
Node<E> parent = grand.right;
Node<E> child = parent.left;
grand.right = child;
parent.left = grand;
afterRotate(grand, parent, child);
}
private 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);
}
private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
parent.parent = grand.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;
// 更新高度
updateHeight(grand);
updateHeight(parent);
}
private void updateHeight(Node<E> node) {
((AVLNode<E>) node).updateHeight();
}
4.2嗽冒、統(tǒng)一操作實現(xiàn)
// 刪除子節(jié)點后重新調(diào)整二叉樹的平衡
protected void afterRemove(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {
// 更新高度
updateHeight(node);
} else {
rebalance2(node);
}
}
}
// grand 高度最低的不平衡點
private void rebalance2(Node<E> grand) {
Node<E> parent = ((AVLNode<E>)grand).tallerChild();
Node<E> node = ((AVLNode<E>)parent).tallerChild();
if (parent.isLeftChild()) {
if (node.isLeftChild()) { // LL
rotate(grand, node.left, node, node.right, parent, parent.right,grand, grand.right);
} else { // LR
rotate(grand, parent.left, parent, node.left, node, node.right,grand, grand.right);
}
} else {
if (node.isLeftChild()) { // RL
rotate(grand, grand.left, grand, node.left, node, node.right, parent, parent.right);
} else { // RR
rotate(grand, grand.left, grand, parent.left, parent, node.left, node, node.right);
}
}
}
// rotate2
private void rotate(Node<E> r,
Node<E> a, Node<E> b, Node<E> c,
Node<E> d,
Node<E> e, Node<E> f, Node<E> g) {
// 讓d 成為這顆子樹的根節(jié)點
d.parent = r.parent;
if (r.isLeftChild()) {
r.parent.left = d;
} else if (r.isRightChild()) {
r.parent.right = d;
} else {
root = d;
}
// a-b-c
b.left = a;
if (a != null) {
a.parent = b;
}
b.right = c;
if (c != null) {
c.parent = b;
}
updateHeight(b);
// e-f-g
f.left = e;
if (e != null) {
e.parent = f;
}
f.right = g;
if (g != null) {
g.parent = f;
}
updateHeight(f);
// b-d-f
d.left = b;
d.right = f;
b.parent = d;
f.parent = d;
updateHeight(d);
}
