紅黑樹。屬性、組織原則、插入機制。

紅黑樹的概念 紅黑樹是二元樹的一種，其主要本質是自平衡能力。自平衡樹有多種類型，但在本文中我們只討論紅黑樹（RCB），平衡是透過引入樹節點的附加屬性「顏色」來實現的。除了元素之外，每個樹節點還儲存 1 位元有關該節點是紅色還是黑色的信息，這不僅可以是顏色，還可以是允許人們區分一種類型節點和另一種類型節點的任何其他資訊。例如，1 或 0、true 或 false 等。KChD 的組織原則（屬性）： 1. 樹的根是黑色的。2. 所有不包含資料的葉子都是黑色的 3. 每個紅色節點的兩個子節點都是黑色的4.對於任何子樹來說， 黑色節點 的深度都是相同的 在樹上執行的主要操作是： 1. 搜尋 2. 插入一個element 3 刪除元素（delete） 最後兩個操作顯然會導致樹的結構發生變化，因此，它們的結果可能是樹的不平衡。 時間和空間複雜性。 時間複雜度 QCD 的插入、刪除和搜尋操作都是 O(log n)，其中n 是樹中的節點數，因為要執行這些操作，我們需要到達所需的節點，並在每個節點丟棄一個子樹步。當插入或刪除導致違反CCH的屬性時，需要重新平衡。平衡由兩個操作組成：重新著色 O(1) 和旋轉 O(1)。每個平衡操作都需要恆定的時間，因為它包括重寫子元素和父元素的連結以及有關其顏色的資訊。然而，在插入或刪除元素時，可能會出現需要從最低節點一直到根來平衡樹的情況。由於保證n個節點組成的CCH的最大高度不超過2log(n + 1)，那麼在最壞的情況下，重新平衡需要log(n) - 操作。插入的記憶體成本是O(1)，因為它只涉及創建新節點；平衡和重畫操作不需要額外的記憶體。 如何判斷一棵樹是否失去平衡？ 對於 KChD，如果滿足前面描述的所有屬性，則處於平衡狀態。 不平衡狀態有 4 種類型： 1. 左右不平衡 (LL) 2. 左右不平衡 (RR) 3. 左右不平衡 (LR) 4. 左右不平衡 (RL) 前兩種狀態也 稱為線性（Line ），因為在視覺上它可以表示為向一側傾斜的直分支。其餘兩個稱為三角形。為了使 CCH 達到平衡狀態，需要對其進行稱為旋轉的操作。 為了平衡這 4 種類型，使用 2 種類型的旋轉： 1. 對於 LL 和 RR 2. 對於 LR 和 RL 第一種類型是將第一個節點向下拉，使中間位於頂部。從視覺上看，這可以表示為節點實際上是掛在釘子上的繩子上的節點： 旋轉本身如下所示： 對於復雜的 LL 旋轉，當節點也有後代時，原理保持不變，但是正確的成為父節點的節點的子節點將成為被拉動節點的左/右子節點。範例： 第二種類型 (LR,RL)由 2 個階段組成，首先將樹置於第一個狀態，然後將第一個節點向下拉： 如果您查看此圖，您會注意到我們只是在移動底部節點到頂部，使其成為“新”祖父，並使“前”祖父成為左孩子或右孩子。範例： 在複雜的 LR/RL 輪換中，當節點也有後代時，原理保持不變，但「新」父節點的前後代取代了子節點的後代的空出位置。例： 紅黑樹的 程式碼 理論講完了，現在我們來看看CNC設備在JAVA程式語言中是如何組織的。特別是在TreeMap實作中使用了紅黑樹機制，但為了清楚起見，我們將使用更簡化的程式碼。這一切都是從初始化 Node 類型的私人靜態欄位 EMPTY 開始的，它代表一個空節點。EMPTY的後代也是EMPTY。當我們插入元素時，它對我們很有用，因為所有工作表（在第一張圖中表示為 NIL）都在插入時由該欄位初始化。

public class RedBlackTree {
    private static final Node EMPTY = new Node(0);

    static {
        EMPTY.left = EMPTY;
        EMPTY.right = EMPTY;
    }

該類別結構包含對當前節點 current 的引用、當前節點parent 的父節點、當前節點grand的祖父節點、當前節點great的曾祖父節點以及指向樹頭根的指標。

protected Node current;
   private Node parent;
   private Node grand;
   private Node great;
   private Node header;

   public RedBlackTree() {
       header = new Node(Integer.MIN_VALUE);
       header.left = EMPTY;
       header.right = EMPTY;
   }

建立時，標頭被初始化為最小值 Integer.MIN_VALUE，以便任何元素都會始終大於它，其子元素將始終是空的 EMPTY 元素。所有元素總是大於標題，因此第一次插入總是發生在標題的右側。因此， header 的右子節點總是指向樹的根，因此，如果header.right == EMPTY，則樹為空。實際上，最有趣的是插入一個元素。在 KCHD 插入元素的策略如下： 1. 插入一個節點並將其著色為紅色。2. 如果插入導致違反了 CCH 的屬性，則重新繪製父級、叔級或祖父級並旋轉節點以使樹恢復平衡狀態。 插入元素時可能會發生 4 種主要情況，為了方便起見，我們將這個插入的元素稱為 Z： 1. Z = root（被插入的元素是樹的根） 2. Z.uncle = red（叔父）正在插入的元素的顏色為紅色） 3. Z .uncle = 黑色（線）。插入元素的叔叔是黑色的，插入元素後，樹以 LL 或 RR 的形式變得不平衡。4. Z.uncle = 黑色（三角形）。插入元素的叔叔是黑色的，插入元素後，樹以 RL 或 LR 的形式變得不平衡。從視覺上看，它看起來像這樣： 讓我們更詳細地看看如何糾正 4 種可能情況中的每一種情況。 案例一。我們把根部塗成黑色。 案例2。我們把祖父塗成紅色，叔叔塗成黑色。如果該節點的祖父節點是根節點，則祖父節點的顏色再次被塗成黑色。 案例3。我們按照第1種方式輪換，即將祖父結拉下來。“A”取代“B”，然後我們將“前”祖父節點重新著色為紅色，將父節點重新著色為黑色。 案例4。這是最困難的，因為它由幾個階段組成。首先，我們根據類型2進行旋轉，這導致我們進入情況3描述的狀態，即我們已經進行了旋轉，但是樹仍然處於不平衡狀態，因為節點“Z”（節點“A”）是紅色的。也就是說，現在節點“A”違反了CCH的屬性，將相對於其父節點進行旋轉，即：祖父-節點“B”，父-節點“Z”。我們再次執行旋轉，然後將“前”祖父重新繪製為紅色，將父級重新繪製為黑色。 讓我們回到程式碼。插入()方法

public void insert(int item) {
//        Сохраняем ссылку на header в current, parent и grand
        current = parent = grand = header;
//        Инициализируем все пустые элементы дерева (листы NIL) числом, которое мы хотим вставить
        EMPTY.element = item;
//        Итерируемся в цикле до тех пор, пока meaning текущего element не станет равно добавляемому (item)
        while (current.element != item) {
//        Изменяем значения 4 ссылок в цикле для итерации в глубину дерева
//        (прадеда на деда, деда на отца, отца на текущий узел)
            great = grand;
            grand = parent;
            parent = current;
//        текущий узел на его правого or левого сына в зависимости от того,
//        больше ли текущий элемент добавляемого or меньше,
//        то есть идем в левое поддерево, если меньше, or в правое, если больше
            current = item > current.element ? current.right : current.left;
//          На каждой итерации проверяем левый сын текущего element и правый сын текущего element красные
            if (current.left.color == Color.RED && current.right.color == Color.RED) {
//           Если да, то вызываем метод для исправления и переориентации дерева относительно текущего element
//           Который записан в current на текущей итерации
                reorient(item);
            }
        }
/*  При выходе из цикла проверяем, является ли current узел пустым листом.
    Если meaning добавляемого числа оказалось равно текущему узлу,
    но при этом мы не дошли до листа (current != Empty),
    значит в дереве уже существует узел с добавляемым meaningм и мы просто выходим из метода.
    Cобственно поэтому при каждом входе в метод, мы перезаписываем ссылки на корневой узел.*/
        if (current != EMPTY) {
            return;
        }
//      Если мы все же дошли до пустого листа, создаем новый узел и инициализируем его потомков пустыми листами
        current = new Node(item, EMPTY, EMPTY);
//      Проверяем, Howим сыном будет являться текущий узел, левым or правым
        if (item < parent.element) {
            parent.left = current;
        } else {
            parent.right = current;
        }
//      красим текущий узел в красный, его листы в чёрный, а также осуществляем перебалансировку
//      в случаях, если parent оказался красным
        reorient(item);
    }

最困難的部分發生在reorient()方法中。此方法處理節點著色以及執行旋轉，在主體內部它引用 -> rotate(int item, Nodeparent)方法，該方法依次調用rotateWithLeftNode(Node element)或rotateWithRightNode(Node element) method ，取決於添加元素的值是小於還是大於祖父元素的左子元素或右子元素（即當前元素的父元素）的值。方法代碼：

protected void reorient(int item) {
//      Первоначально красим текущий узел, до которого мы дошли в методе insert в красный, а его потомков в черный
        current.color = Color.RED;
        current.left.color = Color.BLACK;
        current.right.color = Color.BLACK;
//      Если цвет родителя current оказывается красным, то нам необходимо провести ротацию узлов
        if (parent.color == Color.RED) {
//          красим дедушку в красный
            grand.color = Color.RED;
//          Если текущий элемент левее родителя, но правее деда or наоборот, то вызываем ротацию для родителя.
//          То есть фактически определяем, Howого вида балансировку применить первого or второго
            if (item < grand.element != item < parent.element) {
//          Если второго, то сначала передаем дедушку текущего element и осуществляем поворот влево or вправо,
//          одновременно изменяя ссылку на parent, в результате родителем станет сам current
                parent = rotate(item, grand);
            }
//          Осуществляем ротацию первого вида. Поскольку в результате такого поворота дедушка станет потомком родителя
//          текущего element, то нам нужно перезаписать ссылку на нашего родителя у прадедушки, поэтому мы и передаем
//          ссылку именно на прадеда. Если прадеда в нашем маленьком дереве еще нет, то на него будет указывать HEAD

//          Если балансировка идет по первому виду, то current'ом станет родитель текущего current
//          Если по второму, то current'ом будет сам вставляемый элемент, на него же будет храниться link в parent
            current = rotate(item, great);
//          красим текущий узел в чёрный
            current.color = Color.BLACK;
        }
//      красим корень в черный, если в результате ротаций, например, How в сценарии № 2 дедушкой оказался корень
//      который мы ранее покрасor в красный
        header.right.color = Color.BLACK;
    }

取決於作為父參數傳遞的內容，rotate(int item, Node Parent) 方法的執行方式會有所不同，如在第二種類型的平衡中為“ great ”，或在第一種平衡類型中為“ grand” 。方法代碼：

private Node rotate(int item, Node parent) {
        // Проверяем в Howом поддереве относительно grand/great узла находится текущий элемент
//        Если меньше, значит, гарантированно в левом, если больше - в правом
        if (item < parent.element) {
//          Получаем ссылку на родителя левого поддерева
            Node node = parent.left;
//          Проверяем Howим образом выполнить ротацию - справа
//          если вставляемый элемент больше, чем элемент родителя,
//          or слева, если вставляемый элемент меньше
            Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
//          присваиеваем переданному дедушке or прадедушке ссылку на узел, который стал новым родителем
            parent.left = resultNode;
            return parent.left;
        } else {
//           Получаем ссылку на родителя правого поддерева
            Node node = parent.right;
//           Проделываем аналогичные действия, но для правого поддерева
            Node resultNode = item < node.element ? rotateWithLeftNode(node) : rotateWithRightNode(node);
            parent.right = resultNode;
            return parent.right;
        }
    }

該rotateWithLeftNode(Node element)和rotateWithRightNode(Node element) 方法執行以下操作：

private Node rotateWithLeftNode(Node element) {
//      Передаваемым элементом может быть либо родитель current узла, либо его дедушка
//      Получаем ссылку на левого потомка передаваемого в параметр element.
        Node left = element.left;
//      Назначаем нового левого потомка текущему элементу.
//      Новым потомком становится правый потомок левого потомка
        element.left = left.right;
//      Правый потомок левого потомка теперь ссылается на передаваемый в параметр элемент (дедушку or прадедушку)
//      то есть дедушка or прадедушка становится его правым потомком
        left.right = element;
//      возвращаем левый потомок передаваемого узла
        return left;
    }

private Node rotateWithRightNode(Node element) {
//      Получаем ссылку на правого потомка передаваемого в параметр element.
//      Действия аналогичны
        Node right = element.right;
        element.right = right.left;
        right.left = element;
        return right;
    }

讓我們清楚地看看它們。對於第一種類型，當我們不輸入 條件(item < grand.element != item <parent.element)時，旋轉將如下所示： 對於第二種類型，當我們將 grand（祖父）參數傳遞給參數，旋轉將如下所示： 請注意，父節點已被覆蓋，現在指向我們當前的. 由於旋轉完成後樹仍然不平衡，所以我們再次按照第一種類型旋轉，如上圖所示。 可能會出現問題：為什麼當呼叫rotateWithLeftNode方法時，我們實際上會將節點旋轉到右側，而當呼叫rotateWithRightNode方法時，我們實際上會將節點旋轉到左側？這是因為rotatWithLeftNode意味著與所傳遞節點的左子節點進行旋轉，rotateWithRightNode分別與右子節點旋轉。方法名稱中不考慮旋轉方向。透過這種簡單的方式，對於更複雜的情況也可以進行旋轉。 有用的資料和連結： 1. Wiki 文章 2. 紅黑樹視覺化工具 3. 關於 KChD 的好文章 4.關於 KChD 是否真正平衡的問題 5. KChD 程式碼，誰沒有 JavaRush 帳戶 6.精彩影片非常有才華的老師（講的是AVL，但原理和KChD類似） 7.一系列關於設備、插入和旋轉機制的視頻 作者聯繫方式： Telegram 郵箱：relyte95@gmail.com