Pokok merah-hitam. Sifat, prinsip organisasi, mekanisme penyisipan.

Konsep pokok merah -hitam Pokok merah-hitam adalah sejenis pokok binari, intipati utamanya ialah keupayaan untuk mengimbangi diri. Terdapat beberapa jenis pokok pengimbangan diri, tetapi dalam artikel ini kita hanya akan menyentuh pokok merah-hitam atau (RCB). Keseimbangan dicapai dengan memperkenalkan atribut tambahan nod pokok - "warna". Setiap nod pokok, sebagai tambahan kepada elemen, menyimpan 1 bit maklumat tentang sama ada nod itu merah atau hitam, dan ini bukan sahaja warna, tetapi juga sebarang maklumat lain yang membolehkan seseorang membezakan satu jenis nod daripada yang lain. Contohnya, 1 atau 0, benar atau salah, dsb. Prinsip organisasi (sifat) KChD: 1. Akar pokok berwarna hitam . 2. Semua daun yang tidak mengandungi data adalah hitam 3. Kedua-dua anak bagi setiap nod merah berwarna hitam 4. Kedalaman dalam nod hitam adalah sama untuk mana-mana subpokok Operasi utama yang dilakukan pada pokok ialah: 1. Cari 2. Masukkan an elemen 3 Memadam elemen (padam) Dua operasi terakhir jelas membawa kepada perubahan dalam struktur pokok, dan oleh itu, keputusannya mungkin ketidakseimbangan dalam pokok. Kerumitan Masa dan Ruang. Operasi sisipan, pemadaman dan carian untuk QCD Kerumitan Masa ialah O(log n) , di mana n ialah bilangan nod dalam pepohon, kerana untuk melaksanakannya kita perlu pergi ke nod yang dikehendaki, membuang salah satu subpokok pada setiap langkah. Dalam kes di mana sisipan atau pemadaman membawa kepada pelanggaran sifat CCH, adalah perlu untuk melakukan pengimbangan semula. Pengimbangan terdiri daripada dua operasi: mewarna semula O(1) dan putaran O(1). Setiap operasi pengimbangan mengambil masa yang berterusan, kerana ia terdiri daripada menulis semula pautan elemen anak dan ibu bapa, serta maklumat tentang warnanya. Walau bagaimanapun, apabila memasukkan atau memadam elemen, situasi mungkin timbul di mana pokok itu perlu diseimbangkan dari nod terendah sehingga ke akar. Oleh kerana ia dijamin bahawa ketinggian maksimum CCH yang terdiri daripada n nod adalah tidak lebih daripada 2log(n + 1), maka dalam kes yang paling teruk, pengimbangan semula boleh mengambil log(n) - operasi. Kos ingatan untuk memasukkan ialah O(1) kerana ia hanya melibatkan penciptaan nod baharu; pengimbangan dan operasi mengecat semula tidak memerlukan memori tambahan. Bagaimanakah anda boleh mengetahui jika pokok tidak seimbang? Bagi KChD, ia berada dalam keadaan seimbang jika semua sifatnya yang diterangkan sebelum ini dipenuhi. Terdapat 4 jenis keadaan ketidakseimbangan: 1. Ketidakseimbangan kiri-kiri (LL) 2. Ketidakseimbangan kanan-kanan (RR) 3. Ketidakseimbangan kiri-kanan (LR) 4. Ketidakseimbangan kanan-kiri (RL) Dua keadaan pertama juga dipanggil linear (Garis), kerana secara visual ia boleh diwakili sebagai cabang lurus yang condong ke satu sisi. Baki dua dipanggil segitiga . Untuk membawa CCH ke dalam keadaan keseimbangan, perlu melakukan manipulasi padanya yang dipanggil putaran. Untuk mengimbangi 4 jenis ini, 2 jenis putaran digunakan: 1. Untuk LL dan RR 2. Untuk LR dan RL Jenis pertama ialah tarik nod pertama ke bawah supaya bahagian tengah berada di atas. Secara visual, ini boleh diwakili seolah-olah nod itu benar-benar nod pada tali yang tergantung pada paku: Putaran itu sendiri kelihatan seperti ini: Dengan putaran LL yang rumit, apabila nod juga mempunyai keturunan, prinsipnya tetap sama, tetapi betul. anak nod, yang menjadi induk, menjadi anak kiri/kanan nod yang ditarik . Contoh: Jenis kedua (LR,RL) terdiri daripada 2 peringkat dan terdiri daripada pertama membawa pokok ke keadaan pertama, dan kemudian juga menarik nod pertama ke bawah: Jika anda melihat angka ini, anda akan perasan bahawa kami hanya bergerak nod bawah ke atas , menjadikannya datuk "baru", dan menjadikan datuk "bekas" sama ada anak kiri atau kanan. Contoh: Dengan putaran LR/RL yang rumit, apabila nod juga mempunyai keturunan, prinsipnya tetap sama, tetapi bekas keturunan ibu bapa "baru" mengambil tempat yang kosong bagi keturunan nod anak. Contoh: Kod program pokok merah -hitam Kami bercakap tentang teori, sekarang mari lihat bagaimana peranti CNC diatur dalam bahasa pengaturcaraan JAVA. Mekanik pokok merah-hitam digunakan, khususnya, dalam pelaksanaan TreeMap , tetapi untuk kejelasan kami akan menggunakan kod yang lebih mudah. Semuanya bermula dengan memulakan medan statik peribadi KOSONG jenis Nod, yang mewakili nod kosong. Keturunan KOSONG juga KOSONG. Ia akan berguna kepada kami apabila memasukkan elemen, kerana semua helaian (diwakili sebagai NIL dalam rajah pertama) dimulakan oleh medan ini selepas dimasukkan.

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

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

Struktur kelas mengandungi rujukan kepada arus nod semasa , induk induk nod semasa , datuk kepada grand nod semasa , datuk besar nod semasa , dan penunjuk kepada akar tajuk pokok .

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

Apabila dibuat, pengepala dimulakan kepada nilai minimum Integer.MIN_VALUE supaya mana-mana elemen akan sentiasa lebih besar daripadanya dan anak-anaknya akan sentiasa menjadi elemen KOSONG kosong. Semua elemen akan sentiasa lebih besar daripada pengepala, jadi sisipan pertama sentiasa berlaku di sebelah kanan pengepala. Oleh itu, anak kanan header sentiasa menunjuk ke akar pokok, oleh itu, jika header.right == KOSONG , maka pokok itu kosong . Sebenarnya, perkara yang paling menarik ialah memasukkan elemen . Strategi untuk memasukkan elemen ke dalam KCHD adalah seperti berikut: 1. Masukkan nod dan warnakan ia merah . 2. Jika sisipan membawa kepada pelanggaran sifat CCH, kemudian cat semula ibu bapa, bapa saudara atau datuk dan putar nod untuk membawa pokok itu kembali ke keadaan seimbang. Terdapat 4 senario utama yang boleh berlaku semasa memasukkan elemen, untuk kemudahan kita panggil elemen yang disisipkan ini sebagai Z: 1. Z = akar (elemen yang dimasukkan ialah akar pokok) 2. Z.pakcik = merah (pakcik itu). daripada unsur yang disisipkan ialah merah ) 3. Z .pakcik = hitam (Garis). Pakcik unsur yang disisipkan berwarna hitam dan selepas memasukkan unsur tersebut pokok menjadi tidak seimbang dalam bentuk LL atau RR. 4. Z.pakcik = hitam (segi tiga). Pakcik unsur yang diselitkan berwarna hitam dan selepas memasukkan unsur tersebut pokok menjadi tidak seimbang dalam bentuk RL atau LR. Secara visual ia kelihatan seperti ini: Mari kita lihat dengan lebih terperinci tentang membetulkan keadaan bagi setiap satu daripada 4 kes yang mungkin. Kes No 1 . Kami hanya melukis akar hitam. Kes No. 2. Kami melukis datuk merah , dan bapa saudara hitam. Jika datuk nod adalah akar, maka warna datuk sekali lagi dicat hitam. Kes No 3 . Kami menjalankan putaran mengikut jenis No 1, iaitu, kami menarik simpulan datuk ke bawah. "A" menggantikan "B", dan kemudian kami mewarna semula nod datuk "bekas" merah dan nod induk hitam . Kes No 4 . Ia adalah yang paling sukar kerana ia terdiri daripada beberapa peringkat. Pertama, kami menjalankan putaran mengikut jenis No. 2, yang membawa kami ke keadaan yang diterangkan dalam kes No. 3, iaitu, kami telah melakukan putaran, tetapi pokok itu masih dalam keadaan tidak seimbang, sejak keturunan nod “Z” (nod “A”) berwarna merah . Iaitu, kini nod "A" melanggar sifat CCH dan putaran akan dilakukan berbanding dengan nod induknya, iaitu: datuk - nod "B", induk - nod "Z". Kami melakukan putaran sekali lagi, dan kemudian mengecat semula "bekas" datuk merah dan induk hitam . Mari kita kembali kepada kod. kaedah 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);
    }

Bahagian paling sukar berlaku dalam kaedah reorient() . Kaedah ini berkaitan dengan nod pewarna, serta melakukan putaran, yang di dalam badan ia merujuk kepada kaedah -> rotate(int item, Node parent) , yang seterusnya memanggil rotateWithLeftNode(Node element) atau rotateWithRightNode(Node element) kaedah , bergantung pada sama ada nilai elemen tambahan adalah kurang daripada atau lebih besar daripada nilai anak kiri atau kanan datuk, iaitu, ibu bapa unsur semasa. Kod kaedah:

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

Kaedah rotate(int item, Node parent) akan dilaksanakan secara berbeza bergantung pada apa yang diluluskan sebagai parameter induk , hebat seperti dalam jenis pengimbangan kedua, atau besar seperti dalam jenis pengimbangan pertama. Kod kaedah:

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

Kaedah rotateWithLeftNode(elemen Nod) dan rotateWithRightNode(elemen Nod) melakukan tindakan berikut:

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

Mari kita lihat mereka dengan jelas. Untuk jenis pertama, apabila kita tidak memasukkan syarat (item < grand.element != item < parent.element) , putaran akan kelihatan seperti ini: Untuk jenis kedua, apabila kita menghantar parameter grand (datuk) kepada parameter, putaran akan kelihatan seperti ini: Sila ambil perhatian bahawa nod induk telah ditimpa dan kini menunjuk ke semasa kami . Oleh kerana pokok itu masih tidak seimbang selepas putaran selesai, kami sekali lagi melakukan putaran mengikut jenis pertama , seperti dalam gambar sebelumnya. Persoalan mungkin timbul: mengapa, apabila kaedah rotateWithLeftNode dipanggil , adakah kita sebenarnya memutarkan nod ke kanan, dan apabila rotateWithRightNode - ke kiri? Ini kerana rotatWithLeftNode membayangkan putaran dengan anak kiri nod yang diluluskan, rotateWithRightNode , masing-masing, dengan yang betul. Arah putaran tidak diambil kira dalam nama kaedah . Dengan cara mudah ini, penggiliran juga dilakukan untuk kes yang lebih kompleks. Bahan dan pautan yang berguna: 1. Artikel Wiki 2. Visualizer pokok merah-hitam 3. Artikel bagus tentang KChD 4. Soalan tentang sama ada KChD benar-benar seimbang 5. Kod program KChD, yang tidak mempunyai akaun JavaRush 6. Video yang sangat baik oleh seorang guru yang sangat berbakat (bercakap tentang AVL, tetapi prinsipnya serupa dengan KChD) 7. Satu siri video tentang peranti, mekanisme sisipan dan putaran Kenalan pengarang: Telegram Mail: realyte95@gmail.com