Arbre rouge-noir. Propriétés, principes d'organisation, mécanisme d'insertion.

Le concept d' un arbre rouge-noir Un arbre rouge-noir est un type d'arbre binaire dont l'essence principale est la capacité de s'auto-équilibrer. Il existe plusieurs types d'arbres auto-équilibrés, mais dans cet article, nous n'aborderons que l'arbre rouge-noir ou (RCB). L'équilibre est obtenu en introduisant un attribut supplémentaire du nœud de l'arbre - « couleur ». Chaque nœud de l'arbre, en plus de l'élément, stocke 1 bit d'information indiquant si le nœud est rouge ou noir, et cela peut être non seulement la couleur, mais aussi toute autre information permettant de distinguer un type de nœud d'un autre. Par exemple, 1 ou 0, vrai ou faux, etc. Principes d'organisation (propriétés) du KChD : 1. La racine de l'arbre est noire . 2. Toutes les feuilles qui ne contiennent pas de données sont noires 3. Les deux enfants de chaque nœud rouge sont noirs 4. La profondeur des nœuds noirs est la même pour n'importe quel sous- arbre Les principales opérations effectuées sur un arbre sont : 1. Rechercher 2. Insérer un element 3 Supprimer un élément (delete) Les deux dernières opérations entraînent évidemment un changement dans la structure de l'arbre, et donc, leur résultat peut être un déséquilibre dans l'arbre. Complexité temporelle et spatiale. Les opérations d'insertion, de suppression et de recherche pour le QCD de complexité temporelle sont O(log n) , où n est le nombre de nœuds dans l'arbre, car pour les exécuter, nous devons accéder au nœud souhaité, en supprimant l'un des sous-arbres à chaque fois. étape. Dans le cas où l'insertion ou la suppression entraîne une violation des propriétés du CCH, il est nécessaire d'effectuer un rééquilibrage. L'équilibrage se compose de deux opérations : la recoloration O(1) et la rotation O(1). Chaque opération d'équilibrage prend un temps constant, puisqu'elle consiste à réécrire les liens des éléments enfants et parents, ainsi que des informations sur leur couleur. Cependant, lors de l'insertion ou de la suppression d'un élément, une situation peut survenir dans laquelle l'arbre doit être équilibré du nœud le plus bas jusqu'à la racine. Puisqu'il est garanti que la hauteur maximale d'un CCH composé de n nœuds n'est pas supérieure à 2log(n + 1), alors dans le pire des cas, le rééquilibrage peut nécessiter des opérations log(n). Le coût mémoire de l'insertion est O(1) puisqu'elle implique uniquement la création d'un nouveau nœud ; les opérations d'équilibrage et de repeinture ne nécessitent pas de mémoire supplémentaire. Comment savoir si un arbre est déséquilibré ? Pour KChD, il est en état d’équilibre si toutes ses propriétés décrites précédemment sont remplies. Il existe 4 types d'états de déséquilibre : 1. Déséquilibre gauche-gauche (LL) 2. Déséquilibre droite-droite (RR) 3. Déséquilibre gauche-droite (LR) 4. Déséquilibre droite-gauche (RL) Les deux premiers états sont également appelé linéaire (Ligne ), car visuellement, il peut être représenté comme une branche droite inclinée d'un côté. Les deux autres sont appelés triangles . Pour amener le CCH en état d'équilibre, il est nécessaire d'effectuer sur celui-ci des manipulations appelées rotations. Pour équilibrer ces 4 types, 2 types de rotations sont utilisés : 1. Pour LL et RR 2. Pour LR et RL Le premier type consiste à tirer le premier nœud vers le bas pour que le milieu soit en haut. Visuellement, cela peut être représenté comme si les nœuds étaient en réalité des nœuds sur une corde suspendue à un clou : La rotation elle-même ressemble à ceci : Avec une rotation LL compliquée, lorsque les nœuds ont aussi des descendants, le principe reste le même, mais le droit l'enfant du nœud, qui devient parent, devient l'enfant gauche/droite du nœud en cours d'extraction . Exemple : Le deuxième type (LR,RL) se compose de 2 étapes et consiste d'abord à amener l'arbre au premier état, puis à tirer également le premier nœud vers le bas : Si vous regardez cette figure, vous remarquerez que nous déplaçons simplement du nœud inférieur vers le haut , ce qui en fait le « nouveau » grand-père et faisant de « l'ancien » grand-père un enfant de gauche ou de droite. Exemple : Avec une rotation LR/RL compliquée, lorsque les nœuds ont aussi des descendants, le principe reste le même, mais les anciens descendants du « nouveau » parent prennent les places libérées des descendants des nœuds enfants. Exemple : code de programme d'un arbre rouge- noir Nous avons parlé de la théorie, voyons maintenant comment le dispositif CNC est organisé dans le langage de programmation JAVA. La mécanique des arbres rouge-noir est notamment utilisée dans l'implémentation TreeMap , mais pour plus de clarté, nous utiliserons un code plus simplifié. Tout commence par l'initialisation d'un champ statique privé EMPTY de type Node, qui représente un nœud vide. Les descendants de EMPTY sont également EMPTY. Il nous sera utile lors de l'insertion d'un élément, puisque toutes les feuilles (représentées par NIL sur la première figure) sont initialisées par ce champ lors de l'insertion.

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

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

La structure de classe contient des références au nœud actuel current , au parent du nœud actuel parent , au grand-père du nœud actuel grand , à l'arrière-grand-père du nœud actuel great et un pointeur vers la racine de l'en -tête de l'arborescence .

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

Une fois créés, les en-têtes sont initialisés à la valeur minimale Integer.MIN_VALUE afin que tout élément soit toujours supérieur à celle-ci et que ses enfants soient toujours un élément EMPTY vide. Tous les éléments seront toujours plus grands que l'en-tête, donc la première insertion se produit toujours à droite de l'en-tête. Ainsi, l'enfant droit de header pointe toujours vers la racine de l'arborescence, donc si header.right == EMPTY , alors l'arborescence est vide . En fait, le plus intéressant est d'insérer un élément . La stratégie pour insérer un élément dans le KCHD est la suivante : 1. Insérez un nœud et colorez-le en rouge . 2. Si l'insertion a entraîné une violation des propriétés du CCH, repeignez le parent, l'oncle ou le grand-père et faites pivoter les nœuds pour ramener l'arbre dans un état d'équilibre. Il y a 4 scénarios principaux qui peuvent se produire lors de l'insertion d'un élément, pour plus de commodité appelons cet élément inséré comme Z : 1. Z = racine (l'élément inséré est la racine de l'arbre) 2. Z.uncle = rouge (l'oncle de l'élément en cours d'insertion est rouge ) 3. Z .oncle = noir (Ligne). L'oncle de l'élément inséré est noir et après l'insertion de l'élément, l'arbre s'est déséquilibré sous la forme de LL ou RR. 4. Z.oncle = noir (triangle). L'oncle de l'élément inséré est noir et après avoir inséré l'élément, l'arbre s'est déséquilibré sous la forme de RL ou LR. Visuellement, cela ressemble à ceci : Voyons plus en détail comment corriger la situation pour chacun des 4 cas possibles. Cas n°1 . On peint juste la racine en noir. Cas n°2. On peint le grand-père en rouge , et l'oncle en noir. Si le grand-père du nœud est la racine, alors la couleur du grand-père est à nouveau peinte en noir. Cas n°3 . Nous effectuons une rotation selon le type n°1, c'est-à-dire que nous tirons le nœud du grand-père vers le bas. « A » prend la place de « B », puis on recolore « l'ancien » nœud grand-père en rouge et le nœud parent en noir . Cas n°4 . C'est la plus difficile car elle se compose de plusieurs étapes. Tout d'abord, nous effectuons une rotation selon le type n°2, ce qui nous amène à l'état décrit dans le cas n°3, c'est-à-dire que nous avons effectué une rotation, mais l'arbre est toujours en état de déséquilibre, puisque le descendant de le nœud « Z » (nœud « A ») est rouge . C'est-à-dire que maintenant le nœud « A » viole les propriétés du CCH et la rotation sera effectuée par rapport à ses nœuds parents, qui sont : grand-père - nœud « B », parent - nœud « Z ». Nous effectuons à nouveau la rotation, puis repeignons « l'ancien » grand-père en rouge et le parent en noir . Revenons au code. Méthode insert()

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

La partie la plus difficile se produit dans la méthode reorient() . Cette méthode traite de la coloration des nœuds, ainsi que de l'exécution de rotations, pour lesquelles à l'intérieur du corps, elle fait référence à la méthode -> rotate(int item, Node parent) , qui à son tour appelle rotateWithLeftNode(Node element) ou rotateWithRightNode(Node element) méthode , selon que la valeur de l'élément ajouté est inférieure ou supérieure à la valeur de l'enfant gauche ou droit du grand-père, c'est-à-dire le parent de l'élément courant. Code de la méthode :

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

La méthode rotate(int item, Node parent) sera exécutée différemment selon ce qui a été passé comme paramètre parent , great comme dans le deuxième type d'équilibrage, ou grand comme dans le premier type d'équilibrage. Code de la méthode :

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

Les méthodes rotateWithLeftNode(Node element) et rotateWithRightNode(Node element) effectuent les actions suivantes :

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

Regardons-les clairement. Pour le premier type, lorsque l'on ne saisit pas la condition (item < grand.element != item < parent.element) , la rotation ressemblera à ceci : Pour le deuxième type, lorsque l'on passe le paramètre grand (grand-père) au paramètre, la rotation ressemblera à ceci : Veuillez noter que le nœud parent a été écrasé et pointe désormais vers notre . Puisque l'arbre n'est toujours pas en équilibre après la rotation terminée, nous effectuons à nouveau la rotation selon le premier type , comme dans l'image précédente. La question peut se poser : pourquoi, lorsque la méthode rotateWithLeftNode est appelée , faisons-nous réellement pivoter les nœuds vers la droite, et lorsque rotateWithRightNode - vers la gauche ? En effet, rotatWithLeftNode implique une rotation avec l'enfant gauche du nœud passé, rotateWithRightNode , respectivement, avec celui de droite. Le sens de rotation n'est pas pris en compte dans le nom de la méthode . De cette manière simple, une rotation est également effectuée pour les cas plus complexes. Matériel et liens utiles : 1. Article wiki 2. Visualiseur d'arbre rouge-noir 3. Bel article sur KChD 4. Question de savoir si KChD est vraiment équilibré 5. Code du programme KChD, qui n'a pas de compte JavaRush 6. Excellente vidéo de un professeur très talentueux (parle d'AVL, mais le principe est similaire à KChD) 7. Une série de vidéos sur l'appareil, le mécanisme d'insertion et de rotation Contacts de l'auteur : Telegram Mail : realyte95@gmail.com