一、什麼是AVL樹？
首先解釋一下為什麼會出現AVL樹，上一篇我們學習了二叉搜尋樹，現在我們來分析一下二叉搜尋樹的時間複雜度。我們會發現在某些情況下，二叉搜尋樹的時間複雜度會由O(logn)會退化為O(n)，是以AVL樹就出現了，就是說AVL樹是二叉搜尋樹的一種改進。AVL樹裡多了一個平衡因子的概念。其實很好了解，平衡因子就是對樹平衡程度的一種度量。
平衡因子：該節點的左子樹的高度減去右子樹的高度的內插補點就叫做該節點的平衡因子。
AVL樹的平衡因子隻可能是-1、0、1，AVL樹的添加、删除時間複雜度都是O(logn)。
假如某節點的平衡因子大于1或者小于-1，我們就認為該節點是失衡的。
二、AVL樹的添加
我們先來看一個例子，我們往二叉樹中添加節點13，節點14的平衡因子變成了2，節點15平衡因子變成了2，節點9的平衡因子變成了-2。不幸的是它們全部失衡了，你會發現失衡的節點全是添加節點的祖父節點。
那麼問題就很明顯了，怎麼解決失衡問題？答案隻有兩個字：自旋
我們先梳理一下總體思路：
1.通過加入的節點，不斷循環，找到它的父節點。
2.然後判斷該節點是否失衡，如果不失衡，更新高度；如果失衡，進行自旋
第一種情況：右旋
假設我們不看中間的圖，你很快就會發現自旋的節點高度會下降，此時我們自旋的節點就是g。如果我們找到了第一個失衡節點，并通過自旋達到了平衡。那麼就說明整顆樹就達到了平衡。思考一下為什麼？仔細觀察一下添加節點之前樹的高度和添加節點後自旋後樹的高度是一樣的，那不就說明整顆樹現在是平衡的。
節點g右旋的操作：
g.left = p.right
p.right = g;
讓節點p成為子樹的根節點
更新T2、g的父節點
更新節點p，g的高度
第二種情況：左旋
節點g左旋的操作：
g.right = p.left
p.left = g;
讓節點p成為子樹的根節點
更新T1、g的父節點
更新節點p，g的高度
第三種情況：左右旋
先将節點p左旋，然後将節點g右旋
第四種情況：右左旋
下面開始coding：
這裡我們繼承的是我們上一次寫的二叉搜尋樹，我們要做的就是在原來添加的方法後，增加一個balanceTree(Node<E> node)即可。
public class AVLTree<E> extends BST<E> {
private static class AVLNode<E> extends Node<E>{
int height; //AVL樹的高度
public AVLNode(E element, Node<E> parent) {
super(element, parent);
}
//其實就是取左子樹和右子樹中高度比較高的，然後加1
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);
}
//傳回左子樹和右子樹比較高的子樹
public Node<E> tallerChild() {
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
if (leftHeight >= rightHeight){
return left;
}else{
return right;
}
}
}
}
我們重寫父類的方法：
@Override
protected void balanceTree(Node<E> node) {
//需要通過節點找到第一個失衡的節點
while((node = node.parent)!=null){
if(isBalance(node)){
//更新高度
updateHigh(node);
}else{
//自旋，維持平衡
rebalance(node);
}
}
}
//更新高度的方法
private void updateHigh(Node<E> node){
((AVLNode<E>)node).updateHeight();
}
剩下最核心的就是自旋了：
我把思路寫下來：
1.首先通過這個不平衡的節點grand，找到節點p，然後通過節點n
2.節點的方判斷是上面的四種情況：LL-右旋 ，LR-左右旋，RR-左旋，RL-右左旋
/**
* 恢複平衡
* @param grand 高度最低的那個不平衡節點
*/
private void rebalance(Node<E> grand) {
Node<E> parent = ((AVLNode<E>)grand).tallerChild(); //parent就是節點p
Node<E> node = ((AVLNode<E>)parent).tallerChild(); //節點node就是節點n
if(parent == node.left){
if(node == parent.left){ //LL - 右旋
rightTurn(grand);
}else{ //LR -左右旋
lefTurn(parent);
rightTurn(grand);
}
}else{
if(node == parent.right){ //RR - 左旋
lefTurn(grand);
}else{ //RL - 右左旋
rightTurn(parent);
lefTurn(grand);
}
}
updateHigh(grand);
updateHigh(parent);
}
左右旋的步驟就是我們上面總結的：
//左旋
private void lefTurn(Node<E> grand) {
Node<E> parent = grand.right; //節點p
Node<E> child = parent.left; //子樹T1
grand.right = child;
parent.left = grand;
//讓p成為根節點
parent.parent = grand.parent;
if(grand == grand.parent.left){
grand.parent.left = parent;
}else if(grand == grand.parent.right){
grand.parent.right = parent;
}else{
root = parent;
}
if(child!=null){
child.parent = grand; //更新t1的parent
}
grand.parent = parent; //更新grand的parent
}
//右旋
private void rightTurn(Node<E> grand) {
Node<E> parent = grand.left; //節點p
Node<E> child = parent.right; //子樹T2
grand.left = child;
parent.right = grand;
//讓p成為根節點
parent.parent = grand.parent;
if(grand == grand.parent.left){
grand.parent.left = parent;
}else if(grand == grand.parent.right){
grand.parent.right = parent;
}else{
root = parent;
}
//更新parent屬性
if(child!=null){
child.parent = grand;
}
grand.parent = parent;
}
我們發現上面四種情況很麻煩，有大佬找到了規律，我們一起看看。
統一所有旋轉操作：
我們發現無論是哪種旋轉，最後得到的樹的結構都是一緻的，是以我們可以寫一個方法就可以，參數就是：a,b,c,d,e,f,g七個節點。
private void rotate(
Node<E> r, // 子樹的根節點
Node<E> b, Node<E> c,
Node<E> d,
Node<E> e, Node<E> f) {
// 讓d成為這棵子樹的根節點
d.parent = r.parent;
if (r.isLeftChild()) {
r.parent.left = d;
} else if (r.isRightChild()) {
r.parent.right = d;
} else {
root = d;
}
//b-c
b.right = c;
if (c != null) {
c.parent = b;
}
updateHigh(b);
// e-f
f.left = e;
if (e != null) {
e.parent = f;
}
updateHigh(f);
// b-d-f
d.left = b;
d.right = f;
b.parent = d;
f.parent = d;
updateHigh(d);
}
三、AVL樹的删除
首先思考删除節點，會導緻誰的失衡。删除節點16, 節點15和節點11失衡，我們會發現删除節點影響的是父節點或者是祖父節點的平衡因子，進而會導緻它們的失衡。
删除方法還是和添加方法是有點差別的：
添加的時候我們隻需要找到高度最低的節點，通過旋轉，就能使整顆樹達到平衡，原因在上面已經講過了。但是删除不一樣，舉個例子：看上面左邊這個二叉樹，删除節點16導緻節點15失衡，然後我們通過右旋節點15，但是這個子樹樹的高度變了，比原來少了1，那不就可能影響16更上面的祖父節點的平衡因子嗎？是以我們需要一直疊代下去，知道整顆樹的平衡。
@Override
protected void afterRemove(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {
// 更新高度
updateHeight(node);
} else {
// 恢複平衡
rebalance(node);
}
}
}
最後給出完整的代碼：
第一個類是核心代碼：後面兩個類就是上次寫的二叉搜尋樹，因為AVL樹也是一種二叉搜素樹，隻不過它比二叉搜尋樹多了一個維持自己平衡的動作，正是這個動作使得AVL樹的時間複雜度維持在O(logn),不會出現二叉搜尋樹退化成連結清單的情況。
package AVL樹;
import java.util.Comparator;
public class AVLTree<E> extends BST<E> {
private static class AVLNode<E> extends Node<E>{
int height; //AVL樹的高度
public AVLNode(E element, Node<E> parent) {
super(element, parent);
}
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);
}
public Node<E> tallerChild() {
int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
if (leftHeight >= rightHeight){
return left;
}else{
return right;
}
}
}
@Override
protected void balanceTree(Node<E> node) {
//需要通過節點找到第一個失衡的節點
while((node = node.parent)!=null){
if(isBalance(node)){
//更新高度
updateHigh(node);
}else{
//自旋，維持平衡
rebalance(node);
}
}
}
/**
* 恢複平衡
* @param grand 高度最低的那個不平衡節點
*/
private void rebalance(Node<E> grand) {
Node<E> parent = ((AVLNode<E>)grand).tallerChild();
Node<E> node = ((AVLNode<E>)parent).tallerChild();
if(parent == node.left){
if(node == parent.left){ //LL- 右旋
rightTurn(grand);
}else{ //LR -左有旋
lefTurn(parent);
rightTurn(grand);
}
}else{
if(node == parent.right){ //RR -左旋
lefTurn(grand);
}else{ //RL - 右左旋
rightTurn(parent);
lefTurn(grand);
}
}
updateHigh(grand);
updateHigh(parent);
}
private void rotate(
Node<E> r, // 子樹的根節點
Node<E> b, Node<E> c,
Node<E> d,
Node<E> e, Node<E> f) {
// 讓d成為這棵子樹的根節點
d.parent = r.parent;
if (r.isLeftChild()) {
r.parent.left = d;
} else if (r.isRightChild()) {
r.parent.right = d;
} else {
root = d;
}
//b-c
b.right = c;
if (c != null) {
c.parent = b;
}
updateHigh(b);
// e-f
f.left = e;
if (e != null) {
e.parent = f;
}
updateHigh(f);
// b-d-f
d.left = b;
d.right = f;
b.parent = d;
f.parent = d;
updateHigh(d);
}
private void lefTurn(Node<E> grand) {
Node<E> parent = grand.right; //節點p
Node<E> child = parent.left; //子樹T1
grand.right = child;
parent.left = grand;
//讓p成為根節點
parent.parent = grand.parent;
if(grand == grand.parent.left){
grand.parent.left = parent;
}else if(grand == grand.parent.right){
grand.parent.right = parent;
}else{
root = parent;
}
if(child!=null){
child.parent = grand; //更新t1的parent
}
grand.parent = parent; //更新grand的parent
}
private void rightTurn(Node<E> grand) {
Node<E> parent = grand.left; //節點p
Node<E> child = parent.right; //子樹T2
grand.left = child;
parent.right = grand;
//讓p成為根節點
parent.parent = grand.parent;
if(grand == grand.parent.left){
grand.parent.left = parent;
}else if(grand == grand.parent.right){
grand.parent.right = parent;
}else{
root = parent;
}
//更新parent屬性
if(child!=null){
child.parent = grand;
}
grand.parent = parent;
}
private void updateHigh(Node<E> node){
((AVLNode<E>)node).updateHeight();
}
/**
*
* @param node
* @return
*/
private boolean isBalance(Node<E> node){
return Math.abs(getHigh(node)) <=1;
}
public int getHigh(Node<E> node){
if(node == null) return 0;
if(node.left==null && node.right == null) return 0;
int leftHigh = 0;
int rightHigh = 0;
if(node.left!=null){
leftHigh = getHigh(node.left);
}
if(node.right!=null){
rightHigh = getHigh(node.right);
}
return leftHigh - rightHigh;
}
}
package AVL樹;
import AVL樹.printer.BinaryTreeInfo;
import java.util.LinkedList;
import java.util.Queue;
@SuppressWarnings("unchecked")
public class BinaryTree<E> implements BinaryTreeInfo {
protected int size;
protected Node<E> root;
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
root = null;
size = 0;
}
public void preorder(Visitor<E> visitor) {
if (visitor == null) return;
preorder(root, visitor);
}
private void preorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
visitor.stop = visitor.visit(node.element);
preorder(node.left, visitor);
preorder(node.right, visitor);
}
public void inorder(Visitor<E> visitor) {
if (visitor == null) return;
inorder(root, visitor);
}
private void inorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
inorder(node.left, visitor);
if (visitor.stop) return;
visitor.stop = visitor.visit(node.element);
inorder(node.right, visitor);
}
public void postorder(Visitor<E> visitor) {
if (visitor == null) return;
postorder(root, visitor);
}
private void postorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
postorder(node.left, visitor);
postorder(node.right, visitor);
if (visitor.stop) return;
visitor.stop = visitor.visit(node.element);
}
public void levelOrder(Visitor<E> visitor) {
if (root == null || visitor == null) return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (visitor.visit(node.element)) return;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
public boolean isComplete() {
if (root == null) return false;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (leaf && !node.isLeaf()) return false;
if (node.left != null) {
queue.offer(node.left);
} else if (node.right != null) {
return false;
}
if (node.right != null) {
queue.offer(node.right);
} else { // 後面周遊的節點都必須是葉子節點
leaf = true;
}
}
return true;
}
public int height() {
if (root == null) return 0;
// 樹的高度
int height = 0;
// 存儲着每一層的元素數量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
levelSize--;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (levelSize == 0) { // 意味着即将要通路下一層
levelSize = queue.size();
height++;
}
}
return height;
}
public int height2() {
return height(root);
}
private int height(Node<E> node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
protected Node<E> createNode(E element, Node<E> parent) {
return new Node<>(element, parent);
}
protected Node<E> predecessor(Node<E> node) {
if (node == null) return null;
// 前驅節點在左子樹當中（left.right.right.right....）
Node<E> p = node.left;
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
// 從父節點、祖父節點中尋找前驅節點
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
// node.parent == null
// node == node.parent.right
return node.parent;
}
protected Node<E> successor(Node<E> node) {
if (node == null) return null;
// 前驅節點在左子樹當中（right.left.left.left....）
Node<E> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 從父節點、祖父節點中尋找前驅節點
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
public static abstract class Visitor<E> {
boolean stop;
/**
* @return 如果傳回true，就代表停止周遊
*/
abstract boolean visit(E element);
}
protected static class Node<E> {
E element;
Node<E> left;
Node<E> right;
Node<E> parent;
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
public boolean isLeaf() {
return left == null && right == null;
}
public boolean hasTwoChildren() {
return left != null && right != null;
}
public boolean isLeftChild() {
return parent != null && this == parent.left;
}
public boolean isRightChild() {
return parent != null && this == parent.right;
}
public Node<E> sibling() {
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
}
@Override
public Object root() {
return root;
}
@Override
public Object left(Object node) {
return ((Node<E>)node).left;
}
@Override
public Object right(Object node) {
return ((Node<E>)node).right;
}
@Override
public Object string(Object node) {
return node;
}
}
package AVL樹;
import java.util.Comparator;
@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
private Comparator<E> comparator;
public BST() {
this(null);
}
public BST(Comparator<E> comparator) {
this.comparator = comparator;
}
public void add(E element) {
elementNotNullCheck(element);
// 添加第一個節點
if (root == null) {
root = createNode(element, null);
size++;
// 新添加節點之後的處理
balanceTree(root);
return;
}
// 添加的不是第一個節點
// 找到父節點
Node<E> parent = root;
Node<E> node = root;
int cmp = 0;
do {
cmp = compare(element, node.element);
parent = node;
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { // 相等
node.element = element;
return;
}
} while (node != null);
// 看看插入到父節點的哪個位置
Node<E> newNode = createNode(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
// 新添加節點之後的處理
balanceTree(newNode);
}
/**
* 添加node之後的調整
* @param node 新添加的節點
*/
protected void balanceTree(Node<E> node) { }
/**
* 删除node之後的調整
* @param node 被删除的節點
*/
protected void afterRemove(Node<E> node) { }
public void remove(E element) {
remove(node(element));
}
public boolean contains(E element) {
return node(element) != null;
}
private void remove(Node<E> node) {
if (node == null) return;
size--;
if (node.hasTwoChildren()) { // 度為2的節點
// 找到後繼節點
Node<E> s = successor(node);
// 用後繼節點的值覆寫度為2的節點的值
node.element = s.element;
// 删除後繼節點
node = s;
}
// 删除node節點（node的度必然是1或者0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) { // node是度為1的節點
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度為1的節點并且是根節點
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
// 删除節點之後的處理
afterRemove(node);
} else if (node.parent == null) { // node是葉子節點并且是根節點
root = null;
// 删除節點之後的處理
afterRemove(node);
} else { // node是葉子節點，但不是根節點
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
// 删除節點之後的處理
afterRemove(node);
}
}
private Node<E> node(E element) {
Node<E> node = root;
while (node != null) {
int cmp = compare(element, node.element);
if (cmp == 0) return node;
if (cmp > 0) {
node = node.right;
} else { // cmp < 0
node = node.left;
}
}
return null;
}
/**
* @return 傳回值等于0，代表e1和e2相等；傳回值大于0，代表e1大于e2；傳回值小于于0，代表e1小于e2
*/
private int compare(E e1, E e2) {
if (comparator != null) {
return comparator.compare(e1, e2);
}
return ((Comparable<E>)e1).compareTo(e2);
}
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
}