1. 為什么會(huì)出現(xiàn)平衡二叉樹這種數(shù)據(jù)結(jié)構(gòu)？

之前學(xué)習(xí)了二叉排序樹，假如現(xiàn)有數(shù)列：1,2,3,4,5，要用這個(gè)數(shù)列創(chuàng)建一棵二叉排序樹，結(jié)果是這樣的：

看起來就怪怪的，其實(shí)就是斜著放的單鏈表。這棵樹存在以下問題：

• 左子樹全部為空，其實(shí)就是一個(gè)單鏈表；

• 其實(shí)查詢比單鏈表更慢，因?yàn)樵跈z索的時(shí)候要判斷左子樹是否為空，因?yàn)椴荒馨l(fā)揮二叉排序樹的優(yōu)勢。

為了解決上面的問題，平衡二叉樹(AVL樹) 就應(yīng)運(yùn)而生了。

2. 什么是平衡二叉樹？

• 平衡二叉樹又叫AVL樹，也叫平衡二叉搜索樹，可以保證較高的查詢效率；

• 它是一棵空樹，或者是左右子樹的高度差的絕對(duì)值不會(huì)超過1，并且左右兩棵子樹都是一棵平衡二叉樹；

• 平衡二叉樹常用的實(shí)現(xiàn)算法有紅黑樹，AVL，替罪羊樹，Treap，伸展樹等；

3. 如何創(chuàng)建平衡二叉樹？

(1). 左旋轉(zhuǎn)思路：

假如現(xiàn)有數(shù)列：4,3,6,5,7,8，創(chuàng)建出來的二叉樹排序數(shù)如下圖：

節(jié)點(diǎn)4的左子樹高度為1，右子樹高度為3，高度差是2，所以不是平衡二叉樹。如果要將其變成平衡二叉樹該怎么做呢？因?yàn)槠溆易訕涞母叨雀?，要分點(diǎn)兒給左子樹，所以方法叫做左旋轉(zhuǎn)。具體步驟如下：

• 創(chuàng)建一個(gè)新節(jié)點(diǎn)newNode，值為根節(jié)點(diǎn)的值，即：Node newNode = new Node(4)；

• 當(dāng)前節(jié)點(diǎn)currentNode(節(jié)點(diǎn)4)的左子樹(節(jié)點(diǎn)3)作為新節(jié)點(diǎn)的左子樹，即：newNode.left = currentNode.left；

• 當(dāng)前節(jié)點(diǎn)(節(jié)點(diǎn)4)的右子樹(節(jié)點(diǎn)6)的左子樹(節(jié)點(diǎn)5)作為新節(jié)點(diǎn)的右子樹，即：newNode.right = currentNode.right.left；

• 把當(dāng)前節(jié)點(diǎn)(節(jié)點(diǎn)4)的值換成右子節(jié)點(diǎn)(節(jié)點(diǎn)6)的值，即現(xiàn)在二叉樹的效果如下：

• 當(dāng)前節(jié)點(diǎn)的右子樹(節(jié)點(diǎn)6)的右子樹(節(jié)點(diǎn)7)作為當(dāng)前節(jié)點(diǎn)的右子樹，即：currentNode.right = currentNode.right.right，設(shè)置完后效果如下：

• 最后一步，新節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的左子樹，即：currentNode.left = newNode，最后效果如下：

(2). 右旋轉(zhuǎn)：

過程和左旋轉(zhuǎn)類似，只不過是將左旋轉(zhuǎn)步驟中的左右顛倒一下。

• 創(chuàng)建新節(jié)點(diǎn)，值為當(dāng)前根節(jié)點(diǎn)的值；

• 當(dāng)前節(jié)點(diǎn)的右子樹作為新節(jié)點(diǎn)的右子樹；

• 當(dāng)前節(jié)點(diǎn)左子樹的右子樹作為新節(jié)點(diǎn)的左子樹；

• 把當(dāng)前節(jié)點(diǎn)的值換成左子節(jié)點(diǎn)的值；

• 當(dāng)前節(jié)點(diǎn)的左子樹的左子樹作為當(dāng)前節(jié)點(diǎn)的左子樹；

• 新節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的右子樹。

(3). 代碼實(shí)現(xiàn)左/右旋轉(zhuǎn)：

首先創(chuàng)建如下的AVL樹類：

public class AvlTree {

 // 根節(jié)點(diǎn)
 private Node root;

 /**
  * 給外部調(diào)用的添加節(jié)點(diǎn)的方法
  * 
  * @param value
  */
 public void add(int value) {
  add(new Node(value));
 }

 /**
  * 添加節(jié)點(diǎn)
  * 
  * @param node
  */
 public void add(Node node) {
  if (root == null) {
   root = node;
  } else {
   root.add(node);
  }
 }

 /**
  * 中序遍歷
  */
 public void infixOrder() {
  if (root != null) {
   root.infixOrder();
  } else {
   throw new IllegalArgumentException("二叉排序樹為空");
  }
 }
 

 /**
  * 節(jié)點(diǎn)類
  * 
  * @author zhu
  *
  */
 class Node {
  int value;
  Node left;
  Node right;

  public Node(int value) {
   this.value = value;
  }

  /**
   * 添加節(jié)點(diǎn)
   * 
   * @param node
   */
  public void add(Node node) {
   if (node == null) {
    return;
   }
   // 如果傳入的節(jié)點(diǎn)值比當(dāng)前節(jié)點(diǎn)值小
   if (node.value < this.value) {
    // 如果當(dāng)前節(jié)點(diǎn)左邊沒有節(jié)點(diǎn)
    if (this.left == null) {
     // 就把node掛在當(dāng)前節(jié)點(diǎn)左邊
     this.left = node;
    } else {
     // 當(dāng)前節(jié)點(diǎn)左邊有節(jié)點(diǎn)，那就遞歸
     this.left.add(node);
    }
   } else { // 往右邊添加
    if (this.right == null) {
     // 就把node掛在當(dāng)前節(jié)點(diǎn)右邊
     this.right = node;
    } else {
     // 當(dāng)前節(jié)點(diǎn)右邊有節(jié)點(diǎn)，那就遞歸
     this.right.add(node);
    }
   }
  }

  /**
   * 中序遍歷
   */
  public void infixOrder() {
   // 往左遞歸
   if (this.left != null) {
    this.left.infixOrder();
   }
   // 輸出當(dāng)前節(jié)點(diǎn)
   System.out.println(this.value);
   // 向右遞歸
   if (this.right != null) {
    this.right.infixOrder();
   }
  }
 }

 public Node getRoot() {
  return root;
 }

 public void setRoot(Node root) {
  this.root = root;
 }
}

目前這棵樹只有最基本的添加節(jié)點(diǎn)和中序遍歷的方法。因?yàn)槭欠褚M(jìn)行旋轉(zhuǎn)，需要根據(jù)樹的高度來進(jìn)行判斷，所以在Node內(nèi)部類中新增如下方法，用來獲取樹的高度：

/**
* 返回以當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)的樹的高度
* 
* @return
*/
public int height() {
 // 左右子樹不為空的時(shí)候就遞歸，直到它為空為止，然后取左右子樹中高度較大的值作為樹的高度，最后加1是自身也算一個(gè)高度
 return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}

/**
* 返回當(dāng)前節(jié)點(diǎn)左子樹的高度
* 
* @return
*/
public int leftHeight() {
 return left == null ? 0 : left.height();
}

/**
* 返回當(dāng)前節(jié)點(diǎn)右子樹的高度
* 
* @return
*/
public int rightHeight() {
 return right == null ? 0 : right.height();
}

接下來測試一下獲取樹的高度的代碼是否正確：

public static void main(String[] args) {
 int[] arr = {4,3,6,5,7,8};
//  int[] arr = {10,12,8,9,7,6}; // 需要右旋轉(zhuǎn)的樹
 AvlTree avlTree = new AvlTree();
 for (int i=0; i<arr.length; i++) {
  avlTree.add(arr[i]);
 }
 System.out.printf("樹的高度：%s\r\n" ,avlTree.getRoot().height());
 System.out.printf("根節(jié)點(diǎn)左子樹的高度：%s\r\n", avlTree.getRoot().leftHeight());
 System.out.printf("根節(jié)點(diǎn)右子樹的高度：%s\r\n", avlTree.getRoot().rightHeight());
}

如果正常的話，會(huì)打印出：

樹的高度：4
根節(jié)點(diǎn)左子樹的高度：1
根節(jié)點(diǎn)右子樹的高度：3

接下來，就按照上面左/右旋轉(zhuǎn)的步驟，在Node內(nèi)部類中寫兩個(gè)方法就好了，如下：

/**
* 左旋轉(zhuǎn)
*/
public void leftRotate() {
 // 1. 創(chuàng)建新節(jié)點(diǎn)，值為當(dāng)前節(jié)點(diǎn)的值
 Node newNode = new Node(value);
 // 2. 當(dāng)前節(jié)點(diǎn)左子樹作為新節(jié)點(diǎn)的左子樹
 newNode.left = left;
 // 3. 當(dāng)前節(jié)點(diǎn)的右子樹的左子樹作為新節(jié)點(diǎn)的右子樹
 newNode.right = right.left;
 // 4. 把當(dāng)前節(jié)點(diǎn)的值換成右子節(jié)點(diǎn)的值
 value = right.value;
 // 5. 當(dāng)前節(jié)點(diǎn)的右子樹的右子樹作為當(dāng)前節(jié)點(diǎn)的右子樹
 right = right.right;
 // 6. 新節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的左子樹
 left = newNode;
}
  
/**
* 右旋轉(zhuǎn)，和左旋轉(zhuǎn)對(duì)稱
*/
public void rightRotate() {
 Node newNode = new Node(value);
 newNode.right = right;
 newNode.left = left.right;
 value = left.value;
 left = left.left;
 right = newNode;
}

寫好之后怎么用呢？在Node內(nèi)部類中的add方法中，每添加完一個(gè)節(jié)點(diǎn)，就判斷一下是否需要進(jìn)行左右旋轉(zhuǎn)，如果需要，就調(diào)用左右旋轉(zhuǎn)的方法，如下：

public void add(Node node) {
 if (node == null) {
  return;
 }
 // 如果傳入的節(jié)點(diǎn)值比當(dāng)前節(jié)點(diǎn)值小
 if (node.value < this.value) {
  // 如果當(dāng)前節(jié)點(diǎn)左邊沒有節(jié)點(diǎn)
  if (this.left == null) {
   // 就把node掛在當(dāng)前節(jié)點(diǎn)左邊
   this.left = node;
  } else {
   // 當(dāng)前節(jié)點(diǎn)左邊有節(jié)點(diǎn)，那就遞歸
   this.left.add(node);
  }
 } else { // 往右邊添加
  if (this.right == null) {
   // 就把node掛在當(dāng)前節(jié)點(diǎn)右邊
   this.right = node;
  } else {
   // 當(dāng)前節(jié)點(diǎn)右邊有節(jié)點(diǎn)，那就遞歸
   this.right.add(node);
  }
 }
 // 添加完一個(gè)節(jié)點(diǎn)后，如果(右子樹高度 - 左子樹高度) > 1，左旋轉(zhuǎn)
 if (rightHeight() - leftHeight() > 1) {
  leftRotate();
 }
 // 添加完一個(gè)節(jié)點(diǎn)后，如果(左子樹高度 - 右子樹高度) > 1，右旋轉(zhuǎn)
 if (leftHeight() - rightHeight() > 1) {
  rightRotate();
 }
}

這樣每次添加一個(gè)節(jié)點(diǎn)后，都會(huì)判斷是否需要旋轉(zhuǎn)。同樣是剛才測試的代碼，再次運(yùn)行，就會(huì)發(fā)現(xiàn)樹的高度、左右子樹的高度都發(fā)生變化了。

(4). 雙旋轉(zhuǎn)：

假如現(xiàn)有數(shù)列：10,11,7,6,8,9，用上面的測試代碼跑一下，發(fā)現(xiàn)結(jié)果如下：

樹的高度：4
根節(jié)點(diǎn)左子樹的高度：1
根節(jié)點(diǎn)右子樹的高度：3

沒錯(cuò)，即使進(jìn)行了左右旋轉(zhuǎn)，它仍然不是平衡二叉樹。這種情況，需要進(jìn)行雙旋轉(zhuǎn)。怎么進(jìn)行雙旋轉(zhuǎn)呢？

就是當(dāng)進(jìn)行右旋轉(zhuǎn)的時(shí)候，進(jìn)行如下操作：

• 如果它的左子樹的右子樹高度大于它的左子樹的左子樹的高度，就先對(duì)它的左節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)；

當(dāng)進(jìn)行左旋轉(zhuǎn)的時(shí)候，進(jìn)行如下操作：

• 如果它的右子樹的左子樹高度大于它的右子樹的右子樹的高度，就先對(duì)它的右節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)；

代碼就是在剛才add方法中加的兩個(gè)if中再加一層判斷，如下：

// 添加完一個(gè)節(jié)點(diǎn)后，如果(右子樹高度 - 左子樹高度) > 1，左旋轉(zhuǎn)
if (rightHeight() - leftHeight() > 1) {
 if (right != null && right.leftHeight() > right.rightHeight()) {
  right.rightRotate();
 }
 leftRotate();
 return;
}
// 添加完一個(gè)節(jié)點(diǎn)后，如果(左子樹高度 - 右子樹高度) > 1，右旋轉(zhuǎn)
if (leftHeight() - rightHeight() > 1) {
 if (left != null && left.rightHeight() > left.leftHeight()) {
  left.leftRotate();
 }
 rightRotate();
}

加上這段邏輯，數(shù)列10,11,7,6,8,9形成的二叉樹也是平衡的了。