數據結構與演算法——平衡二叉樹（AVL樹）

• 2021 年 9 月 18 日
• 筆記
• 數據結構與演算法

二叉排序樹存在的問題

一個數列 {1,2,3,4,5,6}，創建一顆二叉排序樹（BST）

創建完成的樹如上圖所示，那麼它存在的問題有以下幾點：

1. 左子樹全部為空，從形式上看，更像一個單鏈表

2. 插入速度沒有影響

3. 但查詢速度明顯降低

   因為需要依次比較，不能利用二叉排序樹的折半優勢。而且每次都還要比較左子樹，可能比單鏈表查詢速度還慢。

那麼解決這個劣勢的方案就是：平衡二叉樹（AVL）。

基本介紹

平衡二叉樹也叫 平衡二叉搜索樹（Self-balancing binary search tree），又被稱為 AVL 樹，可以保證 查詢效率較高。它是解決 二叉排序 可能出現的查詢問題。

它的特點：是一顆空樹或它的 左右兩個子樹的高度差的絕對值不超過 1，並且左右兩個子樹都是一棵平衡二叉樹。

平衡二叉樹的常用實現方法有：

• 紅黑樹
• AVL（演算法）
• 替罪羊樹
• Treap
• 伸展樹

想了解更多的可以去看 平衡樹——維基百科

如下所述，哪些是平衡二叉樹？

1. 是平衡二叉樹：

   • 左子樹高度為 2
   • 右子樹高度為 1

   他們差值為 1

2. 也是平衡二叉樹

3. 不是平衡二叉樹

   1. 左子樹高度為 3
   2. 右子樹高度為 1

   他們差值為 2，所以不是

單旋轉（左旋轉）

一個數列 4,3,6,5,7,8 ，創建出它對應的平衡二叉樹。

思路分析：下圖紅線部分是調整流程。

按照規則調整完成之後，形成了下面這樣一棵樹

完整流程如下圖所示：

如上圖，插入 8 時，發現左右子樹高度相差大於 1，則進行左旋轉：

1. 創建一個新的節點 newNode，值等於當前 根節點 的值（上圖根節點為 4）

2. 把新節點的 左子樹 設置為當前節點（根節點）的 左子樹

   newNode.left = this.left
   

3. 把新節點的 右子樹 設置為當前節點(根節點)的 右子樹 的 左子樹

   newNode.right = this.right.left
   

4. 把 當前節點(根節點) 的值換為 右子節點 的值

   this.value = this.right.value
   

5. 把 當前節點（根節點） 的右子樹設置為 右子樹的右子樹(按上圖的話就是 7)

   this.right = this.right.right
   

6. 把 當前節點(根節點) 的左子樹設置為新節點newNode

   this.left = this.newNode
   

注：左圖是調整前，右圖是調整後。注意調整前的 6 那個節點，調整之後，沒有節點指向他了。也就是說，遍歷的時候它是不可達的。那麼將會自動的被垃圾回收掉。

樹高度計算

前面說過，平衡二叉樹是為了解決二叉排序樹中可能出現的查找效率問題，那麼基本上的程式碼都可以在之前的二叉排序樹上進行優化。那麼下面只給出與當前主題相關的程式碼，最後放出一份完整的程式碼。

樹的高度計算，我們需要得到 3 個高度：

1. 這顆樹的整體高度
2. 左子樹的高度
3. 右子樹的高度

public class AvlTreeTest {
    /**
     * 樹高度測試
     */
    @Test
    public void heightTest() {
        AvlTree tree = new AvlTree();
        int[] arr = {4, 3, 6, 5, 7, 8};
        for (int i = 0; i < arr.length; i++) {
            tree.add(new Node(arr[i]));
        }
        tree.infixOrder();
        System.out.println("樹高度：" + tree.root.height());   // 4
        System.out.println("左樹高度：" + tree.root.leftHeight());  // 1
        System.out.println("右樹高度：" + tree.root.rightHeight()); // 3
    }
}

/**
 * 排序二叉樹
 */
class AvlTree {
    Node root;

    public Node getRoot() {
        return root;
    }
}

/**
 * 節點
 */
class Node {
   /**
     * 以當前節點為基礎：計算出它包含它子樹的所有高度
     *
     * @return
     */
    public int height() {
        /*
          這裡使用了遞歸：返回了左右子樹中，最高的那一個數值。
          遞歸原理：第一個開始統計的時候，一定是一個葉子節點
                  根據這個邏輯：葉子節點的 Math.max(0,0) = 0  看下面程式碼
                  因為當前節點算一層，所以 + 1;

                  返回到上一層的時候，至少是這樣：Math.max(1,0) = 1
                  然後把自己本身的層 +1。 以此類推，返回到根節點的時候，就拿到了從包含根節點的樹的高度
                  所以這個 +1 是精髓所在
         */
        return Math.max(
                (left == null ? 0 : left.height()),
                (right == null ? 0 : right.height())
        ) + 1;
    }

    /**
     * 計算左子樹的高度
     *
     * @return
     */
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        // 如果從根節點開始的話
        // 其實它從中間分開，左側就有很多的小樹
        // 所以還是要計算左右樹的高度，返回一個最大的值，只不過是開始節點變化了
        return left.height();
    }

    /**
     * 計算右子樹的高度，與上面的計算左子樹同理
     *
     * @return
     */
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }
}

測試輸出

3
4
5
6
7
8
樹高度：4
左樹高度：1
右樹高度：3 

旋轉

說下旋轉的時機：也就是什麼時機採取做旋轉的操作？

當然是：當 右子樹高度 - 左子樹高度 > 1 時，才執行左旋轉。

這裡就得到一些資訊:

1. 每次添加完一個節點後，就需要檢查樹的高度

2. 滿足 右子樹高度 - 左子樹高度 > 1，那麼一定滿足下面的條件：

   ①左子樹高度為 1

   ②右子樹高度為 3

   也就是符合這張圖

   

也正是有如上的資訊邏輯，在實現旋轉的時候，只要按照思路分析寫就可以了，不需要進行邊界判定了。

class Node {
   /**
     * 添加節點：按照排序二叉樹的要求添加
     *
     * @param node
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        // 如果添加的值小於當前節點，則往左走
        if (node.value < value) {
            // 左節點為空，則直接掛在上面
            if (left == null) {
                left = node;
            } else {
                // 否則繼續往下查找
                left.add(node);
            }
        } else {
            // 往右走
            if (right == null) {
                right = node;
            } else {
                right.add(node);
            }
        }

        // 旋轉的時候有以下規則
        // 每添加一個節點之後：檢查樹的高度是否平衡
        //      如果右子樹高度 - 左子樹高度 > 1，則左旋轉
        //      也就是說：每次旋轉的層只涉及到 4 層(對照筆記上的圖示理解)
        if (rightHeight() - leftHeight() > 1) {
            leftRotate();
        }
    }

    /**
     * 以當前節點為根節點，進行左旋轉
     */
    public void leftRotate() {
        // 1. 創建一個新的節點 newNode，值等於當前 根節點 的值
        Node newNode = new Node(value);
        // 2. 把 新節點的 左子樹 設置為當前節點的左子樹
        newNode.left = left;
        // 3. 把 新節點的 右子樹 設置為當前節點的 右子樹的左子樹
        newNode.right = right.left;
        // 4. 把 當前節點的值，替換為 右子樹 節點的子
        value = right.value;
        // 5. 把 當前節點 的 右節點 設置為 右子樹的右子樹
        right = right.right;
        // 6. 把 當前節點 的 左節點 設置為 新節點
        left = newNode;
    }
}

測試

    /**
     * 左旋轉測試
     */
    @Test
    public void leftRotatedTest() {
        AvlTree tree = new AvlTree();
        int[] arr = {4, 3, 6, 5, 7, 8};
        for (int i = 0; i < arr.length; i++) {
            tree.add(new Node(arr[i]));
        }
        tree.infixOrder();
        System.out.println("樹高度：" + tree.root.height());   // 3
        System.out.println("左樹高度：" + tree.root.leftHeight());  // 2
        System.out.println("右樹高度：" + tree.root.rightHeight()); // 2
    }

測試輸出

3
4
5
6
7
8
樹高度：3
左樹高度：2
右樹高度：2

看完程式碼之後，它的旋轉其實就是，將 root 節點，往下沉到了，root.right 節點下面。

看著上圖，是否有想過，貌似根本就可以不用前面講解的 6 個步驟來旋轉：

1. 不用創建新節點
2. 直接將 node 節點下沉
3. 更改 node 的 right 節點為 right.left
4. 更改 right.left = node

其實就已經完成了旋轉。但是你仔細想一想，旋轉邏輯是寫在 node 裡面的， avgTree 中的引用如何改變？除非把旋轉邏輯移動到 avgTree 中去，就可以省略掉新建節點的步驟來完成。

右旋轉

弄懂了左旋轉，對於右旋轉其實就很好理解了：

• 左旋轉：右 - 左 > 1，把右邊的往左邊旋轉一層
• 右旋轉：左 - 右 > 1，把左邊的往右邊旋轉一層

他們其實是反著來的，那麼右旋轉的思路如下：

1. 創建一個新的節點 newNode，值等於當前 根節點 的值（以 4 創建）

2. 把新節點的 右子樹 設置為當前節點（根節點）的 右子樹

   newNode.right = right
   

3. 把新節點的 左子樹 設置為當前節點（根節點）的 左子樹的右子樹

   newNode.left = left.right
   

4. 把 當前節點（根節點） 的值換為 左子節點 的值

   value = left.value
   

5. 把 當前節點 （根節點）的左子樹設置為 左子樹的左子樹

   left = left.left 
   

6. 把 當前節點 的右子樹設置為新節點

   right = newNode
   

上述步驟就是對下圖的描述：查看圖示更清楚

class Node {
   /**
     * 添加節點：按照排序二叉樹的要求添加
     *
     * @param node
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        // 如果添加的值小於當前節點，則往左走
        if (node.value < value) {
            // 左節點為空，則直接掛在上面
            if (left == null) {
                left = node;
            } else {
                // 否則繼續往下查找
                left.add(node);
            }
        } else {
            // 往右走
            if (right == null) {
                right = node;
            } else {
                right.add(node);
            }
        }

        // 旋轉的時候有以下規則
        // 每添加一個節點之後：檢查樹的高度是否平衡
        //      如果右子樹高度 - 左子樹高度 > 1，則左旋轉
        //      也就是說：每次旋轉的層只涉及到 4 層(對照筆記上的圖示理解)
        if (rightHeight() - leftHeight() > 1) {
            leftRotate();
            return;
        }

        if (leftHeight() - rightHeight() > 1) {
            rightRotate();
        }
    }
      /**
     * 以當前節點為根節點，進行右旋轉
     */
    public void rightRotate() {
        // 1. 創建一個新的節點 newNode，值等於當前 根節點 的值
        Node newNode = new Node(value);
        // 2. 把 新節點的 右子樹 設置為當前節點的右子樹
        newNode.right = right;
        // 3. 把 新節點的 左子樹 設置為當前節點的 左子樹的右子樹
        newNode.left = left.right;
        // 4. 把 當前節點的值，替換為 左子樹 節點的子
        value = left.value;
        // 5. 把 當前節點 的 左節點 設置為 左子樹的左子樹
        left = left.left;
        // 6. 把 當前節點 的 右節點 設置為 新節點
        right = newNode;
    }
}

測試

    /**
     * 右旋轉測試
     */
    @Test
    public void rightRotatedTest() {
        AvlTree tree = new AvlTree();
        int[] arr = {10, 12, 8, 9, 7, 6};
        for (int i = 0; i < arr.length; i++) {
            tree.add(new Node(arr[i]));
        }
        tree.infixOrder();
        System.out.println("樹高度：" + tree.root.height());   // 3
        System.out.println("左樹高度：" + tree.root.leftHeight());  // 2
        System.out.println("右樹高度：" + tree.root.rightHeight()); // 2
        System.out.println("當前根節點：" + tree.root); // 8
    }

測試輸出

6
7
8
9
10
12
樹高度：3
左樹高度：2
右樹高度：2
當前根節點：Node{value=8}

雙旋轉

在前面的例子中，使用單旋轉（即一次旋轉）就可以將非平衡二叉樹轉換為平衡二叉樹。

但是在某些情況下，就無法做到。比如下面這兩組數列

int[] arr ={10,11,7,6,8,9}
int[] arr ={2,1,6,5,7,3}

運行上面的程式碼測試可以發現並未生效

    /**
     * 不能通過單旋轉解決的場景
     */
    @Test
    public void notLeftOrRightRotatedTest() {
        AvlTree tree = new AvlTree();
        int[] arr = {10, 11, 7, 6, 8, 9};
        for (int i = 0; i < arr.length; i++) {
            tree.add(new Node(arr[i]));
        }
        tree.infixOrder();
        System.out.println("樹高度：" + tree.root.height());   // 4
        System.out.println("左樹高度：" + tree.root.leftHeight());  // 1
        System.out.println("右樹高度：" + tree.root.rightHeight()); // 3
        System.out.println("當前根節點：" + tree.root); // 7
    }

測試輸出

6
7
8
9
10
11
樹高度：4
左樹高度：1
右樹高度：3
當前根節點：Node{value=7}

為什麼會出現這種情況呢？看下圖

左側這個樹滿足 leftHeight - rightHeight > 1 ，也就是滿足右旋轉，旋轉之後，樹結構變化了。但是還是一個非平衡二叉樹。

它的主要原因是：root 左子樹的 左子樹高度 小於 右子樹的高度。即：節點 7 的左子樹高度小於右子樹的高度。

解決辦法：

1. 先將 7 這個節點作為 root 節點，進行左旋轉
2. 再將原始的 root 節點進行右旋轉

過程示意圖如下：

其實可以參考下前面兩個單旋轉的圖例，它有這樣一個特點：

1. 右旋轉：
   • root 的 left 左子樹高度 大於 右子樹高度
   • 右旋轉的時候，會將 left.right 旋轉到 right.left 節點上
2. 左旋轉：
   • root 的 right 右子樹高度 大於 左子樹高度
   • 左旋轉的時候，會將 right.left 旋轉到 left.right 上。

如果不滿足這個要求，在第二個操作的時候，就會導致 2 層的高度被旋轉到 1 層的節點下面，導致不平衡了。

那麼解決程式碼如下：

在 Node 類的 add 方法中進行雙節點邏輯的執行。

    /**
     * 添加節點：按照排序二叉樹的要求添加
     *
     * @param node
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        // 如果添加的值小於當前節點，則往左走
        if (node.value < value) {
            // 左節點為空，則直接掛在上面
            if (left == null) {
                left = node;
            } else {
                // 否則繼續往下查找
                left.add(node);
            }
        } else {
            // 往右走
            if (right == null) {
                right = node;
            } else {
                right.add(node);
            }
        }

        // 旋轉的時候有以下規則
        // 每添加一個節點之後：檢查樹的高度是否平衡
        //      如果右子樹高度 - 左子樹高度 > 1，則左旋轉
        //      也就是說：每次旋轉的層只涉及到 4 層(對照筆記上的圖示理解)
        // 						  小旋轉的時候：只涉及到 3 層，旋轉的時候，最多操作了當前節點和左右節點，所以不會導致 NPE 問題,這一點一定要明白
        if (rightHeight() - leftHeight() > 1) {
            // 當 右節點的：左子樹高度 大於 右子樹的高度時，將 right 節點進行 右旋轉
            if (right != null && right.leftHeight() > right.rightHeight()) {
                 right.rightRotate();
            }
            leftRotate();
            return;
        }

        if (leftHeight() - rightHeight() > 1) {
            // 當 左節點的：右子樹高度 大於 左子樹的高度時，將 left 節點進行左旋轉
            if (left != null && left.rightHeight() > left.leftHeight()) {
                left.leftRotate();
            }
            rightRotate();
        }
    }

測試程式碼

   /**
     * 添加雙旋轉之後，之前測試不能旋轉的數列進行測試
     */
    @Test
    public void doubleRotatedTest() {
        AvlTree tree = new AvlTree();
        int[] arr = {10, 11, 7, 6, 8, 9};
//        int[] arr ={2,1,6,5,7,3}
        for (int i = 0; i < arr.length; i++) {
            tree.add(new Node(arr[i]));
        }
        tree.infixOrder();
        System.out.println("樹高度：" + tree.root.height());
        System.out.println("左樹高度：" + tree.root.leftHeight());
        System.out.println("右樹高度：" + tree.root.rightHeight());
        System.out.println("當前根節點：" + tree.root); 
    }

輸出資訊

6
7
8
9
10
11
樹高度：3
左樹高度：2
右樹高度：2
當前根節點：Node{value=8}


1
2
3
5
6
7
樹高度：3
左樹高度：2
右樹高度：2
當前根節點：Node{value=5}

完整程式碼

public class AVLTreeDemo {

    public static void main(String[] args) {
        //int[] arr = {4,3,6,5,7,8};
        //int[] arr = { 10, 12, 8, 9, 7, 6 };
        int[] arr = {10, 11, 7, 6, 8, 9};
        //創建一個 AVLTree對象
        AVLTree avlTree = new AVLTree();
        //添加結點
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(new Node(arr[i]));
        }

        //遍歷
        System.out.println("中序遍歷");
        avlTree.infixOrder();

        System.out.println("在平衡處理~~");
        System.out.println("樹的高度=" + avlTree.getRoot().height()); //3
        System.out.println("樹的左子樹高度=" + avlTree.getRoot().leftHeight()); // 2
        System.out.println("樹的右子樹高度=" + avlTree.getRoot().rightHeight()); // 2
        System.out.println("當前的根結點=" + avlTree.getRoot());//8


    }

}

// 創建AVLTree
class AVLTree {
    private Node root;

    public Node getRoot() {
        return root;
    }

    // 查找要刪除的結點
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    // 查找父結點
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    // 編寫方法:
    // 1. 返回的 以node 為根結點的二叉排序樹的最小結點的值
    // 2. 刪除node 為根結點的二叉排序樹的最小結點

    /**
     * @param node 傳入的結點(當做二叉排序樹的根結點)
     * @return 返回的 以node 為根結點的二叉排序樹的最小結點的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        // 循環的查找左子節點，就會找到最小值
        while (target.left != null) {
            target = target.left;
        }
        // 這時 target就指向了最小結點
        // 刪除最小結點
        delNode(target.value);
        return target.value;
    }

    // 刪除結點
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            // 1.需求先去找到要刪除的結點 targetNode
            Node targetNode = search(value);
            // 如果沒有找到要刪除的結點
            if (targetNode == null) {
                return;
            }
            // 如果我們發現當前這顆二叉排序樹只有一個結點
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }

            // 去找到targetNode的父結點
            Node parent = searchParent(value);
            // 如果要刪除的結點是葉子結點
            if (targetNode.left == null && targetNode.right == null) {
                // 判斷targetNode 是父結點的左子結點，還是右子結點
                if (parent.left != null && parent.left.value == value) { // 是左子結點
                    parent.left = null;
                } else if (parent.right != null && parent.right.value == value) {// 是由子結點
                    parent.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) { // 刪除有兩顆子樹的節點
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;

            } else { // 刪除只有一顆子樹的結點
                // 如果要刪除的結點有左子結點
                if (targetNode.left != null) {
                    if (parent != null) {
                        // 如果 targetNode 是 parent 的左子結點
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else { // targetNode 是 parent 的右子結點
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else { // 如果要刪除的結點有右子結點
                    if (parent != null) {
                        // 如果 targetNode 是 parent 的左子結點
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else { // 如果 targetNode 是 parent 的右子結點
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }

            }

        }
    }

    // 添加結點的方法
    public void add(Node node) {
        if (root == null) {
            root = node;// 如果root為空則直接讓root指向node
        } else {
            root.add(node);
        }
    }

    // 中序遍歷
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序樹為空，不能遍歷");
        }
    }
}

// 創建Node結點
class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {

        this.value = value;
    }

    /**
     * 以當前節點為基礎：計算出它包含它子樹的所有高度
     *
     * @return
     */
    public int height() {
        /*
          這裡使用了遞歸：返回了左右子樹中，最高的那一個數值。
          遞歸原理：第一個開始統計的時候，一定是一個葉子節點
                  根據這個邏輯：葉子節點的 Math.max(0,0) = 0  看下面程式碼
                  因為當前節點算一層，所以 + 1;

                  返回到上一層的時候，至少是這樣：Math.max(1,0) = 1
                  然後把自己本身的層 +1。 以此類推，返回到根節點的時候，就拿到了從包含根節點的樹的高度
                  所以這個 +1 是精髓所在
         */
        return Math.max(
                (left == null ? 0 : left.height()),
                (right == null ? 0 : right.height())
        ) + 1;
    }

    /**
     * 計算左子樹的高度
     *
     * @return
     */
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        // 如果從根節點開始的話
        // 其實它從中間分開，左側就有很多的小樹
        // 所以還是要計算左右樹的高度，返回一個最大的值，只不過是開始節點變化了
        return left.height();
    }

    /**
     * 計算右子樹的高度，與上面的計算左子樹同理
     *
     * @return
     */
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }

    //左旋轉方法
    private void leftRotate() {

        //創建新的結點，以當前根結點的值
        Node newNode = new Node(value);
        //把新的結點的左子樹設置成當前結點的左子樹
        newNode.left = left;
        //把新的結點的右子樹設置成帶你過去結點的右子樹的左子樹
        newNode.right = right.left;
        //把當前結點的值替換成右子結點的值
        value = right.value;
        //把當前結點的右子樹設置成當前結點右子樹的右子樹
        right = right.right;
        //把當前結點的左子樹(左子結點)設置成新的結點
        left = newNode;


    }

    //右旋轉
    private void rightRotate() {
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right = newNode;
    }

    // 查找要刪除的結點

    /**
     * @param value 希望刪除的結點的值
     * @return 如果找到返回該結點，否則返回null
     */
    public Node search(int value) {
        if (value == this.value) { // 找到就是該結點
            return this;
        } else if (value < this.value) {// 如果查找的值小於當前結點，向左子樹遞歸查找
            // 如果左子結點為空
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else { // 如果查找的值不小於當前結點，向右子樹遞歸查找
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }

    }

    // 查找要刪除結點的父結點

    /**
     * @param value 要找到的結點的值
     * @return 返回的是要刪除的結點的父結點，如果沒有就返回null
     */
    public Node searchParent(int value) {
        // 如果當前結點就是要刪除的結點的父結點，就返回
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            // 如果查找的值小於當前結點的值, 並且當前結點的左子結點不為空
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value); // 向左子樹遞歸查找
            } else if (value >= this.value && this.right != null) {
                return this.right.searchParent(value); // 向右子樹遞歸查找
            } else {
                return null; // 沒有找到父結點
            }
        }

    }

    @Override
    public String toString() {
        return "Node [value=" + value + "]";
    }

    // 添加結點的方法
    // 遞歸的形式添加結點，注意需要滿足二叉排序樹的要求
    public void add(Node node) {
        if (node == null) {
            return;
        }

        // 判斷傳入的結點的值，和當前子樹的根結點的值關係
        if (node.value < this.value) {
            // 如果當前結點左子結點為null
            if (this.left == null) {
                this.left = node;
            } else {
                // 遞歸的向左子樹添加
                this.left.add(node);
            }
        } else { // 添加的結點的值大於 當前結點的值
            if (this.right == null) {
                this.right = node;
            } else {
                // 遞歸的向右子樹添加
                this.right.add(node);
            }

        }

        // 旋轉的時候有以下規則
        // 每添加一個節點之後：檢查樹的高度是否平衡
        //      如果右子樹高度 - 左子樹高度 > 1，則左旋轉
        //      也就是說：每次旋轉的層只涉及到 4 層(對照筆記上的圖示理解)
        // 						  小旋轉的時候：只涉及到 3 層，旋轉的時候，最多操作了當前節點和左右節點，所以不會導致 NPE 問題,這一點一定要明白
        if (rightHeight() - leftHeight() > 1) {
            // 當 右節點的：左子樹高度 大於 右子樹的高度時，將 right 節點進行 右旋轉
            if (right != null && right.leftHeight() > right.rightHeight()) {
                right.rightRotate();
            }
            leftRotate();
            return;
        }

        if (leftHeight() - rightHeight() > 1) {
            // 當 左節點的：右子樹高度 大於 左子樹的高度時，將 left 節點進行左旋轉
            if (left != null && left.rightHeight() > left.leftHeight()) {
                left.leftRotate();
            }
            rightRotate();
        }
    }

    // 中序遍歷
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

}