97人妻爽爽,情色在线视频,Yellow啪啪啪。

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;
對(duì)于任何一顆非空二叉樹，如果葉子節(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)只會(huì)出現(xiàn)在最后兩層，而且最后一層的葉子節(jié)點(diǎn)都是向左對(duì)齊的。完全二叉樹從根節(jié)點(diǎn)到倒數(shù)第二層都是滿二叉樹。完全二叉樹的特效如下：

度為1 的節(jié)點(diǎn)只有左節(jié)點(diǎn)。且度為1的節(jié)點(diǎn)數(shù)只有1個(gè)或0個(gè)；
同樣的節(jié)點(diǎn)數(shù)的二叉樹，完全二叉樹的高度最?。?/li>
假設(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開始，對(duì)于任意的第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;
        // 存儲(chǔ)著每一層的元素?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, 如果是 自定義的對(duì)象 必須指明比較方式；
二叉搜索樹的搜索、刪除、添加最壞時(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á)到一顆適度平衡的二叉搜索樹，稱為平衡二叉樹。

平衡二叉樹 英文簡(jiǎn)稱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í)（只會(huì)在葉子節(jié)點(diǎn)添加），可能會(huì)導(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)致的失衡以及解決辦法：

可能會(huì)導(dǎo)致 父節(jié)點(diǎn) 或 祖先節(jié)點(diǎn) 失衡（只有1個(gè)節(jié)點(diǎn)失衡），其他節(jié)點(diǎn)不會(huì)導(dǎo)致失衡。恢復(fù)平衡后，可能會(huì)導(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，就會(huì)出現(xiàn)連續(xù)兩個(gè) Red，不符合性質(zhì)4，需要進(jìn)行處理；
a. 如果 uncle 節(jié)點(diǎn)不是 Red，將會(huì)導(dǎo)致節(jié)點(diǎn)上溢；
b. 如果 uncle 節(jié)點(diǎn)不是 Red，添加節(jié)點(diǎn)的位置 LL \ RR；
1）將 parent 染成 Black，將 grand 染成 Red；
2）對(duì) 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í)，我們會(huì)使用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)會(huì)找到前驅(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 與紅黑樹對(duì)比：

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；

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

平衡二叉搜索樹

平衡二叉搜索樹

1. 樹的概念

2. 二叉樹的遍歷

3. 二叉搜索樹

4. 平橫二叉搜索樹

5. AVL

6. 紅黑樹

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

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

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

4） AVL 與紅黑樹對(duì)比：

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

平衡二叉搜索樹

1. 樹的概念

2. 二叉樹的遍歷

3. 二叉搜索樹

4. 平橫二叉搜索樹

5. AVL

6. 紅黑樹

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

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

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

4） AVL 與 紅黑樹對(duì)比：

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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

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

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

4） AVL 與紅黑樹對(duì)比：