紅黑樹從結構到源碼

1、二叉查找樹(Binary Search Tree)

二叉查找樹具有的特性：

1. 左子樹上所有結點的值均小於或等於它的根結點的值。
2. 右子樹上所有結點的值均大於或等於它的根結點的值。
3. 左、右子樹也分別為二叉排序樹。

2、紅黑樹

紅黑樹一種自平衡的二叉查找樹。除了具有二叉查找的特性外，還具有的特性：

1. 節點是紅色或黑色。
2. 根節點是黑色。
3. 每個葉子節點都是黑色的空節點（NIL節點）。
4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

3、HashMap中紅黑樹源碼分析

JDK 1.8對HashMap進行了比較大的優化，底層實現由之前的“數組+鏈表”改為“數組+鏈表+紅黑樹”

TreeNode中的方法介紹

<code>    // 紅黑樹兩個節點之間的父節點TreeNode parent;  // red-black tree links    // 紅黑樹左節點    TreeNode left;    // 紅黑樹右節點    TreeNode right;    // 前驅節點，在刪除的時候需要解除綁定關聯的元素，個人理解是功能作用類似於鏈表裡面的 next，在刪除某個節點的時候，上一個節點的 next 屬性需要解綁，    // 有時候也把 parent = pre， 作用應該一樣，都是子節點對應上來父節點的關係    TreeNode prev;    // needed to unlink next upon deletion    // 當前節點是否標紅    boolean red;    // 調用父類初始化方法    TreeNode(int hash, K key, V val, Node next) { }    // 查找出整棵樹的根節點    final TreeNode root() { }    // 把根節點移到最前，確保根節點就是桶的第一個元素    static  void moveRootToFront(Node[] tab, TreeNode root) { }    /**     ** 從根節點開始遍歷查找     * @param h 要查找的節點的 hash 值     * @param k 要查找的節點的 key 值     * @param kc 比較器的類型，用來和 Key 的類型做比較，一般在 put 的時候用到，對比 key 是否相同，然後再做後續處理     * @return     */    final TreeNode find(int h, Object k, Class> kc) { }    // 從根節點開始查找    final TreeNode getTreeNode(int h, Object k) { }    // 當遇到兩個對象的 hash 值（在這裡基本上是指 key）無法比較時，會使用兩個對象的引用來比較，在插入元素以及樹化的時候會用到    // HashMap 中的解釋是，即使遇到相同的 hash 值，不需要完全保證樹的有序性，大家使用的插入規則一樣就可以使得整棵樹平衡了    static int tieBreakOrder(Object a, Object b) { }    // 由鏈表樹化成紅黑樹    final void treeify(Node 
[] tab) { }    // 由紅黑樹退化成鏈表    final Node untreeify(HashMap map) { }    // 如果桶中的元素是紅黑樹的話，就需要用這個方法來添加元素了    final TreeNode putTreeVal(HashMap map, Node[] tab, int h, K k, V v) {  }    // 移除節點    final void removeTreeNode(HashMap map, Node[] tab, boolean movable) {  }    // 會對桶中的元素重新排列（也稱作樹的修剪），樹化的過程以及退化成鏈表的過程都從這裡開始    final void split(HashMap map, Node[] tab, int index, int bit) { }    /* ------------------------------------------------------------ */    // Red-black tree methods, all adapted from CLR    // 紅黑樹左旋轉    static  TreeNode rotateLeft(TreeNode root, TreeNode p) { }    // 紅黑樹右旋轉    static  TreeNode rotateRight(TreeNode root, TreeNode p) { }    // 紅黑樹的數據插入方法，這裡面需要用到上面的左旋和右旋操作，主要是為了維持紅黑樹的結構，插入時需要對樹的結構重新調整    // 保證插入後平衡，共5種插入情況    static  TreeNode balanceInsertion(TreeNode root, TreeNode x) { }    // 和插入的方法一樣，平衡刪除的操作在刪除節點時同樣需要對樹的結構重新調整以維持紅黑樹的結構    // 刪除後調整平衡 ，共6種刪除情況    static  TreeNode balanceDeletion(TreeNode root, TreeNode x) { }    /**     * Recursive invariant check     */    // 在對樹進行處理的時候, 遞歸檢查要插入的節點是否符合紅黑樹的規則    // 檢測是否符合紅黑樹    static  
 boolean checkInvariants(TreeNode t) {}}/<code>

紅黑樹和B+的區別

紅黑樹 和 b+樹的用途有什麼區別？

• 紅黑樹多用在內部排序，即全放在內存中的，STL的map和set的內部實現就是紅黑樹。
• B+樹多用於外存上時，B+也被成為一個磁盤友好的數據結構。

閱讀更多 陳小亮 的文章

關鍵字: Node 鏈表 static