Drzewo czerwono-czarne. Właściwości, zasady organizacji, mechanizm wstawiania.

Koncepcja drzewa czerwono -czarnego Drzewo czerwono-czarne to rodzaj drzewa binarnego, którego główną istotą jest zdolność do samorównoważenia. Istnieje kilka rodzajów drzew samobalansujących, ale w tym artykule zajmiemy się tylko drzewem czerwono-czarnym czyli (RCB).Równowagę osiąga się poprzez wprowadzenie dodatkowego atrybutu węzła drzewa - „koloru”. Każdy węzeł drzewa oprócz elementu przechowuje 1 bit informacji o tym, czy węzeł jest czerwony czy czarny i może to być nie tylko kolor, ale także inna informacja pozwalająca odróżnić jeden typ węzła od drugiego. Na przykład 1 lub 0, prawda lub fałsz itp. Zasady organizacji (właściwości) KChD: 1. Korzeń drzewa jest czarny . 2. Wszystkie liście niezawierające danych są czarne 3. Oboje dzieci każdego czerwonego węzła są czarne 4. Głębokość czarnych węzłów jest taka sama dla każdego poddrzewa Główne operacje wykonywane na drzewie to: 1. Szukaj 2. Wstaw element 3 Usuwanie elementu (usuń) Dwie ostatnie operacje w oczywisty sposób prowadzą do zmiany struktury drzewa, a zatem ich efektem może być brak równowagi w drzewie. Złożoność czasu i przestrzeni. Operacje wstawiania, usuwania i wyszukiwania dla QCD złożoności czasu to O(log n) , gdzie n to liczba węzłów w drzewie, ponieważ aby je wykonać, musimy dostać się do żądanego węzła, odrzucając jedno z poddrzew w każdym krok. W przypadku, gdy wstawienie lub usunięcie prowadzi do naruszenia właściwości CCH, konieczne jest wykonanie ponownego zrównoważenia. Równoważenie składa się z dwóch operacji: ponownego kolorowania O(1) i rotacji O(1). Każda operacja równoważenia zajmuje stały czas, gdyż polega na przepisaniu powiązań elementów podrzędnych i nadrzędnych oraz informacji o ich kolorze. Jednak podczas wstawiania lub usuwania elementu może zaistnieć sytuacja, w której drzewo będzie wymagało zbilansowania od najniższego węzła aż do korzenia. Ponieważ gwarantuje się, że maksymalna wysokość kanału CCH składającego się z n węzłów nie będzie większa niż 2log(n + 1), wówczas w najgorszym przypadku ponowne równoważenie może wymagać operacji log(n). Koszt wstawienia pamięci wynosi O(1) , ponieważ obejmuje jedynie utworzenie nowego węzła; operacje równoważenia i ponownego malowania nie wymagają dodatkowej pamięci. Jak rozpoznać, że drzewo nie jest w równowadze? Dla KChD jest on w stanie równowagi, jeżeli spełnione są wszystkie jego opisane wcześniej właściwości. Wyróżnia się 4 rodzaje stanów nierównowagi: 1. Nierównowaga lewo-lewo (LL) 2. Nierównowaga prawo-prawo (RR) 3. Nierównowaga lewo-prawo (LR) 4. Nierównowaga prawo-lewo (RL) Pierwsze dwa stany są również nazywany liniowym (Linia ), ponieważ wizualnie można go przedstawić jako prostą gałąź przechyloną w jedną stronę. Pozostałe dwa nazywane są trójkątami . Aby doprowadzić CCH do stanu równowagi, należy wykonać na nim manipulacje zwane obrotami. Aby zrównoważyć te 4 typy, stosuje się 2 rodzaje obrotów: 1. Dla LL i RR 2. Dla LR i RL Pierwszy typ polega na przeciągnięciu pierwszego węzła w dół tak, aby środek znalazł się na górze. Wizualnie można to przedstawić tak, jakby węzły były w rzeczywistości węzłami na linie zawieszonej na gwoździu: Sam obrót wygląda następująco: w przypadku skomplikowanej rotacji LL, gdy węzły mają również potomków, zasada pozostaje ta sama, ale prawo Dziecko węzła, które staje się rodzicem, staje się lewym/prawym dzieckiem ciągniętego węzła . Przykład: Drugi typ (LR,RL) składa się z 2 etapów i polega na pierwszym doprowadzeniu drzewa do pierwszego stanu, a następnie także ściągnięciu pierwszego węzła w dół: Jeśli spojrzysz na ten rysunek, zauważysz, że po prostu się poruszamy dolny węzeł do góry , czyniąc go „nowym” dziadkiem, a „byłym” dziadkiem albo lewym, albo prawym dzieckiem. Przykład: Przy skomplikowanej rotacji LR/RL, gdy węzły również mają potomków, zasada pozostaje ta sama, ale dawni potomkowie „nowego” rodzica zajmują zwolnione miejsca potomków węzłów potomnych. Przykład: Kod programu czerwono -czarnego drzewa Mówiliśmy o teorii, teraz zobaczmy, jak urządzenie CNC jest zorganizowane w języku programowania JAVA. Mechanika czerwono-czarnego drzewa została zastosowana w szczególności w implementacji TreeMap , ale dla przejrzystości użyjemy bardziej uproszczonego kodu. Wszystko zaczyna się od inicjalizacji prywatnego pola statycznego EMPTY typu Node, które reprezentuje pusty węzeł. Potomkowie PUSTY są również PUSCI. Będzie to dla nas przydatne podczas wstawiania elementu, ponieważ wszystkie arkusze (przedstawione jako NIL na pierwszym rysunku) są inicjowane przez to pole po wstawieniu.

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

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

Struktura klasy zawiera odniesienia do bieżącego węzła current , rodzica bieżącego węzła parent , dziadka bieżącego węzła grand , pradziadka bieżącego węzła Great oraz wskaźnik do korzenia nagłówka drzewa .

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

Po utworzeniu nagłówki są inicjowane do minimalnej wartości Integer.MIN_VALUE, dzięki czemu każdy element będzie zawsze większy od niego, a jego dzieci będą zawsze pustym pustym elementem. Wszystkie elementy będą zawsze większe niż nagłówek, więc pierwsze wstawienie zawsze następuje po prawej stronie nagłówka. Zatem prawe dziecko nagłówka zawsze wskazuje na korzeń drzewa, dlatego jeśli header.right == EMPTY , to drzewo jest puste . Właściwie najciekawsze jest wstawienie elementu . Strategia wstawiania elementu do KCHD jest następująca: 1. Wstaw węzeł i pokoloruj go na czerwono . 2. Jeśli wstawienie doprowadziło do naruszenia właściwości CCH, przemaluj rodzica, wujka lub dziadka i obróć węzły, aby przywrócić drzewo do stanu równowagi. Istnieją 4 główne scenariusze, które mogą się wydarzyć podczas wstawiania elementu, dla wygody nazwijmy ten wstawiony element Z: 1. Z = korzeń (wstawiany element jest korzeniem drzewa) 2. Z.uncle = czerwony (wujek) wstawianego elementu jest czerwony ) 3. Z .uncle = czarny (Linia). Wujek wstawianego elementu jest czarny i po wstawieniu elementu drzewo stało się niezrównoważone w postaci LL lub RR. 4. Z.wujek = czarny (trójkąt). Wujek wstawianego elementu jest czarny i po wstawieniu elementu drzewo stało się niezrównoważone w postaci RL lub LR. Wizualnie wygląda to tak: Przyjrzyjmy się bardziej szczegółowo naprawieniu sytuacji w każdym z 4 możliwych przypadków. Sprawa nr 1 . Po prostu malujemy korzeń na czarno.Przypadek nr 2. Dziadka malujemy na czerwono , a wujka na czarno. Jeśli dziadek węzła jest korzeniem, kolor dziadka jest ponownie pomalowany na czarno. Sprawa nr 3 . Wykonujemy rotację zgodnie z typem nr 1, czyli ściągamy węzeł dziadka. „A” zajmuje miejsce „B”, a następnie ponownie kolorujemy „były” węzeł dziadka na czerwono , a węzeł nadrzędny na czarno . Sprawa nr 4 . Jest najtrudniejszy, bo składa się z kilku etapów. Najpierw wykonujemy rotację według typu nr 2, co prowadzi nas do stanu opisanego w przypadku nr 3, czyli wykonaliśmy rotację, ale drzewo nadal jest w stanie niezrównoważenia, gdyż potomek węzeł „Z” (węzeł „A”) jest czerwony . Oznacza to, że teraz węzeł „A” narusza właściwości kanału CCH i rotacja zostanie przeprowadzona względem jego węzłów nadrzędnych, którymi są: dziadek - węzeł „B”, rodzic - węzeł „Z”. Wykonujemy obrót ponownie, a następnie odmalowujemy „byłego” dziadka na czerwono i rodzica na czarno . Wróćmy do kodu. metoda wstaw().

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

Najtrudniejsza część dzieje się w metodzie reorient() . Metoda ta zajmuje się kolorowaniem węzłów, a także wykonywaniem obrotów, dla których wewnątrz treści odnosi się do metody -> rotate(int item, Node parent) , która z kolei wywołuje metodęrotatWithLeftNode(element Node) lub turnWithRightNode(element Node) metoda, w zależności od tego, czy wartość dodanego elementu jest mniejsza, czy większa od wartości lewego lub prawego dziecka dziadka, czyli rodzica bieżącego elementu. Kod metody:

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

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

Metoda round(int item, Node parent) zostanie wykonana w różny sposób w zależności od tego, co zostało przekazane jako parametr nadrzędny , Great jak w przypadku równoważenia drugiego typu, lub grand jak w przypadku równoważenia pierwszego typu. Kod metody:

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

Metody turnWithLeftNode(element Node) irotWithRightNode (element Node) wykonują następujące działania:

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

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

Przyjrzyjmy się im wyraźnie. Dla pierwszego typu, gdy nie wpiszemy warunku (item < grand.element != item < parent.element) rotacja będzie wyglądać następująco: Dla drugiego typu, gdy przekażemy parametr grand (dziadek) do parametru obrót będzie wyglądał następująco: Należy pamiętać, że węzeł nadrzędny został nadpisany i teraz wskazuje na nasz bieżący plik . Ponieważ po zakończonym obrocie drzewo nadal nie jest w równowadze, ponownie wykonujemy rotację według pierwszego typu , jak na poprzednim obrazku. Może pojawić się pytanie: dlaczego w przypadku wywołania metody turnWithLeftNode tak naprawdę obracamy węzły w prawo, a w przypadku metody turnWithRightNode w lewo? Dzieje się tak, ponieważ rotatWithLeftNode implikuje rotację z lewym dzieckiem przekazanego węzła, odpowiednio -rotatWithRightNode z prawym. W nazwie metody nie jest brany pod uwagę kierunek obrotu . W ten prosty sposób rotacja jest przeprowadzana także dla bardziej skomplikowanych przypadków. Przydatne materiały i linki: 1. Artykuł w Wiki 2. Czerwono-czarny wizualizator drzewa 3. Fajny artykuł o KChD 4. Pytanie, czy KChD jest rzeczywiście zbalansowany 5. Kod programu KChD, który nie ma konta JavaRush 6. Znakomity film autorstwa bardzo utalentowany nauczyciel (mówi o AVL, ale zasada jest podobna do KChD) 7. Seria filmów o urządzeniu, mechanizmie wstawiania i obracania Kontakty autora: Telegram Mail: realyte95@gmail.com