目錄
一：紅黑樹原理
什麼是紅黑樹：
紅黑規則：
添加節點：
添加節點時如何保證紅黑規則
二：Java實作紅黑樹
紅黑樹API設計以及代碼實作：
測試代碼：
一：紅黑樹原理
什麼是紅黑樹：
紅黑樹是一個二叉查找樹，但不是高度平衡的樹
- 以前交平衡二叉B樹
- 每一個節點可以是紅或者是黑的
- 紅黑樹不是高度平衡的，它的平衡是根據自己的紅黑規則進行實作的
紅黑規則：
- 每一個節點或是紅色的，或者是黑色的；
- 根節點必須是黑色；
- 如果一個節點沒有子節點或者父節點，則該節點相應的指針屬性值為Nil，這些Nil視為葉節；點，每個葉節點都是黑色的；
- 如果某一個節點是紅色的，那麼它的子節點必須是黑色（不能出現紅色節點相連的情況）；
- 對于每一個節點，從該節點到其所有後代葉子節點的簡單路徑（不能回頭，隻能往前）上，均包含相同數目的黑色節點
解釋一下第5點：我們以17節點為例，我們到15節點的左子節點Nil和右子節點Nil是包含了兩個黑色節點，再從17節點到22節點的兩個Nil節點也是包含了兩個黑色節點。
每一個紅黑樹的節點都包含下圖這些内容
添加節點：
- 添加的節點的顔色，可以是紅色的，也可以是黑色的
- 添加節點時預設節點顔色為紅色，效率是最高的，添加三個元素，一共隻需要調整一次，是以添加效率最高
添加節點時如何保證紅黑規則
我們這有十個節點：預設為紅色
1. 我們先添加這個20号，因為根節點必須為黑色是以我們将20号顔色改為黑色
2. 現在我們要添加18，因為18比20小，是以添加到20的左子節點上，在添加23号，同理添加到20的右子節點上
結論1:其父節點為黑色，不需要做任何操作。
3.繼續添加22号，放在23号的左子節點上。
這裡我們就出現了問題，不能出現兩個紅色的節點相連，那這裡我們該怎麼解決呢？
解決問題：其父節點為紅色，叔叔節點也是紅色，我們該怎麼解決。
解決方案：
- 将“父節點23”設定為黑色，将“叔叔節點18”設定為黑色
- 将“祖父節點20”設為“紅色”
- 如果祖父節點為根節點，則将根節點在次變成黑色
添加節點總結：
現在我們讨論添加節點時，父節點為紅色，叔叔節為黑色的時候，應該做的工作。
現在我們有 15 節點和 14 節點
添加15節點，如下圖
此時，我們已經違背了紅黑規則，即不能有兩個紅色節點相連的規則 （15和16節點）
- 将“父節點23”設定為黑色，将“叔叔節點18”設定為黑色
- 将“祖父節點20”設為“紅色”
- 如果祖父節點為根節點，則将根節點在次變成黑色
完成第一步：
完成第二步：
難點現在來了，我們添加14節點。
其父節點為紅色，叔叔節點是黑色，我們既要按照下面的步驟來進行處理：
- 将“父節點15”設定為黑色
- 将“祖父節點16”設為紅色
- 以祖父節點為支點進行旋轉
第一步：将“父節點15”設定為黑色
第二步：将“祖父節點16”設為紅色
第三步：對藍色箭頭的區域進行右旋：
右旋完成：再次遵守紅黑規則
紅黑樹添加總結（全）：
二：Java實作紅黑樹
紅黑樹API設計以及代碼實作：
package com.wt.redblacktree; public class RedBlackTree<Key extends Comparable<Key>, Value> { //根節點 private Node root; //記錄樹中元素的個數 private int N; private static final boolean RED = true; private static final boolean BLACK = false; private class Node { //存儲鍵 public Key key; //存儲值 private Value value; //記錄左子節點 public Node left; //記錄右子節點 public Node right; //由其父節點指向它的連結的顔色 public boolean color; public Node(Key key, Value value, Node left, Node right, boolean color) { this.key = key; this.value = value; this.left = left; this.right = right; this.color = color; } } //擷取樹中元素的個數 public int size() { return N; } /** * 判斷目前節點的父指向連結是否為紅色 * * @param x * @return */ private boolean isRed(Node x) { //傳進來有可能為NULL if (x == null) { return false;//傳回false表示空連接配接為黑色 } else { return x.color == RED; } } /** * 左旋 * * @param h * @return */ private Node rotateLeft(Node h) { //擷取h節點的右子節點，表示為x, Node x = h.right; //讓x節點的左子節點成為h節點的右子節點 h.right = x.left; //讓h節點成為x節點的左子節點 x.left = h; //讓x節點的color屬性，等于h節點的color屬性 h.color = x.color; //讓h節點的color屬性變為紅色 h.color = RED; //傳回一個節點 return x; } /** * 右旋 * * @param h * @return */ private Node rotateRight(Node h) { //擷取h節點的左子節點，表示為x Node x = h.left; //讓x節點的右子節點成為h節點的左子節點 h.left = x.right; //讓h節點成為x節點的右子節點 x.right = h; //讓x節點的color屬性變成h節點一開始的屬性 h.color = x.color; // 讓h節點的color屬性變成紅色 h.color = RED; return x; } /** * 顔色翻轉 * * @param h */ private void flipColors(Node h) { //目前節點變為紅色 h.color = RED; //左子節點和右子節點變為黑色 h.left.color = BLACK; h.right.color = BLACK; } /** * 在樹上完成插入操作 * * @param key * @param val */ public void put(Key key, Value val) { root = put(root, key, val); root.color = BLACK;//根節點的顔色總是黑色的 } /** * 在指定數中，完成插入操作，并傳回添加元素後新的樹，這裡才是插入的核心 * * @param h * @param key * @param val * @return */ private Node put(Node h, Key key, Value val) { //判斷h是否為空，如果為空則直接傳回一個紅色的節點即可 if (h == null) { //數量加1 N++; return new Node(key, val, null, null, RED); } //比較h節點的鍵和key的大小 int cmp = key.compareTo(h.key); if (cmp < 0) { //繼續往左 h.left = put(h.left, key, val); } else if (cmp > 0) { //繼續往右 h.right = put(h.right, key, val); } else { //等于的話，發生值的替換即可 h.value = val; } //插入已經完成，還要做一件事情 //進行左旋：當 目前節點h的左子節點為黑色，右子節點為紅色，需要左旋 if (isRed(h.right) && !isRed(h.left)) { //調用左旋 h = rotateLeft(h); } //進行右旋：當目前節點的h的左子節點和左子節點的左子節點都為紅色，需要右旋 if (isRed(h.left) && isRed(h.left.left)) { h = rotateRight(h); } //進行顔色翻轉:目前節點的左子節點和右子節點都為紅色時，需要顔色翻轉 if (isRed(h.left) && isRed(h.right)) { flipColors(h); } return h; } //擷取相關的算法 //根據key從樹中找出對應的值 public Value get(Key key) { return get(root, key); } //從指定的數x中，查找key對應的值 public Value get(Node x, Key key) { if (x == null) { //就證明沒有key對應的值 return null; } //比較x節點的鍵和key的大小 int cmp = key.compareTo(x.key); if (cmp < 0) { //繼續往左查找 return get(x.left, key); } else if (cmp > 0) { //繼續往右查找 return get(x.right, key); } else { return x.value; } } }
測試代碼：
package com.wt.redblacktree;
public class RedBlackTreeTest {
public static void main(String[] args) {
//建立紅黑樹
RedBlackTree<String,String> tree = new RedBlackTree<>();
//往樹中插入元素
tree.put("1","張三");
tree.put("3","李四");
tree.put("2","王五");
tree.put("4","趙六");
tree.put("6","小七");
tree.put("5","嘿嘿");
//從樹中擷取元素
String s1 = tree.get("1");
System.out.println(s1);
String s2 = tree.get("2");
System.out.println(s2);
String s3 = tree.get("3");
System.out.println(s3);
String s4 = tree.get("4");
System.out.println(s4);
String s5 = tree.get("5");
System.out.println(s5);
String s6 = tree.get("6");
System.out.println(s6);
}
}
運作結果：
以上就是我對紅黑樹規則的了解和java代碼的實作，希望可以幫助到大家。