Rot-schwarzer Baum. Eigenschaften, Organisationsprinzipien, Einfügungsmechanismus.

Das Konzept eines Rot -Schwarz-Baums Ein Rot-Schwarz-Baum ist eine Art Binärbaum, dessen Hauptkern die Fähigkeit zum Selbstausgleich ist. Es gibt verschiedene Arten von selbstausgleichenden Bäumen, aber in diesem Artikel werden wir nur auf den Rot-Schwarz-Baum oder (RCB) eingehen. Der Ausgleich wird durch die Einführung eines zusätzlichen Attributs des Baumknotens erreicht – „Farbe“. Jeder Baumknoten speichert zusätzlich zum Element 1 Bit an Informationen darüber, ob der Knoten rot oder schwarz ist. Dabei kann es sich nicht nur um die Farbe, sondern auch um alle anderen Informationen handeln, die es ermöglichen, einen Knotentyp von einem anderen zu unterscheiden. Zum Beispiel 1 oder 0, wahr oder falsch usw. Organisationsprinzipien (Eigenschaften) des KChD: 1. Die Wurzel des Baums ist schwarz . 2. Alle Blätter, die keine Daten enthalten, sind schwarz. 3. Beide Kinder jedes roten Knotens sind schwarz . 4. Die Tiefe in schwarzen Knoten ist für jeden Teilbaum gleich. Die Hauptoperationen, die an einem Baum ausgeführt werden, sind: 1. Suchen 2. Einfügen eines Element 3 Löschen eines Elements (delete) Die letzten beiden Operationen führen offensichtlich zu einer Änderung der Struktur des Baums und können daher zu einem Ungleichgewicht im Baum führen. Zeit- und Raumkomplexität. Die Einfüge-, Lösch- und Suchoperationen für die Zeitkomplexitäts-QCD sind O(log n) , wobei n die Anzahl der Knoten im Baum ist, denn um sie auszuführen, müssen wir zum gewünschten Knoten gelangen und jeweils einen der Teilbäume verwerfen Schritt. Für den Fall, dass das Einfügen oder Löschen zu einer Verletzung der Eigenschaften des CCH führt, ist ein Neuausgleich erforderlich. Der Ausgleich besteht aus zwei Vorgängen: Umfärben von O(1) und Drehen von O(1). Jeder Ausgleichsvorgang nimmt eine konstante Zeit in Anspruch, da er darin besteht, die Verknüpfungen von untergeordneten und übergeordneten Elementen sowie Informationen über deren Farbe neu zu schreiben. Beim Einfügen oder Löschen eines Elements kann es jedoch vorkommen, dass der Baum vom untersten Knoten bis zur Wurzel ausgeglichen werden muss. Da gewährleistet ist, dass die maximale Höhe eines aus n Knoten bestehenden CCH nicht mehr als 2log(n + 1) beträgt, kann die Neuausrichtung im schlimmsten Fall log(n)-Operationen erfordern. Der Speicheraufwand für das Einfügen beträgt O(1) , da nur ein neuer Knoten erstellt werden muss; Ausgleichs- und Repainting-Vorgänge erfordern keinen zusätzlichen Speicher . Woran erkennt man, ob ein Baum aus dem Gleichgewicht geraten ist? Für KChD befindet es sich in einem Gleichgewichtszustand, wenn alle zuvor beschriebenen Eigenschaften erfüllt sind. Es gibt 4 Arten von Ungleichgewichtszuständen: 1. Links-Links-Ungleichgewicht (LL) 2. Rechts-Rechts-Ungleichgewicht (RR) 3. Links-Rechts-Ungleichgewicht (LR) 4. Rechts-Links-Ungleichgewicht (RL) Die ersten beiden Zustände sind ebenfalls vorhanden genannt linear (Linie), da es visuell als gerader, zur Seite geneigter Ast dargestellt werden kann. Die restlichen beiden werden Dreiecke genannt . Um das CCH in einen Gleichgewichtszustand zu bringen, ist es notwendig, Manipulationen daran vorzunehmen, sogenannte Rotationen. Um diese 4 Typen auszugleichen, werden 2 Arten von Rotationen verwendet: 1. Für LL und RR 2. Für LR und RL Der erste Typ besteht darin, den ersten Knoten nach unten zu ziehen, sodass die Mitte oben liegt. Visuell lässt sich das so darstellen, als wären die Knoten wirklich Knoten an einem Seil, das an einem Nagel hängt: Die Drehung selbst sieht so aus: Bei einer komplizierten LL-Rotation, wenn Knoten auch Nachkommen haben, bleibt das Prinzip dasselbe, aber das Richtige Das untergeordnete Element des Knotens, der zum übergeordneten Knoten wird, wird zum linken/rechten untergeordneten Element des gezogenen Knotens . Beispiel: Der zweite Typ (LR,RL) besteht aus 2 Stufen und besteht darin, zunächst den Baum in den ersten Zustand zu bringen und dann auch den ersten Knoten nach unten zu ziehen: Wenn Sie sich diese Abbildung ansehen, werden Sie feststellen, dass wir uns einfach bewegen vom unteren Knoten zum oberen Knoten , was ihn zum „neuen“ Großvater macht und den „ehemaligen“ Großvater entweder zum linken oder rechten Kind macht. Beispiel: Bei einer komplizierten LR/RL-Rotation, bei der Knoten auch Nachkommen haben, bleibt das Prinzip dasselbe, aber die ehemaligen Nachkommen des „neuen“ Elternteils nehmen die frei gewordenen Plätze der Nachkommen der Kindknoten ein. Beispiel: Programmcode eines Rot -Schwarz-Baums Wir haben über die Theorie gesprochen, nun wollen wir sehen, wie das CNC-Gerät in der Programmiersprache JAVA organisiert ist. Die Mechanik des Rot-Schwarz-Baums wird insbesondere in der TreeMap- Implementierung verwendet , aus Gründen der Übersichtlichkeit verwenden wir jedoch vereinfachten Code. Alles beginnt mit der Initialisierung eines privaten statischen Felds EMPTY vom Typ Node, das einen leeren Knoten darstellt. Die Nachkommen von EMPTY sind auch EMPTY. Es wird uns beim Einfügen eines Elements nützlich sein, da alle Blätter (in der ersten Abbildung als NIL dargestellt) beim Einfügen durch dieses Feld initialisiert werden.

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

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

Die Klassenstruktur enthält Verweise auf den aktuellen Knoten current , den übergeordneten Knoten des aktuellen Knotens parent , den Großvater des aktuellen Knotens grand , den Urgroßvater des aktuellen Knotens great und einen Zeiger auf die Wurzel des Baumheaders .

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;
   }

Beim Erstellen werden Header auf den Mindestwert Integer.MIN_VALUE initialisiert, sodass jedes Element immer größer als dieser Wert ist und seine untergeordneten Elemente immer ein leeres EMPTY-Element sind. Alle Elemente sind immer größer als der Header, sodass die erste Einfügung immer rechts vom Header erfolgt. Somit zeigt das rechte Kind von header immer auf die Wurzel des Baums. Wenn also header.right == EMPTY ist , ist der Baum leer . Das Interessanteste ist eigentlich das Einfügen eines Elements . Die Strategie zum Einfügen eines Elements in das KCHD ist wie folgt: 1. Fügen Sie einen Knoten ein und färben Sie ihn rot . 2. Wenn das Einfügen zu einer Verletzung der Eigenschaften des CCH geführt hat, dann übermalen Sie den Elternteil, Onkel oder Großvater neu und drehen Sie die Knoten, um den Baum wieder in einen Gleichgewichtszustand zu bringen. Es gibt 4 Hauptszenarien, die beim Einfügen eines Elements auftreten können. Der Einfachheit halber nennen wir dieses eingefügte Element Z: 1. Z = Wurzel (das eingefügte Element ist die Wurzel des Baums) 2. Z.uncle = red (der Onkel des einzufügenden Elements ist rot ) 3. Z .uncle = schwarz (Linie). Der Onkel des eingefügten Elements ist schwarz und nach dem Einfügen des Elements wurde der Baum in Form von LL oder RR unausgeglichen. 4. Z.uncle = schwarz (Dreieck). Der Onkel des eingefügten Elements ist schwarz und nach dem Einfügen des Elements wurde der Baum in Form von RL oder LR unausgeglichen. Optisch sieht es so aus: Schauen wir uns die Korrektur der Situation für jeden der 4 möglichen Fälle genauer an. Fall Nr. 1 . Wir malen einfach die Wurzel schwarz. Fall Nr. 2. Wir malen den Großvater rot und den Onkel schwarz. Wenn der Großvater des Knotens die Wurzel ist, wird die Farbe des Großvaters wieder schwarz gestrichen. Fall Nr. 3 . Wir führen eine Rotation nach Typ Nr. 1 durch, das heißt, wir ziehen den Großvaterknoten nach unten. „A“ ersetzt „B“, und dann färben wir den „ehemaligen“ Großvaterknoten rot und den übergeordneten Knoten schwarz . Fall Nr. 4 . Es ist das schwierigste, da es aus mehreren Etappen besteht. Zuerst führen wir eine Rotation gemäß Typ Nr. 2 durch, was uns zu dem in Fall Nr. 3 beschriebenen Zustand führt, d. h. wir haben eine Rotation durchgeführt, aber der Baum befindet sich immer noch in einem Ungleichgewichtszustand, da der Nachkomme von Knoten „Z“ (Knoten „A“) ist rot . Das heißt, jetzt verletzt Knoten „A“ die Eigenschaften des CCH und die Rotation erfolgt relativ zu seinen übergeordneten Knoten, die sind: Großvater – Knoten „B“, übergeordneter Knoten – Knoten „Z“. Wir führen die Drehung erneut durch und streichen dann den „ehemaligen“ Großvater in Rot und den Elternteil in Schwarz neu . Kommen wir zurück zum Code. insert()-Methode

public void insert(int item) {
//        Сохраняем ссылку на header в current, parent и grand
        current = parent = grand = header;
//        Инициализируем все пустые элементы дерева (листы NIL) числом, которое мы хотим вставить
        EMPTY.element = item;
//        Итерируемся в цикле до тех пор, пока Bedeutung текущего Element не станет равно добавляемому (item)
        while (current.element != item) {
//        Изменяем значения 4 ссылок в цикле для итерации в глубину дерева
//        (прадеда на деда, деда на отца, отца на текущий узел)
            great = grand;
            grand = parent;
            parent = current;
//        текущий узел на его правого oder левого сына в зависимости от того,
//        больше ли текущий элемент добавляемого oder меньше,
//        то есть идем в левое поддерево, если меньше, oder в правое, если больше
            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 узел пустым листом.
    Если Bedeutung добавляемого числа оказалось равно текущему узлу,
    но при этом мы не дошли до листа (current != Empty),
    значит в дереве уже существует узел с добавляемым Bedeutungм и мы просто выходим из метода.
    Cобственно поэтому при каждом входе в метод, мы перезаписываем ссылки на корневой узел.*/
        if (current != EMPTY) {
            return;
        }
//      Если мы все же дошли до пустого листа, создаем новый узел и инициализируем его потомков пустыми листами
        current = new Node(item, EMPTY, EMPTY);
//      Проверяем, Wieим сыном будет являться текущий узел, левым oder правым
        if (item < parent.element) {
            parent.left = current;
        } else {
            parent.right = current;
        }
//      красим текущий узел в красный, его листы в чёрный, а также осуществляем перебалансировку
//      в случаях, если parent оказался красным
        reorient(item);
    }

Der schwierigste Teil geschieht in der reorient()- Methode . Diese Methode befasst sich mit dem Färben von Knoten sowie mit der Durchführung von Drehungen, wofür sie sich innerhalb des Körpers auf die -> Methode „rotate(int item, Node parent)“ bezieht , die wiederum „ rotateWithLeftNode(Node element)“ oder „rotateWithRightNode(Node element)“ aufruft. Methode, abhängig davon, ob der Wert des hinzugefügten Elements kleiner oder größer als der Wert des linken oder rechten untergeordneten Elements des Großvaters ist, dh des übergeordneten Elements des aktuellen Elements. Methodencode:

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;
//          Если текущий элемент левее родителя, но правее деда oder наоборот, то вызываем ротацию для родителя.
//          То есть фактически определяем, Wieого вида балансировку применить первого oder второго
            if (item < grand.element != item < parent.element) {
//          Если второго, то сначала передаем дедушку текущего Element и осуществляем поворот влево oder вправо,
//          одновременно изменяя ссылку на parent, в результате родителем станет сам current
                parent = rotate(item, grand);
            }
//          Осуществляем ротацию первого вида. Поскольку в результате такого поворота дедушка станет потомком родителя
//          текущего Element, то нам нужно перезаписать ссылку на нашего родителя у прадедушки, поэтому мы и передаем
//          ссылку именно на прадеда. Если прадеда в нашем маленьком дереве еще нет, то на него будет указывать HEAD

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

Die Methode „rotate(int item, Node parent)“ wird je nach dem, was als übergeordneter Parameter übergeben wurde , unterschiedlich ausgeführt : „Great“ wie bei der zweiten Ausgleichsart oder „ Grand“ wie bei der ersten Ausgleichsart. Methodencode:

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

Die Methoden „rotateWithLeftNode(Node element)“ und „rotateWithRightNode(Node element)“ führen die folgenden Aktionen aus:

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

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

Schauen wir sie uns klar an. Wenn wir für den ersten Typ die Bedingung (item < grand.element != item < parent.element) nicht eingeben , sieht die Drehung wie folgt aus: Für den zweiten Typ, wenn wir den Parameter grand (grandfather) an übergeben Parameter, die Rotation sieht folgendermaßen aus: Bitte beachten Sie, dass der übergeordnete Knoten überschrieben wurde und nun auf unseren aktuellen zeigt . Da der Baum nach der abgeschlossenen Drehung immer noch nicht im Gleichgewicht ist, führen wir erneut eine Drehung nach dem ersten Typ durch , wie im vorherigen Bild. Es kann sich die Frage stellen: Warum drehen wir beim Aufruf der Methode „rotateWithLeftNode “ die Knoten tatsächlich nach rechts und bei „rotateWithRightNode “ nach links? Dies liegt daran, dass rotatWithLeftNode eine Drehung mit dem linken untergeordneten Element des übergebenen Knotens impliziert , bzw. rotationWithRightNode mit dem rechten. Die Drehrichtung wird im Methodennamen nicht berücksichtigt . Auf diese einfache Weise wird eine Rotation auch bei komplexeren Fällen durchgeführt. Nützliche Materialien und Links: 1. Wiki-Artikel 2. Rot-Schwarz-Baum-Visualizer 3. Schöner Artikel über KChD 4. Frage, ob KChD wirklich ausgewogen ist 5. KChD-Programmcode, der kein JavaRush-Konto hat 6. Ausgezeichnetes Video von ein sehr talentierter Lehrer (spricht über AVL, aber das Prinzip ähnelt KChD) 7. Eine Reihe von Videos über das Gerät, den Einführ- und Rotationsmechanismus. Kontakte des Autors: Telegram Mail: realyte95@gmail.com