最近在閑看博客時(shí)看到一篇專(zhuān)門(mén)寫(xiě)紅黑樹(shù)的實(shí)現(xiàn)原理，以Java的TreeMap為例講解，寫(xiě)的很不錯(cuò)艳馒，仔細(xì)看下來(lái)發(fā)現(xiàn)很多地方不是很理解，畢竟沒(méi)有對(duì)樹(shù)的理解并沒(méi)有很深畸陡，所以決定一步一步的將與樹(shù)相關(guān)的擴(kuò)展實(shí)現(xiàn)都了解一遍鹰溜，沿著下面的學(xué)習(xí)路線開(kāi)始虽填，大家也可以參考以下。

• 樹(shù)的基本知識(shí)
• 二叉樹(shù)的知識(shí)
• 二叉查找樹(shù)
• 平衡二叉樹(shù)
• 紅黑樹(shù)
• B樹(shù)曹动，B-樹(shù)斋日，B+樹(shù)

附上上面的將紅黑樹(shù)的blog：史上最清晰的紅黑樹(shù)講解

樹(shù)的基本概念

樹(shù)Tree是n（n≥0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹(shù)中：（1）有且僅有一個(gè)特定的被稱(chēng)為根root的結(jié)點(diǎn)墓陈；（2）當(dāng)n>1時(shí)恶守，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限集T1，T2贡必，…兔港，Tm，其中每一個(gè)集合本身又是一棵樹(shù)仔拟，并且稱(chēng)為根的子樹(shù)SubTree衫樊。

1. 結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱(chēng)為結(jié)點(diǎn)的度（Degree）。度為0的結(jié)點(diǎn)稱(chēng)為葉子（Leaf）或終端結(jié)點(diǎn)利花。度不為0的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)科侈。
2. 樹(shù)的度是樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值。
3. 結(jié)點(diǎn)的子樹(shù)的根稱(chēng)為該結(jié)點(diǎn)的孩子（Child）炒事，相應(yīng)地臀栈，該結(jié)點(diǎn)稱(chēng)為孩子的雙親（Parent）。
4. 結(jié)點(diǎn)的層次（Level）是從根結(jié)點(diǎn)開(kāi)始計(jì)算起挠乳，根為第一層权薯，根的孩子為第二層，依次類(lèi)推睡扬。樹(shù)中結(jié)點(diǎn)的最大層次稱(chēng)為樹(shù)的深度（Depth）或高度盟蚣。
5. 如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左至右是有次序的（即不能互換），則稱(chēng)該樹(shù)為有序樹(shù)威蕉，否則稱(chēng)為無(wú)序樹(shù)刁俭。

二叉樹(shù)的基本概念

二叉樹(shù)（Binary Tree）的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多具有兩棵子樹(shù)（即在二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)），并且子樹(shù)之間有左右之分韧涨。

二叉樹(shù)的性質(zhì)：

1. 在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）牍戚。

2. 深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（k≥1）。

3. 對(duì)任何一棵二叉樹(shù)虑粥，如果其終端結(jié)點(diǎn)數(shù)為n0如孝，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1娩贷。

4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為不大于log2n的最大整數(shù)加1第晰。

5. 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)（從第1層到最后一層，每層從左到右），則對(duì)任一結(jié)點(diǎn)i（1≤i≤n）,有

   a茁瘦、如果i=1,則結(jié)點(diǎn)i是二叉樹(shù)的根品抽，無(wú)雙親；如果i>1甜熔，則其雙親是結(jié)點(diǎn)x（其中x是不大于i/2的最大整數(shù)）圆恤。

   b、如果2i>n腔稀，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）盆昙；否則其左孩子是結(jié)點(diǎn)2i。

   c焊虏、如果2i+1>n淡喜，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子是結(jié)點(diǎn)2i+1诵闭。

二叉查找樹(shù)

二叉查找樹(shù)（BinarySearch Tree炼团，也叫二叉搜索樹(shù)，或稱(chēng)二叉排序樹(shù)Binary Sort Tree）或者是一棵空樹(shù)涂圆，或者是具有下列性質(zhì)的二叉樹(shù)：

1. 若它的左子樹(shù)不為空们镜，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
2. 若它的右子樹(shù)不為空润歉，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
3. 它的左颈抚、右子樹(shù)也分別為二叉查找樹(shù)踩衩。

結(jié)點(diǎn)定義：

public class TreeNode<T> {

    /**
     * 結(jié)點(diǎn)的值
     */
    private T value;

    /**
     * 左結(jié)點(diǎn)
     */
    private TreeNode<T> left;
    
    /**
     * 右結(jié)點(diǎn)
     */
    private TreeNode<T> right;
    
    /**
     * 父親結(jié)點(diǎn)
     */
    private TreeNode<T> parent;

    /**
     * 頻率
     */
    private int freq;

}

插入

根據(jù)二叉查找樹(shù)的性質(zhì)，插入一個(gè)節(jié)點(diǎn)的時(shí)候贩汉，如果根節(jié)點(diǎn)為空驱富，就此節(jié)點(diǎn)作為根節(jié)點(diǎn)，如果根節(jié)點(diǎn)不為空匹舞，就要先和根節(jié)點(diǎn)比較褐鸥，如果比根節(jié)點(diǎn)的值小，就插入到根節(jié)點(diǎn)的左子樹(shù)中赐稽，如果比根節(jié)點(diǎn)的值大就插入到根節(jié)點(diǎn)的右子樹(shù)中叫榕，如此遞歸下去，找到插入的位置姊舵。重復(fù)節(jié)點(diǎn)的插入用值域中的freq標(biāo)記晰绎。如圖2是一個(gè)插入的過(guò)程。

插入過(guò)程圖1

二叉查找樹(shù)的時(shí)間復(fù)雜度要看這棵樹(shù)的形態(tài)括丁，如果比較接近一一棵完全二叉樹(shù)荞下，那么時(shí)間復(fù)雜度在O(logn)左右，如果遇到如圖3這樣的二叉樹(shù)的話(huà)，那么時(shí)間復(fù)雜度就會(huì)恢復(fù)到線性的O(n)了尖昏。

插入過(guò)程圖2

平衡二叉樹(shù)會(huì)很好的解決如圖3這種情況仰税。

核心代碼如下：

private boolean insert(SearchNode<T> curr, SearchNode<T> insertNode, SearchNode<T> parent, boolean currIsLeft) {
    if (curr == null) {
        curr = insertNode;
        if (currIsLeft) {
            parent.setLeft(curr);
        } else {
            parent.setRight(curr);
        }
    } else {
        int result = curr.getValue().compareTo(insertNode.getValue());
        // 如果當(dāng)前值大于插入的值
        if (result > 0) {
            return insert((SearchNode<T>)curr.getLeft(), insertNode, curr, true);
        } else if (result < 0) {
            return insert((SearchNode<T>)curr.getRight(), insertNode, curr, false);
        }else {
            curr.freq++;
        }
    }
    return true;
}

查找

在二叉查找樹(shù)中查找x的過(guò)程如下：

1. 若二叉樹(shù)是空樹(shù)，則查找失敗抽诉。
2. 若x等于根結(jié)點(diǎn)的數(shù)據(jù)陨簇，則查找成功，否則掸鹅。
3. 若x小于根結(jié)點(diǎn)的數(shù)據(jù)塞帐，則遞歸查找其左子樹(shù)，否則巍沙。
4. 遞歸查找其右子樹(shù)葵姥。

核心代碼如下：

protected TreeNode<T> find0(TreeNode<T> node, T value) {
    if (node == null) {
        return null;
    }
    int result = node.getValue().compareTo(value);
    if (result > 0) {
        return find0(node.getLeft(), value);
    } else if (result < 0) {
        return find0(node.getRight(), value);
    }
    return node;
}

刪除

刪除會(huì)麻煩一點(diǎn)，如果是葉子節(jié)點(diǎn)的話(huà)句携，直接刪除就可以了榔幸。如果只有一個(gè)孩子的話(huà)，就讓它的父親指向它的兒子矮嫉，然后刪除這個(gè)節(jié)點(diǎn)削咆。圖4顯示了一棵初始樹(shù)和4節(jié)點(diǎn)被刪除后的結(jié)果。先用一個(gè)臨時(shí)指針指向4節(jié)點(diǎn)蠢笋，再讓4節(jié)點(diǎn)的地址指向它的孩子拨齐，這個(gè)時(shí)候2節(jié)點(diǎn)的右兒子就變成了3節(jié)點(diǎn)，最后刪除臨時(shí)節(jié)點(diǎn)指向的空間昨寞，也就是4節(jié)點(diǎn)瞻惋。

刪除過(guò)程圖1

刪除有兩個(gè)兒子的節(jié)點(diǎn)會(huì)比較復(fù)雜一些。一般的刪除策略是用其右子樹(shù)最小的數(shù)據(jù)代替該節(jié)點(diǎn)的數(shù)據(jù)并遞歸的刪除掉右子樹(shù)中最小數(shù)據(jù)的節(jié)點(diǎn)援岩。因?yàn)橛易訕?shù)中數(shù)據(jù)最小的節(jié)點(diǎn)肯定沒(méi)有左兒子歼狼，所以刪除的時(shí)候容易一些。圖5顯示了一棵初始樹(shù)和2節(jié)點(diǎn)被刪除后的結(jié)果享怀。首先在2節(jié)點(diǎn)的右子樹(shù)中找到最小的節(jié)點(diǎn)3羽峰，然后把3的數(shù)據(jù)賦值給2節(jié)點(diǎn)，這個(gè)時(shí)候2節(jié)點(diǎn)的數(shù)據(jù)變?yōu)?添瓷，然后的工作就是刪除右子樹(shù)中的3節(jié)點(diǎn)了梅屉，采用遞歸刪除。

刪除過(guò)程圖2

我們發(fā)現(xiàn)對(duì)2節(jié)點(diǎn)右子樹(shù)的查找進(jìn)行了兩遍仰坦，第一遍找到最小節(jié)點(diǎn)并賦值履植，第二遍刪除這個(gè)最小的節(jié)點(diǎn)，這樣的效率并不是很高悄晃。你能不能寫(xiě)出只查找一次就可以實(shí)現(xiàn)賦值和刪除兩個(gè)功能的函數(shù)呢玫霎？

如果刪除的次數(shù)不是很多的話(huà)凿滤，有一種刪除的方法會(huì)比較快一點(diǎn)，名字叫懶惰刪除法：當(dāng)一個(gè)元素要被刪除時(shí)庶近，它仍留在樹(shù)中翁脆，只是多了一個(gè)刪除的標(biāo)記。這種方法的優(yōu)點(diǎn)是刪除那一步的時(shí)間開(kāi)銷(xiāo)就可以避免了鼻种，如果重新插入刪除的節(jié)點(diǎn)的話(huà)反番，插入時(shí)也避免了分配空間的時(shí)間開(kāi)銷(xiāo)。缺點(diǎn)是樹(shù)的深度會(huì)增加叉钥，查找的時(shí)間復(fù)雜度會(huì)增加罢缸，插入的時(shí)間可能會(huì)增加。

核心代碼如下：

protected void deleteNode(TreeNode<T> deleteNodeParent, TreeNode<T> deleteNode) {
    if (deleteNodeParent == null) {
        // 左右子樹(shù)都為空
        if (deleteNode.getLeft() == null && deleteNode.getRight() == null) {
            root = null;
        } else if (deleteNode.getLeft() == null || deleteNode.getRight() == null) {
            // 存在左子樹(shù)或右子樹(shù)
            if (deleteNode.getLeft() != null) {
                root = deleteNode.getLeft();
            } else {
                root = deleteNode.getRight();
            }
        } else {
            // 左右子樹(shù)都不為空
            TreeNode<T> temp = deleteNode;
            TreeNode<T> rightLeft = deleteNode.getRight();
            while (rightLeft.getLeft() != null) {
                temp = rightLeft;
                rightLeft = rightLeft.getLeft();
            }
            if(temp == deleteNode) {
                deleteNode.setRight(rightLeft.getRight());
            }else {
                temp.setLeft(rightLeft.getRight());
            }
            deleteNode.setValue(rightLeft.getValue());  
        }
    } else {
        // 左右子樹(shù)都為空
        if (deleteNode.getLeft() == null && deleteNode.getRight() == null) {
            // 根結(jié)點(diǎn)
            if (deleteNodeParent.getLeft() == deleteNode) {
                deleteNodeParent.setLeft(null);
            } else {
                deleteNodeParent.setRight(null);
            }
        } else if (deleteNode.getLeft() == null || deleteNode.getRight() == null) {
            // 存在左子樹(shù)或右子樹(shù)
            if (deleteNode.getLeft() != null) {
                if (deleteNodeParent.getLeft() == deleteNode) {
                    // 如果待刪除結(jié)點(diǎn)是左結(jié)點(diǎn)投队，且其存在左結(jié)點(diǎn)
                    deleteNodeParent.setLeft(deleteNode.getLeft());
                } else {
                    // 如果待刪除結(jié)點(diǎn)是左結(jié)點(diǎn)枫疆，且其存在右結(jié)點(diǎn)
                    deleteNodeParent.setRight(deleteNode.getLeft());
                }
            } else {
                if (deleteNodeParent.getRight() == deleteNode) {
                    deleteNodeParent.setRight(deleteNode.getRight());
                } else {
                    deleteNodeParent.setLeft(deleteNode.getRight());
                }
            }
        } else {
            // 左右子樹(shù)都不為空
            TreeNode<T> temp = deleteNode;
            TreeNode<T> rightLeft = deleteNode.getRight();
            while (rightLeft.getLeft() != null) {
                temp = rightLeft;
                rightLeft = rightLeft.getLeft();
            }
            if(temp == deleteNode) {
                deleteNode.setRight(rightLeft.getRight());
            }else {
                temp.setLeft(rightLeft.getRight());
            }
            deleteNode.setValue(rightLeft.getValue());  
        }
    }

}

具體實(shí)現(xiàn)代碼請(qǐng)查看：https://github.com/mastery001/study/blob/master/study-datastruct/src/main/java/tree/search/BinarySearchTree.java

參考資料：

• 二叉查找樹(shù)--查找、刪除敷鸦、插入（Java實(shí)現(xiàn)）
• 一步一步寫(xiě)二叉查找樹(shù)