溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇內容介紹了“如何使用紅黑樹”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
在學習紅黑樹之前，我們先來看看紅黑樹的性質，針對每一條性質我們都需要問一個Why，帶著問題去學習紅黑樹；如果我們搞懂了這些問題，那么就理解了紅黑樹本質，當然與實現還有一些距離。
紅黑樹是近似平衡的二叉樹，紅黑樹對應的理論模型可以是2-3樹，也可以是2-3-4樹，所以在學習紅黑樹之前，我們需要先了解2-3樹和2-3-4樹；
紅黑樹與2-3樹、2-3-4樹的關系就好比接口與實現類的關系；2-3樹與2-3-4樹是接口，而紅黑樹是基于接口的實現
2-3樹、2-3-4樹都是B樹的特列情況
為了保證樹的絕對平衡，允許樹中的節點保存多個鍵值，在2-3樹中可以出現一個節點存在一個鍵值兩條鏈接，也允許同一個節點包含最多兩個鍵三條鏈接；
2-3樹如下圖：
2-3樹的查找過程與二叉樹類似，查找鍵與節點中的鍵比較，如果遇到與查找鍵相等的節點，查找命中；否則繼續去對應的子樹中去查找，如果遇到空的鏈接表示查找未命中。
通過上面的三種情況的演示，我們發現2-3樹和標準的二叉樹的生長是不同的，二叉樹的生長是由上向下生長的，而2-3樹的生長是由下向上的。
在上一篇的二叉樹中，我們發現最糟糕的情況是插入的節點有序，導致二叉樹退化成了鏈表，性能下降，我們使用2-3樹順序插入看看如何，例如順序插入1，2，3，4，5，6，7
由此我們可以看出在最壞的情況下2-3樹依然完美平衡的，有比較好的性能。但是這是理論，與真正的實現還是有一段距離
了解了紅黑樹的理論模型2-3樹之后，那么就可以基于2-3樹來實現我們的紅黑樹。
由于2-3樹中存在著雙鍵的節點，由于我們需要在二叉樹中表示出雙鍵的節點，所以我們需要在節點中添加一個顏色的屬性color，如果節點是紅色，那么表示當前節點和父節點共同組成了2-3樹中的雙鍵節點。
對上一篇中二叉樹的節點做一些修改，代碼如下：
class Node implements TreeNode {
public static final boolean RED = true;
public static final boolean BLACK = false;
public K key;
public V value;
public Node left;
public Node right;
public boolean color; //RED 或者 BLACK
public int size = 1; //當前節點下節點的總個數
public Node(K key, V value, boolean color) {
this.key = key;
this.value = value;
this.color = color;
}
@Override
public Node getLeft() {
return this.left;
}
@Override
public Node getRight() {
return this.right;
}
@Override
public Color getColor() {
return color ? Color.RED : Color.BLACK;
}
}
由于紅黑樹本身也是二叉樹，所以在上一篇中實現的二叉樹查找方法可以不用做任何的修改就可以直接應用到紅黑樹。
本篇中我們實現的2-3樹紅黑樹參考算法4，并且我們規定紅色節點只能出現在左節點，即左傾紅黑樹。（為什么規定紅色節點只能出現在左節點？其實右邊也是可以的，只允許存在左節點是因為能夠減少可能出現的情況，實現所需的代碼相對較小）
紅黑樹作為了2-3樹的實現，基于2-3樹去看紅黑樹的性質就不在是干癟癟的約定，也不需要要強行記憶。
性質1. 結點是紅色或黑色。（why：為什么節點要區分顏色，紅色節點的作用是什么？） 在上面我們已經解釋過了，要區分顏色主要是想要在二叉樹中來表示出2-3樹的雙鍵節點的情況，如果是紅色節點，那么表示當前節點與父節點共同組成了2-3數的雙鍵；黑色節點表示二叉樹中的普通節點
性質2. 根結點是黑色。（why：為什么根節點必須是黑色） 還是基于紅色節點的作用來理解，根節點本身沒有父節點，無法組成2-3樹雙鍵，所以不可能是紅色節點。
性質3. 所有葉子都是黑色。（why） 此處提到的葉子其實是空鏈接，在上面的圖中空連接未畫出。
性質4. 從每個葉子到根的所有路徑上不能有兩個連續的紅色結點。(why) 此性質還是基于紅色節點的作用來理解，如果出現了兩個連續的紅色節點，那么與父節點組成了3鍵的節點，但是這在2-3樹實現的左傾紅黑樹中是不允許的。（在基于2-3-4樹實現的紅黑樹中允許出現3鍵，但是只能是左右兩邊各一個紅色節點，也不能連續，在后面擴展部分會有講解）
性質5. 從任一節結點到其每個葉子的所有路徑都包含相同數目的黑色結點。(why) 此性質可以基于2-3樹的理論模型來理解，因為在紅色節點表示與父節點同層高，所以在紅黑樹中只有黑色節點會貢獻樹的高度，所以從任一節結點到其每個葉子的所有路徑都包含相同數目的黑色結點
性質6. 每次新插入的節點都必須是紅色（why） 此性質在百度百科中未出現，但在一些國外網站上有看到，個人覺得對于理解紅黑樹也有幫助，所以加在了這里；在上面我們已經演示過了2-3樹插入鍵的過程，先插入鍵值到節點，然后在判斷是否需要分裂，因為優先插入建到當前節點組成2-3樹的雙鍵或3鍵，而在紅黑樹中只有通過使用紅色節點與父節點組成2-3樹的雙鍵或3鍵，所以每次新插入的節點都必須是紅色。
只看節點的變化可能不太直觀，我們可以來看一個2-3樹如何表示成左傾紅黑樹
當我們把紅色節點拖動到與父節點同一個高度的時候，可以與2-3樹對比來看，發現紅黑樹很好的表示了2-3樹
我需要定義個方法來判斷節點屬于什么顏色，如果是紅色就返回true，否則返回false
protected boolean isRed(Node node) {
if (Objects.isNull(node)) {
return Node.BLACK;
}
return node.color;
}
在實現紅黑樹的插入或者刪除操作可能會出現紅色節點在右邊或者兩個連續的紅色節點，在出現這些情況的時候我們需要通過旋轉操作來完成修復。
由于旋轉操作完成之后需要修改父節點的鏈接，所以我們定義的旋轉方法需要返回旋轉之后的節點來重置父節點的鏈接
左旋代碼實現如下：
protected Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = Node.RED;
size(h); //計算子樹節點的個數
size(x);
return x;
}
重新指定兩個節點的左右子樹的鏈接，并且修改節點的顏色。其次是計算每個子樹所包含的節點個數，計算的方式與上一篇中二叉樹的size實現類似，這里就不重復敘述，參考《基于二叉樹實現Map》
右旋代碼實現如下：
protected Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = Node.RED;
size(h);
size(x);
return x;
}
在2-3樹中，當節點中的key值達到了3個就需要進行分裂，其中一個節點將會上浮；那在紅黑樹中應該如何來表示這個操作呢？
在紅黑樹中要實現節點分裂，其實就是節點顏色的變化；紅黑樹經過左旋右旋之后最終都會達到父節點是黑色，左右兩個子節點是紅色（后面再插入操作中可以看到詳細的轉變過程），這種狀態就對應了2-3樹中的三鍵節點的情況，這時候分裂的操作就是把左右兩個子節點的顏色變成黑色，父節點變成紅色。
代碼實現如下：
/轉換顏色，對應了23樹中的節點分裂
protected void upSplit(Node node) {
if (Objects.isNull(node)) {
return;
}
node.left.color = Node.BLACK;
node.right.color = Node.BLACK;
node.color = Node.RED;
}
根據以上各種情況的分析，我們可以總結出統一的變化規律：
圖形變化如下：
經過上面的分析之后我們現在可以來代碼實現紅黑樹的插入操作
@Override
public void put(K key, V value) {
if (Objects.isNull(key)) {
throw new IllegalArgumentException("the key can't null");
}
root = put(root, key, value);
root.color = Node.BLACK;
}
private Node put(Node node, K key, V value) {
if (Objects.isNull(node)) {
return new Node(key, value, Node.RED);
}
int compare = key.compareTo(node.key);
if (compare > 0) {
node.right = put(node.right, key, value);
} else if (compare < 0) {
node.left = put(node.left, key, value);
} else {
node.value = value;
}
if (isRed(node.right) && !isRed(node.left)) {
node = rotateLeft(node);
}
if (isRed(node.left) && isRed(node.left.left)) {
node = rotateRight(node);
}
if (isRed(node.left) && isRed(node.right)) {
upSplit(node);
}
size(node);
return node;
}
由于根節點必須為黑色的性質，防止變色操作把根節點變為紅色，所以我們在插入操作之后統一設置一次根節點為黑色；
紅黑樹的插入操作前半部分和上一篇實現的二叉樹的插入操作一致，唯一不同的只有最后三個if操作，這三個操作就是上面總結的統一變化規律的代碼實現。
第一個if判斷處理如果右節點是紅色，左節點是黑色，那么就進行左旋
第二個if判斷處理如果左節點時紅色且他的左節點也是紅色，那么就進行右旋
第三個if判斷如果左右兩個子節點都是紅色，那么就進行變色
因為刪除操作可能會造成樹不平衡，并且可能會破壞紅黑樹的性質，所以刪除操作會比插入操作更加麻煩。
首先我們需要先回到2-3樹的理論模型中，如果我們刪除的節點當前是雙鍵節點，那么我們可以直接進行刪除操作，樹的高度也不會結構也不會發生變化；所以紅黑樹的刪除操作的關鍵就是需要保證待刪除節點是一個雙鍵的節點。
在執行刪除操作時我們也會實現到變色的操作，這里的變色和插入是的變色操作恰好相反，父節點變為黑色，兩個子節點變為紅色
protected void flipColors(Node h) {
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
在正式實現刪除操作之前，我們先來討論下紅黑樹刪除最小值和最大值的情況，最后實現的刪除操作也會使用到刪除最小值和刪除最大值
二叉樹刪除最小值就是一直沿著樹的左子樹中查找，直到遇到一個節點的左子樹為null，那么就刪除該節點
紅黑樹的刪除最小值類似，但是我們需要保證待刪除的節點是一個雙鍵的節點，所以在在遞歸到每個節點是都需要保住當前節點是雙鍵節點，那么在最后找到的最小值就一定會在一個雙鍵節點中（因為遞歸時已經保住的父節點是雙鍵節點）。
那么如果保證當前遞歸節點是一個雙鍵節點呢？這里就會有3中情況:
以上是紅黑樹刪除最小值會遇到的所有情況，針對最后兩種情況，為了代碼的實現簡單，我們考慮把這兩種情況進行合并；
先把初始化根節點為紅色，再進行變色，然后判斷是否node.right.left是紅色，如果是就進行旋轉操作
刪除最小值的代碼實現如下：
private Node moveToRedLeft(Node h) {
flipColors(h);
if (isRed(h.right.left)) {
h.right = rotateRight(h.right);
h = rotateLeft(h);
flipColors(h);
}
return h;
}
@Override
public void deleteMin() {
if (isEmpty()) {
throw new NoSuchElementException("BST underflow");
}
if (!isRed(root.left) && !isRed(root.right)) {
root.color = Node.RED;
}
root = deleteMin(root);
if (!isEmpty()) {
root.color = Node.BLACK;
}
}
private Node deleteMin(Node h) {
if (h.left == null) {
return null;
}
if (!isRed(h.left) && !isRed(h.left.left)) {
h = moveToRedLeft(h);
}
h.left = deleteMin(h.left);
return balance(h);
}
private Node balance(Node h) {
if (isRed(h.right) && !isRed(h.left)) {
h = rotateLeft(h);
}
if (isRed(h.left) && isRed(h.left.left)) {
h = rotateRight(h);
}
if (isRed(h.left) && isRed(h.right)) {
flipColors(h);
}
h.size = size(h.left) + size(h.right) + 1;
return h;
}
在刪除掉最小值之后，我們需要重新修復紅黑樹，因為之前我們的操作可能會導致3鍵節點的存在，刪除之后我們需要重新分解3建節點；上面代碼中的balance就是重新修復紅黑樹。
刪除最大值思路和刪除最小值的思路類似，這里就不詳細敘述了，直接上圖
刪除最大值需要從左節點中借一個節點，代碼實現如下：
@Override
public void deleteMax() {
if (isEmpty()) {
throw new NoSuchElementException("BST underflow");
}
if (!isRed(root.left) && !isRed(root.right)) {
root.color = Node.RED;
}
root = deleteMax(root);
if (!isEmpty()) {
root.color = Node.BLACK;
}
}
private Node deleteMax(Node node) {
if (isRed(node.left)) { //此處與刪除最小值不同，如果左邊是紅色，那么先借一個節點到右邊來
node = rotateRight(node);
}
if (Objects.isNull(node.right)) {
return null;
}
if (!isRed(node.right) && !isRed(node.right.left)) {
node = moveToRedRight(node);
}
node.right = deleteMax(node.right);
return balance(node);
}
private Node moveToRedRight(Node node) {
flipColors(node);
if (isRed(node.left.left)) {
node = rotateRight(node);
flipColors(node);
}
return node;
}
在查找路徑上進行和刪除最小值相同的變換可以保證在查找過程中任意當前節點不會是雙鍵節點；
如果查找的鍵值在左節點，那么就執行與刪除最小值類似的變化，從右邊借節點；
如果查找的鍵值在右節點，那么就執行與刪除最大值類似的變化，從左邊借節點。
如果待刪除的節點處理葉子節點，那么可以直接刪除；如果是非葉子節點，那么左子樹不為空就與左子樹中最大值進行交換，然后刪除左子樹中的最大值，左子樹為空就與右子樹最小值進行交換，然后刪除右子樹中的最小值。
代碼實現如下：
@Override
public void delete(K key) {
if (isEmpty()) {
throw new NoSuchElementException("BST underflow");
}
if (!isRed(root.left) && !isRed(root.right)) {
root.color = Node.RED;
}
root = delete(root, key);
if (!isEmpty()) {
root.color = Node.BLACK;
}
}
private Node delete(Node node, K key) {
int compare = key.compareTo(node.key);
if (compare < 0) {//左子樹中查找
if (!isRed(node.left) && !isRed(node.left.left)) {
node = moveToRedLeft(node);
}
node.left = delete(node.left, key);
} else if (compare > 0) { //右子樹中查找
if (isRed(node.left)) {
node = rotateRight(node);
}
if (!isRed(node.right) && !isRed(node.right.left)) {
node = moveToRedRight(node);
}
node.right = delete(node.right, key);
} else {
if (Objects.isNull(node.left) && Objects.isNull(node.right)) {
return null; //葉子節點直接結束
}
if (Objects.nonNull(node.left)) { //左子樹不為空
Node max = max(node.left);
node.key = max.key;
node.value = max.value;
node.left = deleteMax(node.left);
} else { //右子樹不為空
Node min = min(node.right);
node.key = min.key;
node.value = min.value;
node.right = deleteMin(node.right);
}
}
return balance(node);
}
上面我們已經實現了紅黑樹的主要代碼，但是如何驗證我們的紅黑樹是不是真正的紅黑樹，最好的方式就是基于我們實現的版本畫出紅黑樹，然后通過紅黑樹的性質來驗證
由于如何畫出紅黑樹不是本篇的重點，所以就不貼出代碼了，有需要的朋友可以去倉庫中查看；
編寫單元來測試我們用紅黑樹實現的Map,并且畫出紅黑樹驗證是否正確
@Test
public void testDelete() throws IOException {
RedBlack23RedBlackTreeMap<Integer, String> map = new RedBlack23RedBlackTreeMap<>();
map.put(8, "80");
map.put(18, "180");
map.put(5, "50");
map.put(15, "150");
map.put(17, "170");
map.put(25, "250");
map.put(40, "40");
map.put(80, "80");
map.put(30, "30");
map.put(60, "60");
map.put(16, "16");
map.draw("/Users/huaan9527/Desktop/redBlack4.png"); //畫出刪除之前的紅黑樹
map.delete(40);
map.delete(17);
map.delete(25);
map.nodes().forEach(System.out::println); //根據key從小到大順序打印出節點
map.draw("/Users/huaan9527/Desktop/redBlack5.png"); //畫出刪除之后的紅黑樹
}
順序打印出node的執行的結果：
“如何使用紅黑樹”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
