Pula-itim na puno. Mga katangian, mga prinsipyo ng organisasyon, mekanismo ng pagpasok.

Ang konsepto ng isang pulang -itim na puno Ang pulang-itim na puno ay isang uri ng binary tree, ang pangunahing kakanyahan nito ay ang kakayahang balansehin ang sarili. Mayroong ilang mga uri ng self-balancing tree, ngunit sa artikulong ito ay hahawakan lamang natin ang pulang-itim na puno o (RCB). Ang balanse ay nakakamit sa pamamagitan ng pagpapakilala ng karagdagang katangian ng tree node - "kulay". Ang bawat tree node, bilang karagdagan sa elemento, ay nag-iimbak ng 1 bit ng impormasyon tungkol sa kung ang node ay pula o itim, at ito ay maaaring hindi lamang ang kulay, kundi pati na rin ang anumang iba pang impormasyon na nagpapahintulot sa isa na makilala ang isang uri ng node mula sa iba. Halimbawa, 1 o 0, totoo o mali, atbp. Mga Prinsipyo ng organisasyon (mga katangian) ng KChD: 1. Ang ugat ng puno ay itim . 2. Ang lahat ng dahon na walang data ay itim 3. Ang parehong mga bata ng bawat pulang node ay itim 4. Ang lalim ng mga itim na node ay pareho para sa anumang subtree Ang mga pangunahing operasyon na ginagawa sa isang puno ay: 1. Maghanap 2. Magpasok ng isang elemento 3 Pagtanggal ng elemento (tanggalin) Ang huling dalawang operasyon ay malinaw na humahantong sa isang pagbabago sa istraktura ng puno, at samakatuwid, ang kanilang resulta ay maaaring isang kawalan ng timbang sa puno. Pagiging kumplikado ng Oras at Space. Ang mga operasyon ng pagpasok, pagtanggal at paghahanap para sa Time Complexity QCD ay O(log n) , kung saan ang n ay ang bilang ng mga node sa puno, dahil upang maisagawa ang mga ito kailangan nating makarating sa nais na node, na itinatapon ang isa sa mga subtree sa bawat isa. hakbang. Sa kaso kung saan ang pagpapasok o pagtanggal ay humahantong sa isang paglabag sa mga katangian ng CCH, kinakailangang magsagawa ng rebalancing. Ang pagbabalanse ay binubuo ng dalawang operasyon: muling pagkulay ng O(1) at pag-ikot ng O(1). Ang bawat operasyon ng pagbabalanse ay tumatagal ng patuloy na oras, dahil binubuo ito ng muling pagsusulat ng mga link ng mga elemento ng bata at magulang, pati na rin ang impormasyon tungkol sa kanilang kulay. Gayunpaman, kapag nagpasok o nagtanggal ng elemento, maaaring lumitaw ang isang sitwasyon kung saan kailangang balansehin ang puno mula sa pinakamababang node hanggang sa ugat. Dahil ginagarantiyahan na ang maximum na taas ng isang CCH na binubuo ng n node ay hindi hihigit sa 2log(n + 1), kung gayon sa pinakamasamang kaso, ang rebalancing ay maaaring tumagal ng log(n) - mga operasyon. Ang halaga ng memorya ng pagpapasok ay O(1) dahil nagsasangkot lamang ito ng paglikha ng bagong node; hindi nangangailangan ng karagdagang memorya ang mga pagpapatakbo ng pagbabalanse at pagpipinta. Paano mo malalaman kung ang isang puno ay hindi balanse? Para sa KChD, ito ay nasa isang estado ng balanse kung ang lahat ng mga katangian nito na inilarawan kanina ay natutugunan. Mayroong 4 na uri ng imbalance states: 1. Kaliwa-kaliwang imbalance (LL) 2. Kanan-kanang imbalance (RR) 3. Kaliwa-kanang imbalance (LR) 4. Right-left imbalance (RL) Ang unang dalawang estado ay din tinatawag na linear (Line ), dahil sa nakikita ay maaari itong ilarawan bilang isang tuwid na sanga na nakahilig sa isang gilid. Ang natitirang dalawa ay tinatawag na mga tatsulok . Upang dalhin ang CCH sa isang estado ng balanse, kinakailangan na magsagawa ng mga manipulasyon dito na tinatawag na mga pag-ikot. Upang balansehin ang 4 na uri na ito, 2 uri ng pag-ikot ang ginagamit: 1. Para sa LL at RR 2. Para sa LR at RL Ang unang uri ay hilahin ang unang node pababa upang ang gitna ay nasa itaas. Sa paningin, maaari itong ilarawan na parang ang mga node ay talagang mga node sa isang lubid na nakabitin sa isang pako: Ang pag-ikot mismo ay ganito: Sa isang kumplikadong pag-ikot ng LL, kapag ang mga node ay mayroon ding mga inapo, ang prinsipyo ay nananatiling pareho, ngunit ang tama anak ng node, na nagiging magulang, ay nagiging kaliwa/kanang anak ng node na hinihila . Halimbawa: Ang pangalawang uri (LR,RL) ay binubuo ng 2 yugto at binubuo sa unang pagdadala ng puno sa unang estado, at pagkatapos ay hilahin din ang unang node pababa: Kung titingnan mo ang figure na ito, mapapansin mo na kami ay gumagalaw lang. ang ibabang node sa itaas , ginagawa itong "bagong" lolo, at ginagawang kaliwa o kanang anak ang "dating" lolo. Halimbawa: Sa isang kumplikadong pag-ikot ng LR/RL, kapag ang mga node ay mayroon ding mga inapo, ang prinsipyo ay nananatiling pareho, ngunit ang mga dating inapo ng "bagong" magulang ay kumukuha ng mga bakanteng lugar ng mga inapo ng mga child node. Halimbawa: Program code ng isang pulang -itim na puno Napag-usapan namin ang tungkol sa teorya, ngayon tingnan natin kung paano nakaayos ang CNC device sa Java programming language. Ginagamit ang red-black tree mechanics, sa partikular, sa pagpapatupad ng TreeMap , ngunit para sa kalinawan ay gagamit kami ng mas pinasimpleng code. Nagsisimula ang lahat sa pamamagitan ng pagsisimula ng pribadong static na field na EMPTY ng uri ng Node, na kumakatawan sa isang walang laman na node. Ang mga kaapu-apuhan ni EMPTY ay EMPTY din. Ito ay magiging kapaki-pakinabang sa amin kapag naglalagay ng isang elemento, dahil ang lahat ng mga sheet (kinakatawan bilang NIL sa unang figure) ay sinisimulan ng field na ito sa pagpasok.

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

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

Ang istraktura ng klase ay naglalaman ng mga reference sa kasalukuyang node current , ang magulang ng kasalukuyang node parent , ang lolo ng kasalukuyang node grand , ang lolo sa tuhod ng kasalukuyang node great , at isang pointer sa ugat ng tree header .

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

Kapag ginawa, ang mga header ay sinisimulan sa pinakamababang halaga na Integer.MIN_VALUE upang ang anumang elemento ay palaging mas malaki kaysa dito, at ang mga anak nito ay palaging isang walang laman na EMPTY na elemento. Ang lahat ng mga elemento ay palaging magiging mas malaki kaysa sa header, kaya ang unang pagpasok ay palaging nangyayari sa kanan ng header. Kaya, ang tamang anak ng header ay palaging tumuturo sa ugat ng puno, samakatuwid, kung header.right == EMPTY , kung gayon ang puno ay walang laman . Sa totoo lang, ang pinakakawili-wiling bagay ay ang pagpasok ng elemento . Ang diskarte para sa pagpasok ng elemento sa KCHD ay ang mga sumusunod: 1. Magpasok ng node at kulayan ito ng pula . 2. Kung ang pagpasok ay humantong sa isang paglabag sa mga ari-arian ng CCH, pagkatapos ay muling pintura ang magulang, tiyuhin o lolo at paikutin ang mga node upang maibalik ang puno sa balanse. Mayroong 4 na pangunahing senaryo na maaaring mangyari kapag nagpasok ng isang elemento, para sa kaginhawahan ay tawagin natin itong nakasingit na elemento bilang Z: 1. Z = ugat (ang elementong ipinapasok ay ang ugat ng puno) 2. Z.tiyo = pula (ang tiyuhin ng elementong ipinapasok ay pula ) 3. Z .tiyuhin = itim (Linya). Ang tiyuhin ng ipinasok na elemento ay itim at pagkatapos ipasok ang elemento ay naging hindi balanse ang puno sa anyo ng LL o RR. 4. Z.tiyuhin = itim (tatsulok). Ang tiyuhin ng ipinasok na elemento ay itim at pagkatapos ipasok ang elemento ay naging hindi balanse ang puno sa anyo ng RL o LR. Biswal na ganito ang hitsura: Tingnan natin nang mas detalyado ang pagwawasto sa sitwasyon para sa bawat isa sa 4 na posibleng kaso. Kaso No. 1 . Pininturahan lang namin ng itim ang ugat. Case No. 2. Pinintura namin ang lolo ng pula , at ang tiyuhin ay itim. Kung ang lolo ng node ay ang ugat, kung gayon ang kulay ng lolo ay muling pininturahan ng itim. Kaso No. 3 . Nagsasagawa kami ng pag-ikot ayon sa uri No. 1, iyon ay, hinihila namin ang buhol ng lolo. Ang "A" ay pumapalit sa "B", at pagkatapos ay muling kulayan namin ang "dating" lolo node na pula at ang parent node ay itim . Kaso No. 4 . Ito ang pinakamahirap dahil binubuo ito ng ilang yugto. Una, nagsasagawa kami ng pag-ikot ayon sa uri No. 2, na humahantong sa amin sa estado na inilarawan sa kaso No. 3, iyon ay, nagsagawa kami ng isang pag-ikot, ngunit ang puno ay nasa isang estado ng kawalan ng timbang, dahil ang inapo ng ang node "Z" (node ​​​​"A") ay pula . Iyon ay, ngayon ang node "A" ay lumalabag sa mga katangian ng CCH at ang pag-ikot ay isasagawa kaugnay sa mga parent node nito, na: lolo - node "B", magulang - node "Z". Isinasagawa namin muli ang pag-ikot, at pagkatapos ay pininturahan muli ang "dating" lolo na pula at ang magulang ay itim . Balik tayo sa code. insert() na pamamaraan

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

Ang pinakamahirap na bahagi ay nangyayari sa reorient() na pamamaraan . Ang pamamaraang ito ay tumatalakay sa mga node ng pangkulay, pati na rin sa pagsasagawa ng mga pag-ikot, kung saan sa loob ng katawan ay tumutukoy ito sa -> rotate(int item, Node parent) method , na tinatawag naman ang rotateWithLeftNode(Node element) o rotateWithRightNode(Node element) method , depende sa kung ang halaga ng idinagdag na elemento ay mas mababa o mas malaki kaysa sa halaga ng kaliwa o kanang anak ng lolo, iyon ay, ang magulang ng kasalukuyang elemento. Code ng pamamaraan:

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

Ang paraan ng rotate(int item, Node parent) ay isasagawa sa ibang paraan depende sa kung ano ang ipinasa bilang parent parameter , mahusay tulad ng sa pangalawang uri ng pagbabalanse, o engrande tulad ng sa unang uri ng pagbabalanse. Code ng pamamaraan:

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

Ang rotateWithLeftNode(Node element) at rotateWithRightNode(Node element) na mga pamamaraan ay nagsasagawa ng mga sumusunod na aksyon:

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

Tingnan natin sila ng malinaw. Para sa unang uri, kapag hindi namin ipinasok ang kundisyon (item < grand.element != item < parent.element) , ang pag-ikot ay magiging ganito: Para sa pangalawang uri, kapag ipinasa namin ang grand (lolo) na parameter sa parameter, ang pag-ikot ay magiging ganito: Pakitandaan na ang parent node ay na-overwrite at ngayon ay tumuturo sa aming kasalukuyang . Dahil ang puno ay hindi pa rin balanse pagkatapos ng nakumpletong pag-ikot, muli kaming nagsasagawa ng pag-ikot ayon sa unang uri , tulad ng sa nakaraang larawan. Ang tanong ay maaaring lumitaw: bakit, kapag ang rotateWithLeftNode na pamamaraan ay tinatawag na , talagang iniikot ba natin ang mga node sa kanan, at kapag rotateWithRightNode - sa kaliwa? Ito ay dahil ang rotatWithLeftNode ay nagpapahiwatig ng pag-ikot sa kaliwang anak ng naipasa na node, rotateWithRightNode , ayon sa pagkakabanggit, gamit ang kanan. Ang direksyon ng pag-ikot ay hindi isinasaalang-alang sa pangalan ng pamamaraan . Sa simpleng paraan na ito, ang pag-ikot ay isinasagawa din para sa mas kumplikadong mga kaso. Mga kapaki-pakinabang na materyales at link: 1. Artikulo ng Wiki 2. Red-black tree visualizer 3. Magandang artikulo tungkol sa KChD 4. Tanong tungkol sa kung talagang balanse ang KChD 5. KChD program code, na walang JavaRush account 6. Napakahusay na video ni isang napakatalino na guro (nag-uusap tungkol sa AVL, ngunit ang prinsipyo ay katulad ng KChD) 7. Isang serye ng mga video tungkol sa device, insertion at rotation mechanism Mga contact ng may-akda: Telegram Mail: realyte95@gmail.com