日日操夜夜添-日日操影院-日日草夜夜操-日日干干-精品一区二区三区波多野结衣-精品一区二区三区高清免费不卡

作者：小傅哥
博客：https://bugstack.cn

沉淀、分享、成長，讓自己和他人都能有所收獲！

一、前言：掛在樹上！

不知道你經(jīng)歷過HashMap的奪命連環(huán)問！

為啥，面試官那么喜歡讓你聊聊 HashMap？因?yàn)?HashMap 涉及的東西廣，用到的數(shù)據(jù)結(jié)構(gòu)多，問題延展性好，一個(gè) HashMap 就能聊下來80%的數(shù)據(jù)結(jié)構(gòu)了。而且面試 HashMap 能通過你對(duì)紅黑樹的了解定位出你哪個(gè)級(jí)別的研發(fā)人員。

而紅黑樹的知識(shí)點(diǎn)可以說是非常龐大，在學(xué)習(xí)紅黑樹時(shí)也不能一下就能掌握，甚至很程序員壓根就沒搞明白紅黑樹，只是背下來它的幾條限定規(guī)則而已。

其實(shí)一開始我也是這樣！ 不過總感覺這塊的知識(shí)點(diǎn)不搞個(gè)明明白白，就鬧心。因?yàn)椴豢赡芤粋€(gè)理科的東西，是需要死記硬背搞下來的。所以在翻閱資料、文檔、歷史、典籍，找到紅黑樹的演化過程，它是從2-3樹演變而來，而2-3樹、AVL樹，這類B-樹，也就是 BalancedTree 平衡樹。它們都是為了解決 BST 二叉搜索樹不自平衡而來的產(chǎn)物。

那么現(xiàn)在清楚了，要想搞定紅黑樹，讓懂了就是真的懂，就需要把前面這些知識(shí)搞定，并且除了理論還能用落地的案例代碼編寫出來，才是悟透。好，那么接下來，小傅哥就帶著你一起搞定這點(diǎn)事

二、BST 樹

Binary Search Tree歷史

二叉搜索樹算法是由包括 PF Windley、Andrew Donald Booth、Andrew Colin、Thomas N. Hibbard 在內(nèi)的幾位研究人員獨(dú)立發(fā)現(xiàn)的。該算法歸功于 Conway Berners-Lee 和 David Wheeler ，他們?cè)?1960 年使用它在磁帶中存儲(chǔ)標(biāo)記數(shù)據(jù)。 最早和流行的二叉搜索樹算法之一是 Hibbard 算法。

1. 二叉搜索樹數(shù)據(jù)結(jié)構(gòu)

二叉搜索樹（Binary Search Tree），也稱二叉查找樹。如果你看見有序二叉樹（Ordered Binary tree）、排序二叉樹（Sorted Binary Tree）那么說的都是一個(gè)東西。

 

 

• 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；
• 若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
• 任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹；

 

二叉搜索樹在日常開發(fā)中使用的場(chǎng)景還是比較多的，例如基于組合模式實(shí)現(xiàn)的規(guī)則引擎，它就是一顆二叉搜索樹。但類似這樣的開發(fā)中用到的二叉樹場(chǎng)景，都是基于配置生成，所以組合出來的節(jié)點(diǎn)也更加方便控制樹高和平衡性。這與 JAVA API HashMap 中的紅黑樹這樣為了解決插入節(jié)點(diǎn)后仍保持樹的平衡性是有所不同的。

所以二叉搜索樹也是一顆沒有經(jīng)過調(diào)衡的基礎(chǔ)性數(shù)據(jù)結(jié)構(gòu)，在一定概率上它完成有可能退化成鏈表，也就是從近似O(logn)的時(shí)間復(fù)雜度退化到O(n)。關(guān)于二叉搜索樹的平衡解決方案，包括；AVL樹、2-3樹、紅黑樹等，小傅哥會(huì)在后續(xù)的章節(jié)繼續(xù)實(shí)現(xiàn)。

2. 二叉搜索樹結(jié)構(gòu)實(shí)現(xiàn)

二叉搜索樹是整個(gè)樹結(jié)構(gòu)中最基本的樹，同時(shí)也是樹這個(gè)體系中實(shí)現(xiàn)起來最容易的數(shù)據(jù)結(jié)構(gòu)。但之所以要使用基于二叉搜索樹之上的其他樹結(jié)構(gòu)，主要是因?yàn)槭褂脭?shù)據(jù)結(jié)構(gòu)就是對(duì)數(shù)據(jù)的存放和讀取。那么為了提高吞吐效率，則需要盡可能的平衡元素的排序，體現(xiàn)在樹上則需要進(jìn)行一些列操作，所以會(huì)有不同的結(jié)構(gòu)樹實(shí)現(xiàn)。

而實(shí)現(xiàn)二叉搜索樹是最好的基礎(chǔ)學(xué)習(xí)，了解基本的數(shù)據(jù)結(jié)構(gòu)后才更容易擴(kuò)展學(xué)習(xí)其他樹結(jié)構(gòu)。

• 源碼地址：https://github.com/fuzhengwei/java-algorithms
• 本章源碼：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree

2.1 樹枝定義 public Integer value; public Node parent; public Node left; public Node right;

• 用于組成一顆樹的節(jié)點(diǎn)，則需要包括；值和與之關(guān)聯(lián)的三角結(jié)構(gòu)，一個(gè)父節(jié)點(diǎn)、兩個(gè)孩子節(jié)點(diǎn)。如果是AVL樹還需要樹高，紅黑樹還需要染色標(biāo)記。

2.2 插入節(jié)點(diǎn) public Node insert(int e) { if (null == root) { root = new Node(e, null, null, null); size++; return root; } // 索引出待插入元素位置，也就是插入到哪個(gè)父元素下 node parent = root; Node search = root; while (search != null && search.value != null) { parent = search; if (e < search.value) { search = search.left; } else { search = search.right; } } // 插入元素 Node newNode = new Node(e, parent, null, null); if (parent.value > newNode.value) { parent.left = newNode; } else { parent.right = newNode; } size++; return newNode; }

• 首先判斷插入元素時(shí)候是否有樹根，沒有則會(huì)把當(dāng)前節(jié)點(diǎn)創(chuàng)建出一顆樹根來。
• 如果當(dāng)前樹是有樹根的，則對(duì)插入元素與當(dāng)前樹進(jìn)行一個(gè)節(jié)點(diǎn)遍歷操作，找到元素可以插入的索引位置 parent（掛到這個(gè)父節(jié)點(diǎn)下）。也就是 search 搜索過程。
• 最后就是插入元素，通過給插入值創(chuàng)建一個(gè) Node 節(jié)點(diǎn)，并綁定它的父元素，以及把新元素掛到索引到的 parent 節(jié)點(diǎn)下。

2.3 索引節(jié)點(diǎn) public Node search(int e) { Node node = root; while (node != null && node.value != null && node.value != e) { if (e < node.value) { node = node.left; } else { node = node.right; } } return node; }

• 值查找的過程，就是對(duì)二叉搜索樹的遍歷，不斷的循環(huán)節(jié)點(diǎn)，按照節(jié)點(diǎn)值的左右匹配，找出最終相當(dāng)?shù)闹倒?jié)點(diǎn)。

2.4 刪除節(jié)點(diǎn) public Node delete(int e) { Node delNode = search(e); if (null == delNode) return null; return delete(delNode); } private Node delete(Node delNode) { if (delNode == null) return null; Node result = null; if (delNode.left == null) { result = transplant(delNode, delNode.right); } else if (delNode.right == null) { result = transplant(delNode, delNode.left); } else { // 因?yàn)閯h除的節(jié)點(diǎn)，有2個(gè)孩子節(jié)點(diǎn)，這個(gè)時(shí)候找到這條分支下，最左側(cè)做小的節(jié)點(diǎn)。用它來替換刪除的節(jié)點(diǎn) Node miniNode = getMiniNode(delNode.right); if (miniNode.parent != delNode) { // 交換位置，用miniNode右節(jié)點(diǎn)，替換miniNode transplant(miniNode, miniNode.right); // 把miniNode 提升父節(jié)點(diǎn)，設(shè)置右子樹并進(jìn)行掛鏈。替代待刪節(jié)點(diǎn) miniNode.right = delNode.right; miniNode.right.parent = miniNode; } // 交換位置，刪除節(jié)點(diǎn)和miniNode 可打印測(cè)試觀察；System.out.println(this); transplant(delNode, miniNode); // 把miniNode 提升到父節(jié)點(diǎn)，設(shè)置左子樹并掛鏈 miniNode.left = delNode.left; miniNode.left.parent = miniNode; result = miniNode; } size--; return result; } private Node getMinimum(Node node) { while (node.left != null) { node = node.left; } return node; } private Node transplant(Node delNode, Node addNode) { if (delNode.parent == null) { this.root = addNode; } // 判斷刪除元素是左/右節(jié)點(diǎn) else if (delNode.parent.left == delNode) { delNode.parent.left = addNode; } else { delNode.parent.right = addNode; } // 設(shè)置父節(jié)點(diǎn) if (null != addNode) { addNode.parent = delNode.parent; } return addNode; } 2.4.1 刪除單節(jié)點(diǎn)

 

 

 

• 待刪除節(jié)點(diǎn)14，判斷此節(jié)點(diǎn)的父節(jié)點(diǎn)的孩子節(jié)點(diǎn)，哪個(gè)等于14，找出左右
• 把待刪節(jié)點(diǎn)的右孩子節(jié)點(diǎn)，掛到刪除節(jié)點(diǎn)的右節(jié)點(diǎn)
• 給待刪節(jié)點(diǎn)的右孩子節(jié)點(diǎn)，設(shè)置上父節(jié)點(diǎn)

2.4.2 刪除雙節(jié)點(diǎn)

 

 

 

• 待刪除節(jié)點(diǎn)64，含有雙子節(jié)點(diǎn)，則需要根據(jù)第一個(gè)右子節(jié)點(diǎn)查找最小左子節(jié)點(diǎn)。從89到72，如果有比72還小的左子節(jié)點(diǎn)，繼續(xù)排查。
• 排查到節(jié)點(diǎn)72，將72這個(gè)準(zhǔn)備替換待刪元素的節(jié)點(diǎn)，與右子節(jié)點(diǎn)73進(jìn)行位置交換，過程與 4.1 相同。使用交換函數(shù) transplant
• 最后是進(jìn)行節(jié)點(diǎn)72與待刪節(jié)點(diǎn)64的交換過程，更換三角關(guān)系，父節(jié)點(diǎn)、左子節(jié)點(diǎn)、右子節(jié)點(diǎn)。

3. 二叉搜索樹功能測(cè)試

 

為了方便觀察樹結(jié)構(gòu)的變化，這里小傅哥找了一些資料資料，一種是我們可以通過程序來打印（類似大家之前打印99乘法表，另外是使用線上的可視化圖：https://visualgo.NET/zh/bst?slide=1）

3.1 隨機(jī)插入元素 @Test public void test_binary_search_tree() { BinarySearchTree tree = new BinarySearchTree(); for (int i = 0; i < 10; i++) { tree.insert(new Random().nextInt(100)); } System.out.println(tree); }

測(cè)試結(jié)果

/----- 91 | ----- 78 /----- 74 | ----- 67 61 | /----- 51 ----- 40 | /----- 28 ----- 14 ----- 7 Process finished with exit code 0

• 因?yàn)槟銣y(cè)試時(shí)的隨機(jī)數(shù)不同，可能會(huì)出現(xiàn)很多不同結(jié)構(gòu)的二叉搜索樹，也可能是一個(gè)類似鏈表結(jié)構(gòu)的退化樹。

3.2 插入并且刪除 @Test public void test_insert_delete(){ BinarySearchTree tree = new BinarySearchTree(); tree.insert(32); tree.insert(7); tree.insert(64); tree.insert(63); tree.insert(89); tree.insert(72); tree.insert(94); tree.insert(6); tree.insert(14); tree.insert(18); tree.insert(73); System.out.println(tree); // 刪除單節(jié)點(diǎn)，只有一個(gè)孩子的父節(jié)點(diǎn) // tree.delete(14); // 刪除雙節(jié)點(diǎn)，擁有二個(gè)孩子的父節(jié)點(diǎn) tree.delete(64); System.out.println(tree); }

 

測(cè)試結(jié)果

/----- 94 /----- 89 | | /----- 73 | ----- 72 /----- 64 | ----- 63 32 | /----- 18 | /----- 14 ----- 7 ----- 6 /----- 94 /----- 89 | ----- 73 /----- 72 | ----- 63 32 | /----- 18 | /----- 14 ----- 7 ----- 6 Process finished with exit code 0

• 這個(gè)案例就是 刪除雙節(jié)點(diǎn) 的案例，刪除了節(jié)點(diǎn)64以后，節(jié)點(diǎn)72被提取上來使用。讀者伙伴也可以嘗試刪除其他節(jié)點(diǎn)測(cè)試驗(yàn)證

三、AVL 樹

 

AVL樹歷史

在計(jì)算機(jī)科學(xué)中，AVL 樹以其兩位蘇聯(lián)發(fā)明家Georgy Adelson-Velsky和 Evgenii Landis的名字命名，他們?cè)?1962 年的論文“信息組織算法”中發(fā)表了它。它是一種自平衡二叉搜索樹(BST)，這是發(fā)明的第一個(gè)這樣的數(shù)據(jù)結(jié)構(gòu)。

1. AVL樹數(shù)據(jù)結(jié)構(gòu)

AVL 自平衡二叉樹的出現(xiàn)，其目的在于解決二叉搜索樹退化成鏈表的問題。當(dāng)我們向BST二叉搜索樹順序存入1、2、3、4、5、6、7個(gè)元素時(shí)，它會(huì)退化成一條鏈表，因而失去樹查詢的時(shí)間復(fù)雜度，所以我們需要AVL樹平衡樹高。如圖所示

 

那么AVL樹是怎么平衡樹高的呢？

當(dāng)二叉樹的左右分支樹高差不為1時(shí)，需要進(jìn)行左旋或者右旋，來調(diào)衡樹高。這有點(diǎn)像開車的時(shí)候，如果車頭偏左就往右打方向盤，車頭偏右就往左打方向盤是一個(gè)道理。那這個(gè)方向盤(左旋、右旋)是怎么打的呢，主要分以下四種情況；

左旋（新增節(jié)點(diǎn)6） 右旋（新增節(jié)點(diǎn)1） 左旋+右旋（新增節(jié)點(diǎn)4） 右旋+左旋（新增節(jié)點(diǎn)3）

 

 

 

 

條件：節(jié)點(diǎn)4，平衡因子為-2，左旋 條件：節(jié)點(diǎn)3，平衡因子為2，右旋 條件：節(jié)點(diǎn)3，平衡因子為2，右旋。但當(dāng)節(jié)點(diǎn)2平衡因子-1先左旋。 條件：節(jié)點(diǎn)2，平衡因子為-2，左旋。但當(dāng)節(jié)點(diǎn)5平衡因子1先右旋。

 

• 節(jié)點(diǎn)樹高：以節(jié)點(diǎn)4為說明，最長的左右分支節(jié)點(diǎn)個(gè)數(shù)，就是節(jié)點(diǎn)4的最大樹高。這里節(jié)點(diǎn)4左右孩子節(jié)點(diǎn)最長路徑都為2，所以它的樹高為2。同理可計(jì)算其他節(jié)點(diǎn)樹高。
• 平衡因子：通過當(dāng)前節(jié)點(diǎn)的左右子節(jié)點(diǎn)作差計(jì)算平衡因子，之后AVL樹通過平衡因子，定義了什么時(shí)候進(jìn)行左旋和右旋。
• 源碼地址：https://github.com/fuzhengwei/java-algorithms
• 本章源碼：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree

2. AVL樹代碼實(shí)現(xiàn)

 

對(duì)于 AVL 樹的實(shí)現(xiàn)與 BST 二叉搜索樹相比，在樹的節(jié)點(diǎn)定義上多了一個(gè)樹高的屬性。也有些AVL樹使用的是平衡因子的屬性，就是通過樹高計(jì)算后的結(jié)果。樹節(jié)點(diǎn)代碼結(jié)構(gòu)如下；

public class Node { public Class clazz; public Integer value; public Node parent; public Node left; public Node right; // AVL 樹所需屬性 public int height; }

接下來小傅哥就分別通過代碼講解下一顆AVL樹的左旋、右旋、左旋+右旋、右旋+左旋的代碼操作。不要擔(dān)心這沒有多復(fù)雜，只要你能搞清楚左旋，就能搞清楚右旋。兩旋弄懂組合就沒啥難度了。

 

• 源碼地址：https://github.com/fuzhengwei/java-algorithms
• 本章源碼：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/stack
• 動(dòng)畫演示：https://visualgo.net/zh/bst?slide=1 —— AVL樹初次理解還是比較困難的，可以結(jié)合學(xué)習(xí)內(nèi)容的同時(shí)做一些動(dòng)畫演示。

2.1 左旋

 

圖解左旋操作；它就是一種摘鏈更換調(diào)整節(jié)點(diǎn)的處理過程，小傅哥把它分解展示，整個(gè)過程如下；

 

代碼實(shí)現(xiàn)

protected Node rotateLeft(Node node) { Node temp = node.right; temp.parent = node.parent; node.right = temp.left; if (node.right != null) { node.right.parent = node; } temp.left = node; node.parent = temp; if (temp.parent == null) { root = temp; } else { if (temp.parent.left == node) { temp.parent.left = temp; } else { temp.parent.right = temp; } } return temp; }

1. 左旋的作用，相當(dāng)于通過向上遷移樹高差大于1的右子節(jié)點(diǎn)來降低樹高的操作。
2. 通過節(jié)點(diǎn)4拿到父節(jié)點(diǎn)2和右子節(jié)點(diǎn)5，把父節(jié)點(diǎn)2和右子節(jié)點(diǎn)5建立關(guān)聯(lián)
3. 節(jié)點(diǎn)5的左子節(jié)點(diǎn)，相當(dāng)于是大于4小于4的那么一個(gè)值，只不過這里不體現(xiàn)。那么這個(gè)節(jié)點(diǎn)4的左子節(jié)點(diǎn)，應(yīng)該被遷移到節(jié)點(diǎn)3的右子節(jié)點(diǎn)上。
4. 整理節(jié)點(diǎn)5的關(guān)系，左子節(jié)點(diǎn)為4。左子節(jié)點(diǎn)4的父節(jié)點(diǎn)為5
5. 如果說遷移上來的節(jié)點(diǎn)5無父節(jié)點(diǎn)，那么它就是父節(jié)點(diǎn) root = temp
6. 遷移上來的節(jié)點(diǎn)5，找到原節(jié)點(diǎn)4是對(duì)應(yīng)父節(jié)點(diǎn)的左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)，對(duì)應(yīng)的設(shè)置節(jié)點(diǎn)5的左右位置

2.2 右旋

 

圖解右旋操作；它就是一種摘鏈更換調(diào)整節(jié)點(diǎn)的處理過程，小傅哥把它分解展示，整個(gè)過程如下；

 

代碼實(shí)現(xiàn)

protected Node rotateRight(Node node) { Node temp = node.left; temp.parent = node.parent; node.left = temp.right; if (node.left != null) { node.left.parent = node; } temp.right = node; node.parent = temp; if (temp.parent == null) { root = temp; } else { if (temp.parent.left == node) { temp.parent.left = temp; } else { temp.parent.right = temp; } } return temp; }

1. 右旋的作用，相當(dāng)于通過向上遷移樹高差大于1的右子節(jié)點(diǎn)來降低樹高的操作。
2. 通過節(jié)點(diǎn)3拿到父節(jié)點(diǎn)4和左子節(jié)點(diǎn)2，把父節(jié)點(diǎn)7和左子節(jié)點(diǎn)2建立關(guān)聯(lián)
3. 節(jié)點(diǎn)2的右子節(jié)點(diǎn)，相當(dāng)于是大于2小于3的那么一個(gè)值，只不過這里不體現(xiàn)。那么這個(gè)節(jié)點(diǎn)2的右子節(jié)點(diǎn)，應(yīng)該被遷移到節(jié)點(diǎn)3的左子節(jié)點(diǎn)上。
4. 整理節(jié)點(diǎn)2的關(guān)系，右子節(jié)點(diǎn)為3。右子節(jié)點(diǎn)3的父節(jié)點(diǎn)為2
5. 如果說遷移上來的節(jié)點(diǎn)2無父節(jié)點(diǎn)，那么它就是父節(jié)點(diǎn) root = temp
6. 遷移上來的節(jié)點(diǎn)2，找到原節(jié)點(diǎn)3是對(duì)應(yīng)父節(jié)點(diǎn)的左子節(jié)點(diǎn)還是右子節(jié)點(diǎn)，對(duì)應(yīng)的設(shè)置節(jié)點(diǎn)2的左右位置

2.3 左旋 + 右旋

 

之所以會(huì)有左旋 + 右旋，是因?yàn)橐淮斡倚僮鳑]法平衡樹高，而這種樹的不平衡節(jié)點(diǎn)的左子節(jié)點(diǎn)的右子節(jié)點(diǎn)過長，所以要把不平衡節(jié)點(diǎn)的左子節(jié)點(diǎn)向左旋轉(zhuǎn)一次，之后再進(jìn)行右旋操作。

 

代碼實(shí)現(xiàn)

if (factor(node.left) >= 0) { Node temp = super.rotateRight(node); refreshHeight(temp.right); refreshHeight(temp); } else { Node temp = super.rotateLeft(node.left); refreshHeight(temp.left); refreshHeight(temp); node.left = temp; temp = super.rotateRight(node); refreshHeight(temp.right); refreshHeight(temp); } 2.4 右旋 + 左旋

之所以會(huì)有右旋 + 左旋，是因?yàn)橐淮巫笮僮鳑]法平衡樹高，而這種樹的不平衡節(jié)點(diǎn)的右子節(jié)點(diǎn)的左子節(jié)點(diǎn)過長，所以要把不平衡節(jié)點(diǎn)的右子節(jié)點(diǎn)向右旋轉(zhuǎn)一次，之后再進(jìn)行左旋操作。

 

代碼實(shí)現(xiàn)

if (factor(node.right) <= 0) { Node temp = super.rotateLeft(node); refreshHeight(temp.left); refreshHeight(temp); } else { Node temp = super.rotateRight(node.right); refreshHeight(temp.right); refreshHeight(temp); node.right = temp; temp = super.rotateLeft(node); refreshHeight(temp.left); refreshHeight(temp); } 3. AVL樹功能測(cè)試

為了驗(yàn)證AVL樹的實(shí)現(xiàn)正確與否，這里我們做一下隨機(jī)節(jié)點(diǎn)的插入，如果它能一直保持平衡，那么它就是一顆可靠 AVL 平衡樹。

單元測(cè)試

@Test public void test_random() { AVLTree tree = new AVLTree(); for (int i = 0; i < 30; i++) { tree.insert(new Random().nextInt(100)); } System.out.println(tree); }

測(cè)試結(jié)果

輸入節(jié)點(diǎn)：61,3,34,82,1,75,56,65,87,18,3,96,53,50,42,24,69,11,95,69,1,1,84,22,5,70,28,55,38,92 /----- 96(0) /----- 95(1) | ----- 92(0) /----- 87(2) | | /----- 84(0) | ----- 82(1) /----- 75(3) | | /----- 70(0) | | /----- 69(1) | ----- 69(2) | ----- 65(0) 61(5) | /----- 56(1) | | ----- 55(0) | /----- 53(2) | | | /----- 50(0) | | ----- 42(1) | | ----- 38(0) ----- 34(4) | /----- 28(0) | /----- 24(1) | | ----- 22(0) | /----- 18(2) | | ----- 11(1) | | ----- 5(0) ----- 3(3) | /----- 3(1) | | ----- 1(0) ----- 1(2) ----- 1(0) Process finished with exit code 0

• 隨機(jī)插入30個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的順序已經(jīng)打印，經(jīng)過AVL左右旋調(diào)衡后，二叉結(jié)構(gòu)始終保持樹高平衡因子不超過1，那么驗(yàn)證通過。

四、2-3樹

 

這時(shí)候大部分資料會(huì)用2-3樹來講解紅黑樹，不過又不去實(shí)現(xiàn)一個(gè)2-3樹，只是用了一個(gè)理論套另外一個(gè)理論。雖然能從理解上多一些參考，但始終感覺沒有抓手呀。對(duì)于理科思維來說，你得給我東西呀。老是整這懸得楞的誰能受了。所以這里我們先來用Java實(shí)現(xiàn)一個(gè)2-3樹，有了基礎(chǔ)再學(xué)習(xí)紅黑樹

1. 2-3樹數(shù)據(jù)結(jié)構(gòu)

2–3樹是一種樹型數(shù)據(jù)結(jié)構(gòu)，由約翰·霍普克洛夫特于1970年發(fā)明。它通過在一個(gè)節(jié)點(diǎn)存放1-2個(gè)元素來平衡樹高。從而也使2-3樹存在2叉節(jié)點(diǎn)和3叉節(jié)點(diǎn)。

 

這里要提到一點(diǎn)，在BST二叉搜索樹可能退化成鏈表的基礎(chǔ)上。引出了自平衡二叉樹，也就是包括上一章實(shí)現(xiàn)的AVL樹和Java API HashMap中用到的紅黑樹，它們都屬于BalancedTree，也統(tǒng)稱為B樹，平衡的意思。

而本章實(shí)現(xiàn)的2-3樹也是一種簡(jiǎn)單的平衡樹，其中每個(gè)具有子節(jié)點(diǎn)（內(nèi)部節(jié)點(diǎn)）的節(jié)點(diǎn)要么有兩個(gè)子節(jié)點(diǎn)（2 節(jié)點(diǎn)）和一個(gè)數(shù)據(jù)元素，要么有三個(gè)子節(jié)點(diǎn)（3 節(jié)點(diǎn)）和兩個(gè)數(shù)據(jù)元素。另外 2-3 樹是3階B 樹，2-3-4 樹是4階B樹。

在實(shí)現(xiàn)2-3樹之前，先通過圖稿演示下在2-3樹中順序插入1、2、3、4、5、6、7，七個(gè)元素時(shí)，2-3樹的調(diào)衡處理。

 

 

• 2-3 樹的插入過程與 BST 樹類似，會(huì)通過樹的左右節(jié)點(diǎn)大小，找到自己的插入位置。
• 一個(gè)節(jié)點(diǎn)可以右1-3個(gè)元素，但當(dāng)元素個(gè)數(shù)為3時(shí)，則需要調(diào)衡。把三個(gè)節(jié)點(diǎn)的中間節(jié)點(diǎn)晉升上來，其余兩個(gè)節(jié)點(diǎn)為子節(jié)點(diǎn)。
• 如果進(jìn)行一次調(diào)衡后，上一層父節(jié)點(diǎn)達(dá)到3個(gè)元素，則需要2次調(diào)衡，來滿足2-3樹的規(guī)則。

 

咋樣，是不看過這個(gè)圖之后對(duì)于2-3樹的實(shí)現(xiàn)已經(jīng)有感覺了，想動(dòng)手寫寫試試了？

 

• 源碼地址：https://github.com/fuzhengwei/java-algorithms
• 本章源碼：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree

2. 2-3樹結(jié)構(gòu)實(shí)現(xiàn)

 

2-3 樹的實(shí)現(xiàn)并不復(fù)雜，但在實(shí)現(xiàn)前要思考以下幾個(gè)問題；

 

• Node 節(jié)點(diǎn)屬性信息都包括什么？
• 插入值，是否需要?jiǎng)?chuàng)建新的 Node？
• 插入后，節(jié)點(diǎn)內(nèi)有3個(gè)元素后，怎么遷移元素？

2.1 節(jié)點(diǎn)定義 public class Node_2_3 { // 元素 public int[] items; // 序號(hào) public int number; // 孩子 public Node_2_3[] children; // 父親【非必須】 public Node_2_3 parent; public Node_2_3() { this.items = new int[3]; this.number = 0; this.children = new Node_2_3[4]; this.parent = null; } public void insert(int e) { int idx = this.number - 1; while (idx >= 0) { if (this.items[idx] < e) break; this.items[idx + 1] = this.items[idx]; --idx; } this.items[idx + 1] = e; ++this.number; } // ... 省略部分代碼 }

• 2-3樹的幾點(diǎn)元素需要包括；一個(gè)數(shù)組的元素集合、元素的序號(hào)、孩子元素。因?yàn)橐粋€(gè)節(jié)點(diǎn)最多可臨時(shí)放入3個(gè)元素，那么就會(huì)最多有4個(gè)孩子元素，所以孩子元素也是一個(gè)數(shù)組并且在構(gòu)造函數(shù)中按照4個(gè)元素進(jìn)行初始化。
• 由于本身2-3樹插入元素的開始階段，并不是直接創(chuàng)建一個(gè)新的節(jié)點(diǎn)，而是在初始化的數(shù)組空間中存入元素。所以在節(jié)點(diǎn)中提供了一個(gè)插入元素的方法 insert 來處理新增元素。
• 另外2-3樹的節(jié)點(diǎn)類，還提供了一個(gè)方便查詢的方法。包括：獲取左邊元素、中間元素、右邊元素，以及最小值、最大值和判斷是否有孩子節(jié)點(diǎn)。這些內(nèi)容可以源碼。

2.2 拆分節(jié)點(diǎn)

 

當(dāng)一個(gè)節(jié)點(diǎn)內(nèi)有3個(gè)元素的時(shí)候，就要發(fā)起拆分東西，拆分的過程分為；

 

1. 對(duì)3個(gè)節(jié)點(diǎn)的中間節(jié)點(diǎn)，插入到父節(jié)點(diǎn)上。
2. 剩余2個(gè)節(jié)點(diǎn)創(chuàng)建出新的節(jié)點(diǎn)。
3. 建立父節(jié)點(diǎn)和新創(chuàng)建的2個(gè)節(jié)點(diǎn)間關(guān)系。

 

整個(gè)操作流程如圖所示

 

2.1 插入父節(jié)點(diǎn) private Node_2_3 split(Node_2_3 node, Node_2_3 parent) { if (parent == null) { parent = new Node_2_3(node); } parent.insert(node.getMiddleItem()); Node_2_3[] newNodes = this.triangle(node); this.replaceChild(parent, node, newNodes[0], newNodes[1]); return parent; }

• 整個(gè)2-3樹拆分的過程就是在 split 這個(gè)方法里，第一步解決了是否有父節(jié)點(diǎn)，沒有則創(chuàng)建。
• 之后將原節(jié)點(diǎn)的中間值插入到父節(jié)點(diǎn)中。接下來的操作就是拆分新節(jié)點(diǎn)和更換孩子節(jié)點(diǎn)建立新連接。

2.2 拆分新節(jié)點(diǎn) private Node_2_3[] triangle(Node_2_3 node) { Node_2_3[] newNodes = new Node_2_3[2]; newNodes[0] = new Node_2_3(node.items[0]); newNodes[1] = new Node_2_3(node.items[2]); if (!node.isLeaf()) { // 左孩子 newNodes[0].children[0] = node.children[0]; newNodes[0].children[1] = node.children[1]; // 右孩子 newNodes[1].children[0] = node.children[2]; newNodes[1].children[1] = node.children[3]; } return newNodes; }

• 基于傳遞進(jìn)來的節(jié)點(diǎn)，將節(jié)點(diǎn)的左右孩子創(chuàng)建新節(jié)點(diǎn)，如果這個(gè)孩子節(jié)點(diǎn)還有分支節(jié)點(diǎn)，則一并更新。

2.3 建立新連接 private void replaceChild(Node_2_3 parent, Node_2_3 oldChild, Node_2_3 child01, Node_2_3 child02) { if (oldChild == parent.children[0]) { parent.children[3] = parent.children[2]; parent.children[2] = parent.children[1]; parent.children[1] = child02; parent.children[0] = child01; } else if (oldChild == parent.children[1]) { parent.children[3] = parent.children[2]; parent.children[2] = child02; parent.children[1] = child01; } else { parent.children[3] = child02; parent.children[2] = child01; } }

• 建立新連接需要判斷這個(gè)節(jié)點(diǎn) oldChild 是父節(jié)點(diǎn)的左、中、右，之后進(jìn)行依次的更換。
• 如拆分節(jié)點(diǎn)的介紹圖中，用到的就是 parent.children[1] = child02;parent.children[0] = child01; 兩步操作過程。

2.3 新增節(jié)點(diǎn) public void insert(int e) { // 記錄元素 elementList.add(e); // 插入元素 if (root == null) { root = new Node_2_3(e); } else { root = insert(e, root); if (root.number == 3) { root = split(root, null); } } } private Node_2_3 insert(int e, Node_2_3 parent) { if (parent.isLeaf()) { parent.insert(e); return parent; } Node_2_3 child = null; if (parent.number == 1) { if (e < parent.getMinItem()) { child = insert(e, parent.getLeft()); } else { child = insert(e, parent.getMiddle()); } } else { if (e < parent.getMinItem()) { child = insert(e, parent.getLeft()); } else if (e > parent.getMiddleItem()) { child = insert(e, parent.getRight()); } else { child = insert(e, parent.getMiddle()); } } if (child.number == 3) { return this.split(child, parent); } return parent; }

• 新增節(jié)點(diǎn)的過程就比較簡(jiǎn)單了，一種是使用遞歸找到可以插入的位置，另外一種就是 where 循環(huán)。我們?cè)貰ST、AVL兩種數(shù)據(jù)結(jié)構(gòu)種都是用了 where 循環(huán)。
• 在2-3樹中 insert 方法遞歸到對(duì)應(yīng)的插入位置后，開始插入元素。當(dāng)插入元素結(jié)束后判斷這個(gè)節(jié)點(diǎn)是否已經(jīng)達(dá)到了3個(gè)節(jié)點(diǎn)，如果是則進(jìn)行拆分。拆分就調(diào)用了上面的步驟

3. 2-3樹結(jié)構(gòu)測(cè)試

 

為了讓讀者更好的理解2-3樹的結(jié)構(gòu)，小傅哥在程序的控制臺(tái)打印了插入的過程。網(wǎng)上沒有2-3樹在線的動(dòng)畫演示，如果讀者看到也可以留言給小傅哥

@Test public void test_insert_incr() { Tree_2_3 tree = new Tree_2_3(); for (int i = 1; i <= 10; i++) { tree.insert(i); System.out.println(tree); } }

• 順序插入10個(gè)節(jié)點(diǎn)，如果這是一顆BST樹，它將會(huì)退化成鏈表。那么我們使用自平衡的2-3樹，來看看它的插入效果。

 

測(cè)試效果

輸入節(jié)點(diǎn)(1個(gè))：1 [1] 輸入節(jié)點(diǎn)(2個(gè))：1,2 [1,2] 輸入節(jié)點(diǎn)(3個(gè))：1,2,3 /----- [3] [2] ----- [1] 輸入節(jié)點(diǎn)(4個(gè))：1,2,3,4 /----- [3,4] [2] ----- [1] 輸入節(jié)點(diǎn)(5個(gè))：1,2,3,4,5 /----- [5] [2,4]---- [3] ----- [1] 輸入節(jié)點(diǎn)(6個(gè))：1,2,3,4,5,6 /----- [5,6] [2,4]---- [3] ----- [1] 輸入節(jié)點(diǎn)(7個(gè))：1,2,3,4,5,6,7 /----- [7] /----- [6] | ----- [5] [4] | /----- [3] ----- [2] ----- [1] 輸入節(jié)點(diǎn)(8個(gè))：1,2,3,4,5,6,7,8 /----- [7,8] /----- [6] | ----- [5] [4] | /----- [3] ----- [2] ----- [1] 輸入節(jié)點(diǎn)(9個(gè))：1,2,3,4,5,6,7,8,9 /----- [9] /----- [6,8]---- [7] | ----- [5] [4] | /----- [3] ----- [2] ----- [1] 輸入節(jié)點(diǎn)(10個(gè))：1,2,3,4,5,6,7,8,9,10 /----- [9,10] /----- [6,8]---- [7] | ----- [5] [4] | /----- [3] ----- [2] ----- [1] Process finished with exit code 0

• 有了這樣的數(shù)據(jù)結(jié)構(gòu)示意，是不是再來看2-3樹就非常清晰了。—— 我說過，理科生 + 技術(shù)，不要只拋理論，要看效果的！東西到手了，能拿捏了，再補(bǔ)充理論。

五、紅黑樹

 

紅黑樹的歷史

紅黑樹（Red Black Tree）是一種自平衡二叉查找樹，于 1972 年由 Rudolf Bayer 發(fā)明的對(duì)稱二叉B樹演化而來，并以2-3-4樹、2-3樹流行。最終在 1978 年由 Leonidas J. Guibas 和 Robert Sedgewick 從對(duì)稱二叉 B 樹中推導(dǎo)出紅黑樹。PS：之所以選擇“紅色”，是因?yàn)樗亲髡咴赬erox PARC工作時(shí)可用的彩色激光打印機(jī)產(chǎn)生的最好看的顏色。

1. 紅黑樹數(shù)據(jù)結(jié)構(gòu)

建立在 BST 二叉搜索樹的基礎(chǔ)上，AVL、2-3樹、紅黑樹都是自平衡二叉樹（統(tǒng)稱B-樹）。但相比于AVL樹，高度平衡所帶來的時(shí)間復(fù)雜度，紅黑樹對(duì)平衡的控制要寬松一些，紅黑樹只需要保證黑色節(jié)點(diǎn)平衡即可。也正因紅黑樹在插入和刪除時(shí)不需要太多的平衡操作，也讓它成為；Java中HashMap的元素碰撞后的轉(zhuǎn)換、linux的CFS進(jìn)行調(diào)度算法、多路復(fù)用技術(shù)的Epoll等各類底層的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。

但紅黑樹并不是一個(gè)那么容易理解的知識(shí)點(diǎn)，甚至很多資料都只是給出紅黑樹的理論，但為什么要染色、為什么要左旋、為什么還要左旋接右旋。這樣的知識(shí)點(diǎn)本就不應(yīng)該是考死記硬背來學(xué)習(xí)的，這根本不是學(xué)習(xí)編程的”套路“。—— 你背的再溜，也沒法理解核心本質(zhì)，忘也只是時(shí)間的問題！

其實(shí)根據(jù)紅黑樹的歷史來看，最早紅黑樹就是來自于2-3樹的結(jié)構(gòu)，所以要學(xué)習(xí)清楚的結(jié)構(gòu)就要學(xué)習(xí) 2-3樹。但同時(shí)對(duì)于 2-3樹的學(xué)習(xí)也不能只是依靠一份理論，否則對(duì)于紅黑的學(xué)習(xí)來看，就是用不太理解的 2-3樹理論套紅黑樹理論，依舊沒法理解。所以小傅哥在上一章專門講解了 2-3樹，并做了具體的代碼實(shí)現(xiàn)。

現(xiàn)在來本章，我們?cè)趤砜纯醇t黑樹與2-3樹的關(guān)系；

紅黑樹 紅黑樹 2-3樹

 

 

 

一棵標(biāo)準(zhǔn)二叉紅黑樹 紅黑樹演化（紅色節(jié)點(diǎn)拉平） 最終恢復(fù)到2-3樹

紅黑樹一棵在2-3樹基礎(chǔ)上的左傾紅黑樹，這樣就可以把紅色節(jié)點(diǎn)與對(duì)應(yīng)的父節(jié)點(diǎn)拉平，再把兩個(gè)拉平的節(jié)點(diǎn)放到一個(gè)節(jié)點(diǎn)中。就是我們熟悉的2-3樹了。如果你還沒有學(xué)習(xí)過2-3樹，最好先看下小傅哥的2-3樹，否則你會(huì)看的很吃力

現(xiàn)在再來看下紅黑樹的五條定義；

 

1. 每個(gè)節(jié)點(diǎn)不是紅色就是黑色。 黑色決定平衡，紅色不決定平衡。這對(duì)應(yīng)了2-3樹中一個(gè)節(jié)點(diǎn)內(nèi)可以存放1~2個(gè)節(jié)點(diǎn)。
2. 根是黑色的。 這條規(guī)則有時(shí)會(huì)被省略。由于根總是可以從紅色變?yōu)楹谏灰欢ㄏ喾矗虼嗽撘?guī)則對(duì)分析幾乎沒有影響。
3. 所有葉子 (NIL) 都是黑色的。 這里指的是紅黑樹都會(huì)有一個(gè)空的葉子節(jié)點(diǎn)，是紅黑樹自己的規(guī)則。
4. 如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的兩個(gè)子節(jié)點(diǎn)都是黑色的。 通常這條規(guī)則也叫不會(huì)有連續(xù)的紅色節(jié)點(diǎn)。這體現(xiàn)在2-3樹中，一個(gè)節(jié)點(diǎn)最多臨時(shí)會(huì)有3個(gè)節(jié)點(diǎn)，中間是黑色節(jié)點(diǎn)，左右是紅色節(jié)點(diǎn)。2-3樹中出現(xiàn)這樣的情況后，會(huì)進(jìn)行節(jié)點(diǎn)遷移，中間節(jié)點(diǎn)成為父節(jié)點(diǎn)，左右節(jié)點(diǎn)成為子節(jié)點(diǎn)。
5. 從給定節(jié)點(diǎn)到其任何后代 NIL 節(jié)點(diǎn)的每條路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)。 對(duì)應(yīng)2-3樹中，每一層都只是有一個(gè)節(jié)點(diǎn)貢獻(xiàn)了樹高決定平衡性，也就是對(duì)應(yīng)紅黑樹中的黑色節(jié)點(diǎn)。

 

好啦，現(xiàn)在再看這5條理論是不就不需要再死記硬背了。因?yàn)榫幊瘫揪褪菍?duì)數(shù)學(xué)邏輯的具體實(shí)現(xiàn)，只要把核心邏輯理順其實(shí)很好理解。接下來小傅哥就帶著大家動(dòng)手實(shí)現(xiàn)一下紅黑樹。

2. 紅黑樹結(jié)構(gòu)實(shí)現(xiàn)

基于 BST 二叉搜索樹的基礎(chǔ)上，AVL樹添加了樹高作為計(jì)算平衡因子的條件，那么紅黑樹也需要添加一個(gè)新的顏色屬性，用于處理平衡操作。

public class Node { public Class clazz; public Integer value; public Node parent; public Node left; public Node right; // AVL 樹所需屬性 public int height; // 紅黑樹所需屬性 public Color color = Color.RED; }

相比于AVL樹通過左右旋轉(zhuǎn)平衡樹高，紅黑樹則是在2-3樹的基礎(chǔ)上，只對(duì)黑色節(jié)點(diǎn)維護(hù)樹高，所以它會(huì)使用到染色和左右旋來對(duì)樹高調(diào)衡。染色與左右旋相比，減少了平衡操作

 

• 源碼地址：https://github.com/fuzhengwei/java-algorithms
• 本章源碼：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree
• 動(dòng)畫演示：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html—— 紅黑樹初次理解還是比較困難的，可以結(jié)合學(xué)習(xí)內(nèi)容的同時(shí)做一些動(dòng)畫演示。

2.1 左傾染色

 

新增節(jié)點(diǎn)1，相當(dāng)于2-3樹中在節(jié)點(diǎn)2上添加了一個(gè)節(jié)點(diǎn)，這個(gè)時(shí)候并不影響樹高，只需要染色保持紅黑樹的規(guī)則即可。染色過程如圖所示。

 

Node uncle = grandParent.right; // 染色 if (uncle.color == Node.Color.RED){ parent.color = Node.Color.BLACK; uncle.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; current = grandParent; }

• 染色時(shí)根據(jù)當(dāng)前節(jié)點(diǎn)的爺爺節(jié)點(diǎn)，找到當(dāng)前節(jié)點(diǎn)的叔叔節(jié)點(diǎn)。
• 再把父節(jié)點(diǎn)染黑、叔叔節(jié)點(diǎn)染黑，爺爺節(jié)點(diǎn)染紅。但爺爺節(jié)點(diǎn)染紅是臨時(shí)的，當(dāng)平衡樹高操作后會(huì)把根節(jié)點(diǎn)染黑。具體參考源碼

2.2 右傾染色

 

新增節(jié)點(diǎn)4，相當(dāng)于2-3樹中在節(jié)點(diǎn)3上添加了一個(gè)節(jié)點(diǎn)，這個(gè)時(shí)候并不影響樹高，只需要染色保持紅黑樹的規(guī)則即可。染色過程如圖所示。

 

Node uncle = grandParent.left; // 染色 if(uncle.color == Node.Color.RED){ parent.color = Node.Color.BLACK; uncle.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; current= grandParent; }

• 染色時(shí)根據(jù)當(dāng)前節(jié)點(diǎn)的爺爺節(jié)點(diǎn)，找到當(dāng)前節(jié)點(diǎn)的叔叔節(jié)點(diǎn)。
• 再把父節(jié)點(diǎn)染黑、叔叔節(jié)點(diǎn)染黑，爺爺節(jié)點(diǎn)染紅。但爺爺節(jié)點(diǎn)染紅是臨時(shí)的，當(dāng)平衡樹高操作后會(huì)把根節(jié)點(diǎn)染黑。具體參考源碼

2.3 左旋調(diào)衡 2.3.1 一次左旋

 

對(duì)照2-3樹，只有當(dāng)一個(gè)節(jié)點(diǎn)內(nèi)有3個(gè)節(jié)點(diǎn)的時(shí)候，才需要調(diào)衡。那么紅黑樹則是判斷當(dāng)前節(jié)點(diǎn)的叔叔節(jié)點(diǎn)是否為紅色節(jié)點(diǎn)，如果不是則沒法通過染色調(diào)衡，也就是需要選擇進(jìn)行調(diào)衡。

 

parent.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; super.rotateLeft(grandParent);

• 當(dāng)你把紅黑樹對(duì)照理解成2-3樹，如圖中第1步驟下的左側(cè)小圖，新增的節(jié)點(diǎn)5倒置2-3樹不平衡。
• 那么這個(gè)時(shí)候需要把2-3樹中節(jié)點(diǎn)4提起來，而對(duì)應(yīng)紅黑樹則需要先進(jìn)行染色，待操作的節(jié)點(diǎn)4為黑色，兩個(gè)孩子節(jié)點(diǎn)為紅色。
• 最后是把節(jié)點(diǎn)3進(jìn)行一次左旋操作，完成樹的平衡。對(duì)應(yīng)步驟3中的左側(cè)小圖是2-3樹調(diào)衡后的結(jié)果。

2.3.2 右旋 + 左旋

 

當(dāng)一次左旋沒法調(diào)衡，需要右旋+左旋的情況，在AVL樹中有同樣的場(chǎng)景。本身樹需要左旋操作，但整體分支樹節(jié)點(diǎn)偏左，此時(shí)需要右旋調(diào)整樹結(jié)構(gòu)再左旋。此處可參考小傅哥編寫的AVL樹

 

// 偏左↙，先右旋一次調(diào)衡 if (current == parent.left){ current = parent; super.rotateRight(current); parent = current.parent; } parent.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; super.rotateLeft(grandParent);

• 紅黑樹新增節(jié)點(diǎn)4以后，4↙5 結(jié)構(gòu)偏左，需要先進(jìn)行右旋調(diào)衡樹結(jié)構(gòu)，再進(jìn)行左旋。其實(shí)這個(gè)時(shí)候再進(jìn)行的左旋就和上面一次左旋操作一致了。

4. 右旋調(diào)衡 2.4.1 一次右旋

 

對(duì)照2-3樹，只有當(dāng)一個(gè)節(jié)點(diǎn)內(nèi)有3個(gè)節(jié)點(diǎn)的時(shí)候，才需要調(diào)衡。那么紅黑樹則是判斷當(dāng)前節(jié)點(diǎn)的叔叔節(jié)點(diǎn)是否為紅色節(jié)點(diǎn)，如果不是則沒法通過染色調(diào)衡，也就是需要選擇進(jìn)行調(diào)衡。

 

parent.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; super.rotateRight(grandParent);

• 當(dāng)你把紅黑樹對(duì)照理解成2-3樹，如圖中第1步驟下的右側(cè)小圖，新增的節(jié)點(diǎn)1倒置2-3樹不平衡。
• 那么這個(gè)時(shí)候需要把2-3樹中節(jié)點(diǎn)2提起來，而對(duì)應(yīng)紅黑樹則需要先進(jìn)行染色，待操作的節(jié)點(diǎn)2為黑色，兩個(gè)孩子節(jié)點(diǎn)為紅色。
• 最后是把節(jié)點(diǎn)2進(jìn)行一次右旋操作，完成樹的平衡。對(duì)應(yīng)步驟3中的右側(cè)小圖是2-3樹調(diào)衡后的結(jié)果。

2.4.2 左旋 + 右旋

 

當(dāng)一次左旋沒法調(diào)衡，需要左旋+右旋的情況，在AVL樹中有同樣的場(chǎng)景。本身樹需要右旋操作，但整體分支樹節(jié)點(diǎn)偏右，此時(shí)需要左旋調(diào)整樹結(jié)構(gòu)再右旋。

 

// 偏右↘，先左旋一次調(diào)衡 if (current == parent.right){ current = parent; super.rotateLeft(current); parent = current.parent; } parent.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; super.rotateRight(grandParent);

• 紅黑樹新增節(jié)點(diǎn)2以后，1↘2 結(jié)構(gòu)偏右，需要先進(jìn)行左旋調(diào)衡樹結(jié)構(gòu)，再進(jìn)行右旋。其實(shí)這個(gè)時(shí)候再進(jìn)行的右旋就和上面一次右旋操作一致了。

3. 紅黑樹實(shí)現(xiàn)測(cè)試

 

為了驗(yàn)證紅黑樹的實(shí)現(xiàn)正確與否，這里我們做一下隨機(jī)節(jié)點(diǎn)的插入，如果它能一直保持平衡，那么它就是一顆可靠紅黑平衡樹。

@Test public void test_binary_search_tree() { Tree tree = new RedBlackTree(); for (int i = 0; i < 20; i++) { tree.insert(new Random().nextInt(100)); } System.out.println(tree); }

測(cè)試結(jié)果

RedBlackTree，輸入節(jié)點(diǎn)：79,92,36,35,72,22,11,66,98,28,30,39,56,26,1,25,33,80,22,23 /----- /----- 98(紅) | ----- /----- 92(黑) | | /----- | ----- 80(紅) | ----- /----- 79(黑) | | /----- | | /----- 72(黑) | | | ----- | ----- 66(紅) | | /----- | | /----- 56(紅) | | | ----- | ----- 39(黑) | ----- 36(黑) | /----- | /----- 35(黑) | | | /----- | | ----- 33(紅) | | ----- | /----- 30(紅) | | | /----- | | ----- 28(黑) | | ----- ----- 26(黑) | /----- | /----- 25(紅) | | ----- | /----- 23(黑) | | | /----- | | ----- 22(紅) | | ----- ----- 22(紅) | /----- ----- 11(黑) | /----- ----- 1(紅) ----- 對(duì)照2-3樹結(jié)構(gòu) /----- [98] /----- [92] | ----- [80] /----- [79] | | /----- [72] | ----- [66] | ----- [39,56] [36] | /----- [33,35] | /----- [30] | | ----- [28] ----- [26] | | /----- [25] ----- [22,23]----- [22] ----- [1,11]

• 隨機(jī)插入20個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的順序已經(jīng)打印，經(jīng)過紅黑樹的染色和左右旋調(diào)衡后，二叉結(jié)構(gòu)始終保持樹保持平衡，那么驗(yàn)證通過。
• 另外本文出現(xiàn)的案例已經(jīng)在單元測(cè)試中都有編寫，讀者可以在源碼中進(jìn)行測(cè)試。