ต้นไม้สีแดง-ดำ คุณสมบัติ หลักการขององค์กร กลไกการแทรก

แนวคิดของต้นไม้สีแดง - ดำ ต้นไม้สีแดงดำเป็นต้นไม้ไบนารีชนิดหนึ่งซึ่งมีสาระสำคัญหลักคือความสามารถในการปรับสมดุลในตนเอง ต้นไม้ที่ปรับสมดุลในตัวเองมีหลายประเภท แต่ในบทความนี้ เราจะพูดถึงเฉพาะต้นไม้สีแดงดำหรือ (RCB) เท่านั้น ความสมดุลเกิดขึ้นได้โดยการแนะนำคุณลักษณะเพิ่มเติมของโหนดต้นไม้ - "สี" นอกเหนือจากองค์ประกอบแล้ว โหนดต้นไม้แต่ละโหนดยังเก็บข้อมูล 1 บิตว่าโหนดนั้นเป็นสีแดงหรือสีดำ ซึ่งไม่เพียงแต่เป็นสีเท่านั้น แต่ยังรวมถึงข้อมูลอื่น ๆ ที่ช่วยให้สามารถแยกแยะโหนดประเภทหนึ่งจากอีกโหนดหนึ่งได้ ตัวอย่างเช่น 1 หรือ 0 จริงหรือเท็จ เป็นต้น หลักการจัดระเบียบ (คุณสมบัติ) ของ KChD: 1. รากของต้นไม้เป็นสีดำ 2. ใบไม้ทั้งหมดที่ไม่มีข้อมูลจะเป็นสีดำ 3. ลูกทั้งสองของแต่ละโหนดสีแดง เป็น สีดำ 4. ความลึกใน โหนด สีดำจะเท่ากันสำหรับทรีย่อยใดๆ การดำเนินการหลักที่ทำบนทรีคือ: 1. ค้นหา 2. ใส่ องค์ประกอบที่ 3 การลบองค์ประกอบ (ลบ) การดำเนินการสองรายการสุดท้ายนำไปสู่การเปลี่ยนแปลงโครงสร้างของแผนภูมิอย่างชัดเจน ดังนั้นผลลัพธ์จึงอาจเป็นความไม่สมดุลในแผนภูมิ ความซับซ้อนของเวลาและพื้นที่ การดำเนินการแทรก การลบ และการค้นหาสำหรับ Time Complexity QCD คือ O(log n)โดยที่ n คือจำนวนโหนดในแผนผัง เนื่องจากในการดำเนินการดังกล่าว เราจำเป็นต้องไปยังโหนดที่ต้องการ โดยละทิ้งแผนผังย่อยหนึ่งรายการในแต่ละแผนผัง ขั้นตอน ในกรณีที่การแทรกหรือการลบทำให้เกิดการละเมิดคุณสมบัติของ CCH จำเป็นต้องดำเนินการปรับสมดุลใหม่ การปรับสมดุลประกอบด้วยการดำเนินการสองอย่าง: การเปลี่ยนสี O(1) และการหมุน O(1) การดำเนินการปรับสมดุลแต่ละครั้งจะใช้เวลาคงที่ เนื่องจากประกอบด้วยการเขียนลิงก์ขององค์ประกอบลูกและองค์ประกอบหลักใหม่ รวมถึงข้อมูลเกี่ยวกับสีของพวกเขา อย่างไรก็ตาม เมื่อแทรกหรือลบองค์ประกอบ สถานการณ์อาจเกิดขึ้นซึ่งต้นไม้จำเป็นต้องสมดุลจากโหนดต่ำสุดไปจนถึงราก เนื่องจากมีการรับประกันว่าความสูงสูงสุดของ CCH ที่ประกอบด้วย n โหนดจะไม่เกิน 2log(n + 1) ดังนั้นในกรณีที่เลวร้ายที่สุด การปรับสมดุลใหม่อาจต้องใช้การดำเนินการ log(n) - ต้นทุนหน่วยความจำของการแทรกคือO(1)เนื่องจากเกี่ยวข้องกับการสร้างโหนดใหม่เท่านั้น การดำเนินการปรับสมดุลและการทาสีใหม่ไม่จำเป็นต้องใช้หน่วยความจำเพิ่มเติม คุณจะบอกได้อย่างไรว่าต้นไม้ไม่สมดุล? สำหรับ KChD จะอยู่ในสถานะสมดุลหากมีคุณสมบัติตรงตามที่อธิบายไว้ก่อนหน้านี้ทั้งหมด สถานะความไม่สมดุลมี 4 ประเภท: 1. ความไม่สมดุลซ้าย-ซ้าย (LL) 2. ความไม่สมดุลขวา-ขวา (RR) 3. ความไม่สมดุลซ้าย-ขวา (LR) 4. ความไม่สมดุลขวา-ซ้าย (RL) สองสถานะแรกก็เช่น กัน เรียกว่า เชิงเส้น(Line )เนื่องจากมองเห็นได้ว่าเป็นกิ่งก้านตรงที่เบ้ไปด้านหนึ่ง อีกสองอันที่เหลือเรียกว่าสามเหลี่ยม ในการทำให้ CCH เข้าสู่สภาวะสมดุลจำเป็นต้องดำเนินการจัดการที่เรียกว่าการหมุน เพื่อปรับสมดุลทั้ง 4 ประเภทนี้ จะใช้การหมุน 2 แบบ: 1. สำหรับ LL และ RR 2. สำหรับ LR และ RL ประเภทแรกคือการดึงโหนดแรกลงเพื่อให้ตรงกลางอยู่ด้านบน เมื่อมองเห็นสิ่งนี้สามารถแสดงได้ราวกับว่าโหนดนั้นเป็นโหนดจริงๆ บนเชือกที่แขวนอยู่บนตะปู: การหมุนนั้นมีลักษณะดังนี้: ด้วยการหมุน LL ที่ซับซ้อน เมื่อโหนดมีการสืบทอดเช่นกัน หลักการยังคงเหมือนเดิม แต่ด้านขวา ลูกของโหนดซึ่ง กลายเป็นพาเรนต์จะกลายเป็นลูกซ้าย/ขวาของโหนดที่ถูกดึง ตัวอย่าง: ประเภทที่สอง (LR,RL)ประกอบด้วย 2 ขั้นตอนและประกอบด้วยการนำต้นไม้ไปสู่สถานะแรกก่อน จากนั้นจึงดึงโหนดแรกลงมาด้วย: หากคุณดูรูปนี้ คุณจะสังเกตเห็นว่าเราเพียงแค่เคลื่อนไหว โหนดด้านล่างขึ้นไปด้านบนทำให้เป็นปู่ "ใหม่" และทำให้ปู่ "อดีต" เป็นลูกทางซ้ายหรือขวา ตัวอย่าง: ด้วยการหมุนเวียน LR/RL ที่ซับซ้อน เมื่อโหนดมีการสืบทอด หลักการจะยังคงเหมือนเดิม แต่การสืบทอดในอดีตของพาเรนต์ "ใหม่" จะเข้ามาแทนที่การสืบทอดของโหนดย่อยที่ว่าง ตัวอย่าง: รหัสโปรแกรมของต้นไม้สีแดง- ดำ เราได้พูดถึงทฤษฎีแล้ว ตอนนี้เรามาดูกันว่าอุปกรณ์ CNC ได้รับการจัดระเบียบในภาษาโปรแกรม JAVA อย่างไร โดยเฉพาะอย่างยิ่งมีการใช้กลไกต้นไม้สีแดง-ดำใน การใช้งานTreeMapแต่เพื่อความชัดเจน เราจะใช้โค้ดที่ง่ายขึ้น ทุกอย่างเริ่มต้นด้วยการเริ่มต้นฟิลด์คงที่ส่วนตัว EMPTY ประเภท Node ซึ่งแสดงถึงโหนดว่าง ทายาทของ EMPTY ก็ว่างเปล่าเช่นกัน มันจะมีประโยชน์สำหรับเราเมื่อแทรกองค์ประกอบ เนื่องจากชีตทั้งหมด (แสดงเป็น NIL ในรูปแรก) จะถูกเตรียมใช้งานโดยฟิลด์นี้เมื่อมีการแทรก

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

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

โครงสร้างคลาสประกอบด้วยการอ้างอิงถึงโหนดปัจจุบัน current ,พาเรนต์ของโหนดพาเรนต์ปัจจุบัน,คุณปู่ของโหนดปัจจุบันgrand , ปู่ทวดของโหนดปัจจุบันgreat และตัวชี้ไปยังรากของส่วนหัวของแผนผัง

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

เมื่อสร้างแล้ว ส่วนหัวจะเริ่มต้นเป็นค่าต่ำสุด Integer.MIN_VALUE เพื่อให้องค์ประกอบใดๆ ก็ตามมีค่ามากกว่าเสมอ และรายการย่อยจะเป็นองค์ประกอบว่างเสมอ องค์ประกอบทั้งหมดจะมีขนาดใหญ่กว่าส่วนหัวเสมอ ดังนั้นการแทรกครั้งแรกจะเกิดขึ้นทางด้านขวาของส่วนหัวเสมอ ดังนั้น ลูกด้านขวาของ header จะชี้ไปที่รากของแผนผังเสมอ ดังนั้นหากheader.right == EMPTYต้นไม้ก็จะว่างเปล่า จริงๆ แล้วสิ่งที่น่าสนใจที่สุดคือการแทรกองค์ประกอบ กลยุทธ์ในการแทรกองค์ประกอบลงใน KCHD มีดังนี้: 1. แทรกโหนดและกำหนดให้เป็นสีแดง 2. หากการแทรกนำไปสู่การละเมิดคุณสมบัติของ CCH ให้ทาสีผู้ปกครองลุงหรือปู่ใหม่และหมุนโหนดเพื่อนำต้นไม้กลับเข้าสู่สภาวะสมดุล มี 4 สถานการณ์หลักที่อาจเกิดขึ้นได้เมื่อแทรกองค์ประกอบ เพื่อความสะดวก ให้เรียกองค์ประกอบที่แทรกนี้เป็น Z: 1. Z = root (องค์ประกอบที่ถูกแทรกคือรากของแผนผัง) 2. Z.uncle = สีแดง (ลุง ขององค์ประกอบที่แทรกคือสีแดง ) 3. Z .uncle = สีดำ (เส้น) ลุงขององค์ประกอบที่แทรกจะเป็นสีดำและหลังจากแทรกองค์ประกอบ ต้นไม้ก็ไม่สมดุลในรูปแบบของ LL หรือ RR 4. Z.uncle = สีดำ (สามเหลี่ยม) ลุงขององค์ประกอบที่แทรกจะเป็นสีดำและหลังจากแทรกองค์ประกอบ ต้นไม้ก็ไม่สมดุลในรูปแบบของ RL หรือ LR เมื่อมองเห็นจะมีลักษณะดังนี้: มาดูรายละเอียดเพิ่มเติมเกี่ยวกับการแก้ไขสถานการณ์สำหรับแต่ละกรณีที่เป็นไปได้ทั้ง 4 กรณี คดีหมายเลข 1 . เราแค่ทารากดำ กรณีที่ 2เราทาปู่สีแดงและลุงดำ หากปู่ของโหนดเป็นราก สีของปู่จะถูกทาสีดำอีกครั้ง คดีหมายเลข 3 . เราดำเนินการหมุนตามประเภทที่ 1 นั่นคือเราดึงปมของคุณปู่ลง “A” แทนที่ “B” จากนั้นเราจะเปลี่ยนสีโหนดปู่ “เดิม” เป็นสีแดงและโหนดหลัก เป็น สี ดำ คดีหมายเลข 4 . เป็นเรื่องยากที่สุดเนื่องจากประกอบด้วยหลายขั้นตอน ขั้นแรกเราดำเนินการหมุนเวียนตามประเภทที่ 2 ซึ่งนำเราไปสู่สถานะที่อธิบายไว้ในกรณีที่หมายเลข 3 นั่นคือเราได้ดำเนินการหมุนเวียนแล้ว แต่ต้นไม้ยังอยู่ในสภาพไม่สมดุลเนื่องจากทายาทของ โหนด “Z” (โหนด “A”) เป็นสีแดง นั่นคือตอนนี้โหนด "A" ละเมิดคุณสมบัติของ CCH และการหมุนจะดำเนินการโดยสัมพันธ์กับโหนดหลักซึ่งก็คือ: ปู่ - โหนด "B", ผู้ปกครอง - โหนด "Z" เราทำการหมุนอีกครั้ง จากนั้นทาสีปู่ "อดีต" ใหม่สีแดงและพาเรนต์สีดำ . กลับมาที่โค้ดกัน วิธีการแทรก ()

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

ส่วนที่ยากที่สุดเกิดขึ้นใน วิธีการ reorient ( ) วิธีการนี้เกี่ยวข้องกับการระบายสีโหนด เช่นเดียวกับการดำเนินการหมุน ซึ่งภายในร่างกายมันอ้างถึง -> หมุน(int item, Node parent) วิธีการ ซึ่งจะเรียกrotateWithLeftNode(องค์ประกอบโหนด)หรือrotrotWithRightNode(องค์ประกอบโหนด)วิธีการ ขึ้นอยู่กับว่าค่าขององค์ประกอบที่เพิ่มนั้นน้อยกว่าหรือมากกว่าค่าของลูกทางซ้ายหรือทางขวาของปู่ นั่นคือ ค่าพาเรนต์ขององค์ประกอบปัจจุบัน รหัสวิธีการ:

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

วิธี การหมุน ( รายการ int, โหนดพาเรนต์)จะถูกดำเนินการแตกต่างกันไปขึ้นอยู่กับสิ่งที่ส่งผ่านเป็น พารามิเตอร์ พาเรนต์ดีเยี่ยมในการปรับสมดุลประเภทที่สอง หรือยิ่งใหญ่เช่นเดียวกับในการปรับสมดุลประเภทแรก รหัสวิธีการ:

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

เมธอดRotWithLeftNode(องค์ประกอบ Node)และRotWithRightNode(องค์ประกอบ Node)ดำเนินการต่อไปนี้:

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

มาดูกันชัดๆ สำหรับประเภทแรก เมื่อ เราไม่ป้อน เงื่อนไข(item < grand.element != item < parent.element) การหมุนจะมีลักษณะดังนี้: สำหรับประเภทที่สอง เมื่อเราส่งพารามิเตอร์ grand (grandfather) ไปยัง การหมุนจะมีลักษณะดังนี้: โปรดทราบว่า โหนด หลักถูกเขียนทับแล้ว และตอนนี้ชี้ไปที่ไฟล์ . เนื่องจากต้นไม้ยังไม่สมดุลหลังจากการหมุนเสร็จสมบูรณ์เราจึงทำการหมุนอีกครั้งตามประเภทแรกดังในภาพก่อนหน้า คำถามอาจเกิดขึ้น: ทำไมเมื่อมี การเรียกใช้เมธอด RotWithLeftNodeเราจะหมุนโหนดไปทางขวาจริง ๆ และเมื่อRotWithRightNode - ไปทางซ้ายหรือไม่ นี่เป็นเพราะrotatWithLeftNodeแสดงถึงการหมุนด้วยลูกด้านซ้ายของโหนดที่ส่งผ่าน หมุน ด้วย RightNodeตามลำดับ ทางด้านขวา ทิศทางการหมุนไม่ได้ถูกนำมาพิจารณาในชื่อวิธีการ ด้วยวิธีง่ายๆ นี้ จะมีการหมุนเวียนในกรณีที่ซับซ้อนมากขึ้นด้วย สื่อและลิงก์ที่มีประโยชน์: 1. บทความ Wiki 2. เครื่องมือสร้างภาพต้นไม้สีแดง-ดำ 3. บทความดีๆ เกี่ยวกับ KChD 4. คำถามว่า KChD มีความสมดุลจริงหรือไม่ 5. โค้ดโปรแกรม KChD ใครไม่มีบัญชี JavaRush 6. วิดีโอยอดเยี่ยมโดย ครูที่มีความสามารถมาก (พูดถึง AVL แต่หลักการคล้ายกับ KChD) 7. ชุดวิดีโอเกี่ยวกับอุปกรณ์ การแทรก และกลไกการหมุน ผู้ติดต่อของผู้เขียน: Telegram Mail: realyte95@gmail.com