红黑树。属性、组织原理、插入机制。

红黑树的概念 红黑树是二叉树的一种，其主要本质是自平衡能力。自平衡树有多种类型，但在本文中我们只讨论红黑树（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 轮换中，当节点也有后代时，原理保持不变，但“新”父节点的前后代取代了子节点的后代的空出位置。例： 红黑树的 程序代码 理论讲完了，现在我们看看数控设备在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