平衡二叉搜索樹

1. 樹的概念

image

一個(gè)樹由節(jié)點(diǎn)組成，這些節(jié)點(diǎn)包含根節(jié)點(diǎn)冗荸，父節(jié)點(diǎn)承璃，子節(jié)點(diǎn)，兄弟節(jié)點(diǎn)蚌本；沒有任何一個(gè)節(jié)點(diǎn)的樹稱為空樹盔粹；如果一棵樹只包含一個(gè)節(jié)點(diǎn)，那么該節(jié)點(diǎn)為根節(jié)點(diǎn)程癌；

節(jié)點(diǎn)的度（degree）: 子樹的個(gè)數(shù)
樹的度：所有節(jié)點(diǎn)度中的最大值
葉子節(jié)點(diǎn)：度為0的節(jié)點(diǎn)
非葉子節(jié)點(diǎn)：度不為0的節(jié)點(diǎn)
層數(shù)（level）: 根節(jié)點(diǎn)在第1層舷嗡，根節(jié)點(diǎn)的子節(jié)點(diǎn)在第2層，以此類推
節(jié)點(diǎn)的深度（depth）: 從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的唯一路徑的節(jié)點(diǎn)總數(shù)
樹的深度：所有節(jié)點(diǎn)深度的最大值
節(jié)點(diǎn)的高度：從當(dāng)前節(jié)點(diǎn)到最遠(yuǎn)葉節(jié)點(diǎn)的路徑節(jié)點(diǎn)總數(shù)
樹的高度：所有節(jié)點(diǎn)高度中的最大值
樹的深度等于樹的高度

二叉樹是每個(gè)節(jié)點(diǎn)的度最大為2的樹嵌莉，分別為 左子樹 或 右子樹进萄；樹按類型分為 有序樹 和 無序樹领跛，二叉樹是一種有序樹。二叉樹特征：

二叉樹

非空二叉樹的第 i 層祭犯，最多包含由 $i^{2-1}$ 個(gè)節(jié)點(diǎn)续崖，其中i >= 1;
高度為h的二叉樹上，最多包含 $2^h$ - 1 個(gè)節(jié)點(diǎn)枯怖，其中h >= 1;
對于任何一顆非空二叉樹，如果葉子節(jié)點(diǎn)個(gè)數(shù)為n0，度為2的節(jié)點(diǎn)個(gè)數(shù)為n2抛寝，則n0 = n2 + 1;

假設(shè)節(jié)點(diǎn)度為1的個(gè)數(shù)是n1，那么二叉樹的總節(jié)點(diǎn)樹n = n0 + n1 + n2曙旭；
二叉樹的邊數(shù) boundary = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1盗舰；
可得出 n0 = n2 + 1;

二叉樹分類：

真二叉樹 是度為0，或度為2
滿二叉樹 是度為0桂躏，或度為2钻趋，且所有的葉子節(jié)點(diǎn)都是最后一層；滿二叉樹肯定是真二叉樹剂习，而且是相同層數(shù)的二叉樹中節(jié)點(diǎn)個(gè)數(shù)最多的蛮位。

滿二叉樹
完全二叉樹 是指葉子節(jié)點(diǎn)只會出現(xiàn)在最后兩層，而且最后一層的葉子節(jié)點(diǎn)都是向左對齊的鳞绕。完全二叉樹從根節(jié)點(diǎn)到倒數(shù)第二層都是滿二叉樹失仁。完全二叉樹的特效如下：

度為1 的節(jié)點(diǎn)只有左節(jié)點(diǎn)。且度為1的節(jié)點(diǎn)數(shù)只有1個(gè)或0個(gè)们何；
同樣的節(jié)點(diǎn)數(shù)的二叉樹萄焦，完全二叉樹的高度最小冤竹；
假設(shè)完全二叉樹的高度為h (h >= 1), 那么有
至少有 $2^{h-1}$ 個(gè)節(jié)點(diǎn)拂封；
最多有 $2^{h}$ - 1 個(gè)節(jié)點(diǎn)茬射；
節(jié)點(diǎn)數(shù)為 $2^{h-1}$ <= n < $2^{h}$ ;
h-1 <= $\log_2{n}$ < h ；
h = floor( $\log_2{n}$ ) + 1 冒签；

如果有n 節(jié)點(diǎn)的完全二叉樹(n>0)躲株，從上到下，從左到右的節(jié)點(diǎn)排序索引從1開始镣衡，對于任意的第i個(gè)節(jié)點(diǎn)霜定；

i = 1 , 表示根節(jié)點(diǎn)；
i > 1 廊鸥，則父節(jié)點(diǎn)索引為floor(i/2)望浩；
如果 2i <= n，它的左子樹索引為 2i 惰说；
如果 2*i > n 磨德，該節(jié)點(diǎn)無左子樹；
如果 2i + 1 <= n ,該節(jié)點(diǎn)的右子節(jié)點(diǎn)索引為 2i + 1;
如果 2*i + 1 > n吆视，該節(jié)點(diǎn)無右子節(jié)點(diǎn)典挑；

2. 二叉樹的遍歷

二叉樹的遍歷分為 前序遍歷（Preorder Traversal），中序遍歷（Inorder Traversal）啦吧， 后序遍歷（Postorder Traversal）您觉，層序遍歷（Level Traversal）。

前序遍歷：從根節(jié)點(diǎn), 前序遍歷左子樹授滓，前序遍歷右子樹琳水。遍歷順序?yàn)椋?，2般堆，1在孝，3，6淮摔，5私沮，7；
中序遍歷：中序遍歷左子樹和橙、根節(jié)點(diǎn)仔燕、中序遍歷右子樹。遍歷順序?yàn)椋?胃碾，2涨享，3，4仆百，5厕隧，6，7；
后序遍歷：后序遍歷左子樹吁讨、后序遍歷右子樹髓迎、根節(jié)點(diǎn)。遍歷順序?yàn)椋?建丧，3排龄，2，5翎朱，7橄维，6，4拴曲；
層序遍歷：從上到下争舞，從左到右依次訪問每個(gè)節(jié)點(diǎn)。遍歷順序?yàn)椋?澈灼，2竞川，6，1叁熔，3委乌，5，7荣回；

層序遍歷的應(yīng)用：

計(jì)算二叉樹的高度：

    public int height() {
        if (root == null) return 0;
        
        // 樹的高度
        int height = 0;
        // 存儲著每一層的元素?cái)?shù)量
        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;
    }

    // 方式2
    private int height(Node<E> node) {
        if (node == null) return 0;
        return 1 + Math.max(height(node.left), height(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) { // node.left == null && node.right != null
                return false;
            }
            
            if (node.right != null) {
                queue.offer(node.right);
            } else { // node.right == null
                leaf = true;
            }
        }
        
        return true;
    }

前驅(qū)節(jié)點(diǎn)與后繼節(jié)點(diǎn)

前驅(qū)節(jié)點(diǎn)（predecessor）：中序遍歷時(shí)的前一個(gè)節(jié)點(diǎn)遭贸。即node.left.right.right.right...，直到right為null;
后繼節(jié)點(diǎn)（successor）：中序遍歷時(shí)的后一個(gè)節(jié)點(diǎn)驹马。即node.right.left.left.left...革砸，直到left為null;

3. 二叉搜索樹

二叉搜索樹是二叉樹的一種除秀，又被稱為二叉查找樹糯累、二叉排序樹。英文縮寫為BST册踩。

任意一個(gè)節(jié)點(diǎn)的值大于其左子樹所有節(jié)點(diǎn)的值泳姐；
任意一個(gè)節(jié)點(diǎn)的值小于其右子樹所有節(jié)點(diǎn)的值；
二叉搜索樹節(jié)點(diǎn)的值必須具備可比較性暂吉。比如int胖秒， float, 如果是 自定義的對象 必須指明比較方式；
二叉搜索樹的搜索慕的、刪除阎肝、添加最壞時(shí)間復(fù)雜度均可優(yōu)化為O(logn)；
不允許為null肮街；

4. 平橫二叉搜索樹

時(shí)間復(fù)雜度分析

上圖為二叉搜索樹的時(shí)間復(fù)雜度风题，當(dāng)n較大時(shí)兩者的差異比較明顯。所以為了保障二叉搜索樹的性能，需要保障左右子樹的平衡沛硅。

平衡：當(dāng)節(jié)點(diǎn)數(shù)量固定時(shí)眼刃，左右子樹的高度越接近，這顆樹就越平衡摇肌，即樹的高度越低擂红。最理想的平衡像完全二叉樹、滿二叉樹围小，高度達(dá)到最小昵骤。

改進(jìn)二叉搜索樹的方式是在節(jié)點(diǎn)的添加，刪除操作之后肯适，想辦法讓二叉搜索樹達(dá)到平衡涉茧，從而達(dá)到一顆適度平衡的二叉搜索樹，稱為平衡二叉樹疹娶。

平衡二叉樹 英文簡稱BBST伴栓，常見的典型平衡二叉樹有：

AVL， Window NT內(nèi)核中廣泛使用雨饺；
紅黑樹钳垮， java的TreeMap, TreeSet, HashMap, HashSet等廣泛使用。

5. AVL

平衡因子（Balance Factor）指某個(gè)節(jié)點(diǎn) 左右子樹的高度差额港；
AVL 特點(diǎn)：

每個(gè)節(jié)點(diǎn)的平衡因子只能為-1饺窿、0、1移斩；

搜索肚医，添加，刪除的時(shí)間復(fù)雜度為O(logn)向瓷；

添加節(jié)點(diǎn)導(dǎo)致的失衡以及解決辦法：

向AVL樹中添加節(jié)點(diǎn)時(shí)（只會在葉子節(jié)點(diǎn)添加）肠套，可能會導(dǎo)致所有祖先節(jié)點(diǎn)都失衡，但是父節(jié)點(diǎn)猖任、非祖父節(jié)點(diǎn)都是不可能失衡的你稚。
LL ----- 右旋轉(zhuǎn)

右旋轉(zhuǎn)
RR ----- 左旋轉(zhuǎn)

左旋轉(zhuǎn)
LR ----- LR 旋轉(zhuǎn)

LR旋轉(zhuǎn)
RL ----- RL旋轉(zhuǎn): 與LR 旋轉(zhuǎn)相似，先將p右旋轉(zhuǎn)朱躺，再將g左旋轉(zhuǎn)刁赖；略...

添加節(jié)點(diǎn)后，調(diào)整平衡

刪除節(jié)點(diǎn)導(dǎo)致的失衡以及解決辦法：

可能會導(dǎo)致 父節(jié)點(diǎn) 或 祖先節(jié)點(diǎn) 失衡（只有1個(gè)節(jié)點(diǎn)失衡）长搀，其他節(jié)點(diǎn)不會導(dǎo)致失衡宇弛。恢復(fù)平衡后源请，可能會導(dǎo)致更高層的祖先節(jié)點(diǎn)失衡枪芒。刪除和添加的都是根據(jù)節(jié)點(diǎn)所在的位置是否失衡轿钠，來進(jìn)行旋轉(zhuǎn)，以達(dá)到平衡病苗。
一直遞歸父節(jié)點(diǎn)以及祖父節(jié)點(diǎn)疗垛，先判斷平衡因子是否-1，0硫朦，1贷腕，如果不是調(diào)整節(jié)點(diǎn)的平衡(rebalance)

刪除后，調(diào)整平衡

平均時(shí)間復(fù)雜度

搜索：O(logn)咬展；
添加：O(logn)泽裳，僅需O(1)次旋轉(zhuǎn)操作;
刪除：O(logn)，最多需要O(logn)次旋轉(zhuǎn)操作破婆；

6. 紅黑樹

紅黑樹

紅黑樹也是一種自平衡的二叉搜索樹涮总，紅黑樹的5個(gè)特性：

節(jié)點(diǎn)是 Red 或者 Black；
根節(jié)點(diǎn)是 Black祷舀；
葉子節(jié)點(diǎn)（外部節(jié)點(diǎn)瀑梗、空節(jié)點(diǎn)）為 Black；
Red 的子節(jié)點(diǎn)都是 Black節(jié)點(diǎn)（即在所有路徑上裳扯，不可能包含連續(xù)2個(gè)為 Red 的節(jié)點(diǎn)）抛丽；
任意節(jié)點(diǎn) 到 葉子節(jié)點(diǎn)的所有路徑上包含相同數(shù)量的 Black 節(jié)點(diǎn)；

紅黑樹和 4階B樹具有等價(jià)轉(zhuǎn)化饰豺。

Black 節(jié)點(diǎn)與它的 Red 子節(jié)點(diǎn)融合形成B樹的一個(gè)節(jié)點(diǎn)亿鲜；
紅黑樹的 Black 節(jié)點(diǎn)個(gè)數(shù) 與 4階B樹的節(jié)點(diǎn)總數(shù)相等；

1）添加節(jié)點(diǎn)：

parent : 父節(jié)點(diǎn)
sibling : 兄弟節(jié)點(diǎn)
uncle : 叔父節(jié)點(diǎn)（parent節(jié)點(diǎn)的兄弟節(jié)點(diǎn)）
grand : 祖父節(jié)點(diǎn) （parent節(jié)點(diǎn)的父節(jié)點(diǎn)）
新添加的節(jié)點(diǎn)必須添加到葉子節(jié)點(diǎn)中冤吨，建議新添加的為 Red 節(jié)點(diǎn)蒿柳，這樣可以盡可能滿足紅黑樹性質(zhì)，即滿足性質(zhì)1漩蟆，2垒探，3，5爆安，性質(zhì)4不一定滿足叛复。

如果添加的是根節(jié)點(diǎn)，那么直接染成 Black扔仓；
如果 parent 節(jié)點(diǎn)是 Black，那么添加的 Red 節(jié)點(diǎn)不需要做任何處理咖耘，就已經(jīng)符合紅黑樹的全部性質(zhì)翘簇；

88節(jié)點(diǎn)的添加
如果 parent 節(jié)點(diǎn)是 Red，就會出現(xiàn)連續(xù)兩個(gè) Red儿倒，不符合性質(zhì)4版保，需要進(jìn)行處理呜笑；
a. 如果 uncle 節(jié)點(diǎn)不是 Red，將會導(dǎo)致節(jié)點(diǎn)上溢彻犁；
b. 如果 uncle 節(jié)點(diǎn)不是 Red叫胁，添加節(jié)點(diǎn)的位置 LL \ RR；
1）將 parent 染成 Black汞幢，將 grand 染成 Red驼鹅；
2）對 grand 進(jìn)行單旋轉(zhuǎn)操作；

uncle節(jié)點(diǎn)不是red森篷，LL\RR情況

c. 如果 uncle 節(jié)點(diǎn)不是 Red, 添加節(jié)點(diǎn)的位置 LR \ RL输钩；
1）將自己染成 Black，將 grand 染成 Red仲智；
2）進(jìn)行 LR\RL 雙旋轉(zhuǎn)买乃；

uncle節(jié)點(diǎn)不是red，LR\RL情況

d. 如果 uncle 節(jié)點(diǎn)是 Red钓辆；
1）將 parent剪验，uncle 染成Black；
2）將 grand 染成 Red前联，向上合并碉咆，即當(dāng)作新的節(jié)點(diǎn)進(jìn)行處理；

uncle節(jié)點(diǎn)是red蛀恩，將parent疫铜、uncle染成black，grand染成red双谆，向上合并當(dāng)作新節(jié)點(diǎn)添加

2）刪除節(jié)點(diǎn)：

由于刪除節(jié)點(diǎn)時(shí)壳咕，我們會使用B樹的前驅(qū)或后繼節(jié)點(diǎn)來替換該節(jié)點(diǎn)，實(shí)際上刪除都是葉子節(jié)點(diǎn)

刪除的是 Red 節(jié)點(diǎn)顽馋，不需要任何處理谓厘；
不可能直接刪除擁有2個(gè)Red 子節(jié)點(diǎn)的 Black 節(jié)點(diǎn)，因?yàn)檫@個(gè)節(jié)點(diǎn)會找到前驅(qū)或后繼節(jié)點(diǎn)來替換寸谜，所以不考慮竟稳；
所以只需要考慮，刪除的是擁有 1個(gè)Red 子節(jié)點(diǎn)的 Black 節(jié)點(diǎn) 或者 Black的葉子節(jié)點(diǎn):
刪除的是擁有 1個(gè)Red 子節(jié)點(diǎn)的 Black 節(jié)點(diǎn)：
a. 用 Red子節(jié)點(diǎn)替代 parent節(jié)點(diǎn)熊痴；
b. 將替代的Red 子節(jié)點(diǎn)染成 Black他爸，既可以修復(fù)紅黑樹性質(zhì)；
刪除Black的葉子節(jié)點(diǎn)果善，并且sibling為Black诊笤；
a. 如果sibling最少有一個(gè)Red 子節(jié)點(diǎn)：
1）根據(jù)情況，進(jìn)行之前的LL巾陕、RR讨跟、LR纪他、RL旋轉(zhuǎn)
2）旋轉(zhuǎn)后，中心點(diǎn)（該子樹的根節(jié)點(diǎn)）繼承parent的顏色晾匠；
3）旋轉(zhuǎn)后茶袒，將左右子節(jié)點(diǎn)染成 Black；

刪除Black的葉子節(jié)點(diǎn)凉馆，并且sibling為Black（80）

b. sibling沒有一個(gè)Red 子節(jié)點(diǎn)：
1）將sibling 染成 Red, parent 染成 Black薪寓，就可以修復(fù)紅黑樹性質(zhì)；

刪除Black的葉子節(jié)點(diǎn)句喜，sibling沒有一個(gè)**Red** 子節(jié)點(diǎn)

刪除Black的葉子節(jié)點(diǎn)预愤，并且sibling為 Red；
a. 先將sibling染成 Black咳胃，parent 染成 Red植康，在進(jìn)行旋轉(zhuǎn)操作；
b. 回到sibling 是 Black的情況展懈，再進(jìn)行刪除操作销睁；

刪除**Black**的葉子節(jié)點(diǎn)，并且sibling為 **Red**

3）紅黑樹的平均時(shí)間復(fù)雜度：

搜索：O(logn)存崖；
添加：O(logn)冻记，O(1)次旋轉(zhuǎn)；
刪除：O(logn)来惧，O(1)次旋轉(zhuǎn)冗栗；

4） AVL 與紅黑樹對比：

AVL 標(biāo)準(zhǔn)比較嚴(yán)格，平衡因子不能超過1供搀；
AVL的樹高度比紅黑樹高度低隅居；
AVL搜索，添加葛虐，刪除的時(shí)間復(fù)雜度都是O(logn)胎源，添加僅需O(1)次旋轉(zhuǎn)調(diào)整，刪除最多需要O(logn)次旋轉(zhuǎn)操作屿脐；
紅黑樹的搜索涕蚤，添加，刪除操作時(shí)間復(fù)雜度都是O(logn)的诵，添加和刪除僅需O(1)次旋轉(zhuǎn)調(diào)整万栅；
搜索的次數(shù)遠(yuǎn)遠(yuǎn)大于添加，刪除時(shí)奢驯，優(yōu)先選擇AVL（高度比較低）申钩，否則選擇紅黑樹，總體上紅黑樹的性能比 AVL高瘪阁；

繪圖工具： BinaryTreeGraph撒遣；