Wit abang-ireng. Properties, prinsip organisasi, mekanisme penyisipan.

Konsep wit abang -ireng Wit abang-ireng minangka jinis wit binar, inti utama yaiku kemampuan kanggo ngimbangi diri. Ana sawetara jinis wit sing ngimbangi diri, nanging ing artikel iki kita mung bakal ndemek wit abang-ireng utawa (RCB). Keseimbangan digayuh kanthi ngenalake atribut tambahan saka simpul wit - "werna". Saben simpul wit, saliyane kanggo unsur, nyimpen 1 dicokot informasi bab apa simpul abang utawa ireng, lan iki bisa uga ora mung werna, nanging uga informasi liyane sing ngidini siji kanggo mbedakake siji jinis simpul saka liyane. Contone, 1 utawa 0, bener utawa salah, etc. Prinsip organisasi (properti) saka KChD: 1. ROOT saka wit ireng . 2. Kabeh godhong sing ora ngemot data ireng 3. Loro-lorone bocah saben simpul abang ireng 4. Ambane ing simpul ireng padha kanggo subtree apa wae Operasi utama sing ditindakake ing wit yaiku: 1. Telusuri 2. Lebokake an unsur 3 Mbusak unsur (mbusak) Loro operasi pungkasan temenan mimpin kanggo owah-owahan ing struktur wit, lan mulane, asil sing bisa dadi boten seimbang kalebet ing wit. Kompleksitas Wektu lan Ruang. Operasi penyisipan, pambusakan lan telusuran kanggo Kompleksitas Wektu QCD yaiku O(log n) , ing ngendi n minangka jumlah simpul ing wit, amarga kanggo nindakake, kita kudu tekan simpul sing dikarepake, mbuwang siji subtree ing saben. langkah. Ing kasus nalika selipan utawa pambusakan ndadékaké nglanggar sifat CCH, iku perlu kanggo nindakake rebalancing. Balancing kasusun saka rong operasi: recoloring O (1) lan rotasi O (1). Saben operasi imbangan mbutuhake wektu sing tetep, amarga kalebu nulis ulang tautan unsur anak lan wong tuwa, uga informasi babagan warna. Nanging, nalika nglebokake utawa mbusak unsur, bisa uga ana kahanan sing wit kudu diimbangi saka simpul paling ngisor nganti oyod. Wiwit iku dijamin sing dhuwur maksimum CCH kasusun saka n kelenjar ora luwih saka 2log(n + 1), banjur ing kasus paling awon, rebalancing bisa njupuk log (n) - operasi. Biaya selipan memori yaiku O(1) amarga mung nggawe simpul anyar; operasi imbangan lan repainting ora mbutuhake memori tambahan. Kepiye carane ngerti yen wit ora seimbang? Kanggo KChD, ana ing imbangan yen kabeh sifat sing diterangake sadurunge ketemu. Ana 4 jinis kahanan ora seimbang: 1. Ketidakseimbangan kiwa-kiwa (LL) 2. Ketidakseimbangan tengen-tengen (RR) 3. Ketimpangan kiwa-tengen (LR) 4. Ketimpangan kiwa-tengen (RL) Loro negara pisanan uga disebut linear (garis), amarga kanthi visual bisa diwakili minangka cabang lurus sing miring menyang sisih siji. Loro sing isih ana diarani segitiga . Kanggo nggawa CCH menyang negara imbangan, iku perlu kanggo nindakake manipulasi ing disebut rotasi. Kanggo ngimbangi 4 jinis kasebut, 2 jinis rotasi digunakake: 1. Kanggo LL lan RR 2. Kanggo LR lan RL Jinis pisanan yaiku narik simpul pisanan mudhun supaya tengah ana ing ndhuwur. Secara visual, iki bisa diwakili kaya-kaya simpul kasebut pancen simpul ing tali sing digantung ing pucuk: Rotasi kasebut katon kaya mangkene: Kanthi rotasi LL sing rumit, nalika simpul uga duwe turunan, prinsip tetep padha, nanging sing bener. anak simpul, sing dadi wong tuwa, dadi anak kiwa / tengen saka simpul sing ditarik . Conto: Tipe kapindho (LR,RL) kasusun saka 2 orane tumrap sekolah lan kasusun ing pisanan nggawa wit menyang negara pisanan, lan banjur uga narik simpul pisanan mudhun: Yen katon ing tokoh iki, sampeyan bakal sok dong mirsani sing kita mung obah. simpul ngisor menyang ndhuwur , nggawe mbah "anyar", lan nggawe mbah "mantan" salah siji anak kiwa utawa tengen. Conto: Kanthi rotasi LR / RL sing rumit, nalika simpul uga duwe keturunan, prinsip tetep padha, nanging mantan keturunan saka wong tuwa "anyar" njupuk panggonan sing dikosongake saka keturunan kelenjar anak. Conto: Kode program saka wit abang-ireng Kita ngomong babagan teori, saiki ayo ndeleng carane piranti CNC diatur ing basa program JAVA. Mekanika wit abang-ireng digunakake, utamane, ing implementasine TreeMap , nanging kanggo gamblang kita bakal nggunakake kode sing luwih disederhanakake. Iku kabeh diwiwiti kanthi nginisialisasi kolom statis pribadi EMPTY saka jinis Node, sing nuduhake simpul kosong. Turunane KOSONG uga KOSONG. Iku bakal migunani kanggo kita nalika nglebokake unsur, wiwit kabeh sheets (diwakili minangka NIL ing tokoh pisanan) initialized dening lapangan iki nalika selipan.

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

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

Struktur kelas ngemot referensi kanggo arus simpul saiki , wong tuwa saka simpul saiki , mbah kakung saka simpul saiki , mbah buyut saka simpul saiki , lan pointer menyang root header wit .

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

Nalika digawe, header diinisialisasi menyang nilai minimal Integer.MIN_VALUE supaya unsur apa wae bakal luwih gedhe tinimbang, lan anak-anake bakal dadi unsur KOSONG. Kabeh unsur bakal tansah luwih gedhe tinimbang header, supaya sisipan pisanan tansah ana ing sisih tengen header. Mangkono, anak tengen header tansah nunjuk menyang ROOT wit, mulane, yen header.right == KOSONG , banjur wit kosong . Bener, sing paling menarik yaiku nglebokake unsur . Strategi kanggo nglebokake unsur menyang KCHD kaya ing ngisor iki: 1. Lebokake simpul lan wernane abang . 2. Yen sisipan mimpin kanggo nglanggar sifat saka CCH, banjur repaint tiyang sepah, paman utawa mbah kakung lan muter kelenjar kanggo nggawa wit bali menyang negara imbangan. Ana 4 skenario utama sing bisa kedadeyan nalika nglebokake unsur, supaya luwih gampang diarani unsur sing dilebokake iki minangka Z: 1. Z = oyot (unsur sing dilebokake yaiku oyod wit) 2. Z.paman = abang (paman). saka unsur kang dilebokake abang ) 3. Z .paman = ireng (Garis). Pakdhe unsur sing dilebokake ireng lan sawise dilebokake unsur wit dadi ora seimbang wujude LL utawa RR. 4. Z.paman = ireng (segitiga). Pakdhe unsur sing dilebokake ireng lan sawise dilebokake unsur wit dadi ora seimbang wujude RL utawa LR. Visual katon kaya iki: Ayo dadi katon ing liyane rinci ing mbenerake kahanan kanggo saben 4 kasus bisa. Kasus nomer 1 . We mung Paint werna ireng. Kasus No.. 2. We Paint simbah abang , lan pakdhe ireng. Yen simbah simpul iku oyod, banjur warna simbah maneh dicet ireng. Kasus No. 3 . Kita nindakake rotasi miturut jinis nomer 1, yaiku, narik simpul simbah mudhun. "A" njupuk Panggonan "B", lan banjur kita recolor "mantan" simpul mbah abang lan tuwane simpul ireng . Kasus No. 4 . Paling angel amarga kasusun saka sawetara tahapan. Kaping pisanan, kita nindakake rotasi miturut jinis nomer 2, sing ndadékaké kita menyang negara sing diterangake ing kasus No. simpul "Z" (simpul "A") abang . Dadi, saiki simpul "A" nglanggar sifat CCH lan rotasi bakal ditindakake relatif marang kelenjar induk, yaiku: mbah kakung - simpul "B", wong tuwa - simpul "Z". We nindakake rotasi maneh, lan banjur repaint "mantan" mbah kakung abang lan tuwane ireng . Ayo bali menyang kode. metode 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);
    }

Sisih paling angel kedadeyan ing metode reorient () . Cara iki gegayutan karo simpul pewarnaan, uga nindakake rotasi, sing ing jero awak kasebut nuduhake metode -> rotate(int item, Node parent) , sing banjur diarani rotateWithLeftNode(elemen Node) utawa rotateWithRightNode(elemen Node) cara , gumantung ing apa Nilai saka unsur ditambahaké kurang saka utawa luwih saka Nilai saka anak kiwa utawa tengen mbah kakung, sing, tiyang sepah saka unsur saiki. Kode metode:

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

Cara rotate(int item, Node parent) bakal dieksekusi kanthi beda-beda gumantung saka apa sing dilewati minangka parameter induk , apik kaya ing jinis imbangan kapindho, utawa gedhe kaya ing jinis imbangan pisanan. Kode metode:

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

Cara rotateWithLeftNode(elemen Node) lan rotateWithRightNode(elemen Node) nindakake tumindak ing ngisor iki:

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

Ayo padha ndeleng kanthi cetha. Kanggo jinis pisanan, nalika kita ora ngetik kondisi (item < grand.element != item < parent.element) , rotasi bakal katon kaya iki: Kanggo jinis kapindho, nalika kita pass parameter grand (mbah) menyang parameter, rotasi bakal katon kaya iki: Wigati dimangerteni menawa simpul induk wis ditindhes lan saiki nuduhake kita saiki . Wiwit wit isih ora imbangan sawise rotasi rampung, kita maneh nindakake rotasi miturut jinis pisanan , kaya ing gambar sadurunge. Pitakonan bisa uga muncul: kenapa, nalika metode rotateWithLeftNode diarani , apa kita bener-bener muter simpul ing sisih tengen, lan nalika rotateWithRightNode - ngiwa? Iki amarga rotatWithLeftNode nuduhake rotasi karo anak kiwa saka simpul sing dilewati, rotateWithRightNode , karo sing tengen. Arah rotasi ora dianggep ing jeneng metode . Kanthi cara sing prasaja iki, rotasi uga ditindakake kanggo kasus sing luwih rumit. Bahan lan pranala sing migunani: 1. Artikel Wiki 2. Visualizer wit abang-ireng 3. Artikel sing apik babagan KChD 4. Pitakonan babagan apa KChD pancen seimbang 5. Kode program KChD, sing ora duwe akun JavaRush 6. Video sing apik banget dening guru sing bakat banget (ngomong babagan AVL, nanging prinsip padha karo KChD) 7. Seri video babagan piranti, selipan lan mekanisme rotasi Kontak Pengarang: Telegram Mail: realyte95@gmail.com