Рубрики

Красно-Черные Деревья | Вставка сверху вниз

При вставке «снизу вверх» красно-черных деревьев используется «простая» вставка бинарного дерева поиска с последующей коррекцией нарушений дерева RB по пути обратно к корню. Это можно легко сделать с помощью рекурсии. Во время вставки сверху вниз исправления выполняются при прохождении дерева вниз до точки вставки. Когда фактическая вставка сделана, дальнейшие исправления не требуются, поэтому нет необходимости проходить обратно по дереву.

Следовательно, цель вставки сверху вниз состоит в том, чтобы пройти от корня к точке вставки таким образом, чтобы сохранить свойства RB. Таким образом, этот итеративный подход делает вставку сверху вниз быстрее, чем вставку снизу вверх.

Две основные операции для устранения нарушений и балансировки:

  • перекрашивание
  • вращение
  • Ниже приводится подробный алгоритм
    Основная цель этого алгоритма состоит в том, чтобы создать точку вставки, в которой родитель нового узла — черный, или дядя нового узла — черный.

    Пусть N будет новым узлом для вставки.

    1. Если Y и Z черные:
    2. выполнить простую вставку BST . Вставьте новый узел N как левый / правый дочерний элемент Y ИЛИ Z и сделайте цвет недавно вставленного узла красным.

    3. Если родитель X черный
    4. Затем перекрасьте X, Y, Z и продолжайте вниз по дереву.

    5. Родитель Х — красный, дед — черный, а Х и Р — левые ИЛИ правые дети дедушки G:
    • Перекрасить X, Y, Z
    • Поверните P вокруг G
    • Цвет Р черный
    • Цвет G красный

    Если нарушения существуют, продолжайте в следующих случаях.

  • Родитель Х — Красный, Дедушка — Черный, а Х и Р — противоположные дети Дедушки Г
    • Перекрасить X, Y, Z
    • Поверните X вокруг P
    • Поверните X вокруг G
    • Перекрасить X и G

    Вставьте новый узел N в требуемое положение.

    Пример :
    Вставьте Узел 3 в дерево RB ниже —

    Ниже приведена реализация следующего подхода:

    Джава

    // Java реализация для Top-Down
    // Создание вставки красно-черного дерева
    // красное черное дерево и сохранение
    // Английское предложение в него, используя Top
    // метод вставки вниз

      

    import static java.lang.Integer.max;

      
    // Класс для выполнения
    // RBTree операции

    public class RbTree {

        TreeNode Root = null;

      

        // Функция для расчета

        // высота дерева

        int HeightT(TreeNode Root)

        {

            int lefth, righth;

      

            if (Root == null

                || (Root.children == null

                    && Root.children[1] == null)) {

                return 0;

            }

            lefth = HeightT(Root.children[0]);

            righth = HeightT(Root.children[1]);

      

            return (max(lefth, righth) + 1);

        }

      

        // Функция для проверки

        // dir равен 0

        int check(int dir)

        {

            return dir == 0 ? 1 : 0;

        }

      

        // Функция для проверки, если

        // цвет узла красный или нет

        boolean isRed(TreeNode Node)

        {

            return Node != null

                && Node.color.equals("R");

        }

      

        // Функция для выполнения

        // одиночное вращение

        TreeNode SingleRotate(TreeNode Node,

                              int dir)

        {

            TreeNode temp

                = Node.children[check(dir)];

            Node.children[check(dir)]

                = temp.children[dir];

            temp.children[dir] = Node;

            Root.color = "R";

            temp.color = "B";

      

            return temp;

        }

      

        // Функция для двойного вращения

        TreeNode DoubleRotate(TreeNode Node,

                              int dir)

        {

            Node.children[check(dir)]

                = SingleRotate(Node.children[check(dir)],

                               check(dir));

            return SingleRotate(Node, dir);

        }

      

        // Функция для вставки нового

        // узел с заданными данными

        TreeNode Insert(RbTree tree,

                        String data)

        {

            if (tree.Root == null) {

                tree.Root

                    = new TreeNode(data);

                if (tree.Root == null)

                    return null;

            }

            else {

      

                // временный корень

                TreeNode temp = new TreeNode("");

      

                // дед и родитель

                TreeNode g, t;

                TreeNode p, q;

      

                int dir = 0, last = 0;

      

                t = temp;

      

                g = p = null;

      

                t.children[1] = tree.Root;

      

                q = t.children[1];

                while (true) {

      

                    if (q == null) {

      

                        // Вставка корневого узла

                        q = new TreeNode(data);

                        p.children[dir] = q;

                    }

      

                    // Брат красный

                    else if (isRed(q.children[0])

                             && isRed(q.children[1])) {

      

                        // Перекрашивание, если оба

                        // дети красные

                        q.color = "R";

                        q.children[0].color = "B";

                        q.children[1].color = "B";

                    }

      

                    if (isRed(q) && isRed(p)) {

      

                        // Разрешаем красно-красный

                        // нарушение

                        int dir2;

                        if (t.children[1] == g) {

                            dir2 = 1;

                        }

                        else {

                            dir2 = 0;

                        }

      

                        // Если дети и родитель

                        // лево-лево или

                        // право-право прародителя

                        if (q == p.children[last]) {

                            t.children[dir2]

                                = SingleRotate(g,

                                               last == 0

                                                   ? 1

                                                   : 0);

                        }

      

                        // Если они противоположны

                        // дочерние элементы, т.е. слева направо

                        // или вправо-влево

                        else {

                            t.children[dir2]

                                = DoubleRotate(g,

                                               last == 0

                                                   ? 1

                                                   : 0);

                        }

                    }

      

                    // Проверка на правильность

                    // положение узла

                    if (q.data.equals(data)) {

                        break;

                    }

                    last = dir;

      

                    // Находим путь к

                    // traverse [Любой слева

                    // или право ]

                    dir = q.data.compareTo(data) < 0

                              ? 1

                              : 0;

      

                    if (g != null) {

                        t = g;

                    }

      

                    // Переставляем указатели

                    g = p;

                    p = q;

                    q = q.children[dir];

                }

      

                tree.Root = temp.children[1];

            }

      

            // Назначаем черный цвет

            // к корневому узлу

            tree.Root.color = "B";

      

            return tree.Root;

        }

      

        // Печать узлов на каждом

        // уровень в порядке уровней

        // обход

        void PrintLevel(TreeNode root, int i)

        {

            if (root == null) {

                return;

            }

      

            if (i == 1) {

                System.out.print("| "

                                 + root.data

                                 + " | "

                                 + root.color

                                 + " |");

      

                if (root.children[0] != null) {

                    System.out.print(" "

                                     + root.children[0].data

                                     + " |");

                }

                else {

                    System.out.print(" "

                                     + "NULL"

                                     + " |");

                }

                if (root.children[1] != null) {

                    System.out.print(" "

                                     + root.children[1].data

                                     + " |");

                }

                else {

                    System.out.print(" "

                                     + "NULL"

                                     + " |");

                }

      

                System.out.print(" ");

      

                return;

            }

      

            PrintLevel(root.children[0],

                       i - 1);

            PrintLevel(root.children[1],

                       i - 1);

        }

      

        // Функция полезности для

        // выполнить порядок уровней

        // обход

        void LevelOrder(TreeNode root)

        {

            int i;

      

            for (i = 1;

                 i < HeightT(root) + 1;

                 i++) {

                PrintLevel(root, i);

                System.out.print("\n\n");

            }

        }

    }

      
    // Класс для представления
    // узел дерева

    class TreeNode {

      

        // переменные класса

        String data, color;

        TreeNode children[];

      

        public TreeNode(String data)

        {

            // Цвет R- Красный

            // и B - черный

            this.data = data;

            this.color = "R";

            children

                = new TreeNode[2];

            children[0] = null;

            children[1] = null;

        }

    }

      
    // Код драйвера

    class Driver {

        public static void main(String[] args)

        {

            // Представление узла дерева

            // -------------------------------------------

            // ДАННЫЕ | ЦВЕТ | ЛЕВЫЙ РЕБЕНОК | ПРАВЫЙ РЕБЕНОК |

            // -------------------------------------------

      

            RbTree Tree = new RbTree();

            String Sentence, Word;

            Sentence = "old is gold";

            String Word_Array[]

                = Sentence.split(" ");

      

            for (int i = 0;

                 i < Word_Array.length;

                 i++) {

                Tree.Root

                    = Tree.Insert(Tree,

                                  Word_Array[i]);

            }

      

            // Печать уровня обхода заказа

            System.out.println("The Level"

                               + "Order Traversal"

                               + "of the tree is:");

            Tree.LevelOrder(Tree.Root);

            System.out.println("\nInserting a"

                               + " word in the tree:");

            Word = "forever";

            Tree.Root = Tree.Insert(Tree,

                                    Word);

      

            System.out.println("");

            Tree.LevelOrder(Tree.Root);

        }

    }

    C #

    // реализация C # для Top-Down
    // Создание вставки красно-черного дерева
    // красное черное дерево и сохранение
    // Английское предложение в него, используя Top
    // метод вставки вниз

    using System;

      
    // Класс для выполнения
    // RBTree операции

    class RbTree

    {

        public TreeNode Root = null;

      

        // Функция для расчета

        // высота дерева

        public int HeightT(TreeNode Root)

        {

            int lefth, righth;

      

            if (Root == null || 

               (Root.children == null && 

                Root.children[1] == null)) 

            {

                return 0;

            }

            lefth = HeightT(Root.children[0]);

            righth = HeightT(Root.children[1]);

      

            return (Math.Max(lefth, righth) + 1);

        }

      

        // Функция для проверки

        // dir равен 0

        public int check(int dir)

        {

            return dir == 0 ? 1 : 0;

        }

      

        // Функция для проверки, если

        // цвет узла красный или нет

        public bool isRed(TreeNode Node)

        {

            return Node != null && 

                   Node.color.Equals("R");

        }

      

        // Функция для выполнения

        // одиночное вращение

        public TreeNode SingleRotate(TreeNode Node, int dir)

        {

            TreeNode temp = Node.children[check(dir)];

            Node.children[check(dir)] = temp.children[dir];

            temp.children[dir] = Node;

            Root.color = "R";

            temp.color = "B";

      

            return temp;

        }

      

        // Функция для двойного вращения

        public TreeNode DoubleRotate(TreeNode Node, int dir)

        {

            Node.children[check(dir)] = 

                 SingleRotate(Node.children[check(dir)], 

                                            check(dir));

            return SingleRotate(Node, dir);

        }

      

        // Функция для вставки нового

        // узел с заданными данными

        public TreeNode Insert(RbTree tree,

                               String data)

        {

            if (tree.Root == null)

            {

                tree.Root = new TreeNode(data);

                if (tree.Root == null)

                    return null;

            }

            else

            {

      

                // временный корень

                TreeNode temp = new TreeNode("");

      

                // дед и родитель

                TreeNode g, t;

                TreeNode p, q;

      

                int dir = 0, last = 0;

      

                t = temp;

      

                g = p = null;

      

                t.children[1] = tree.Root;

      

                q = t.children[1];

                while (true

                {

                    if (q == null

                    {

      

                        // Вставка корневого узла

                        q = new TreeNode(data);

                        p.children[dir] = q;

                    }

      

                    // Брат красный

                    else if (isRed(q.children[0]) && 

                             isRed(q.children[1])) 

                    {

      

                        // Перекрашивание, если оба

                        // дети красные

                        q.color = "R";

                        q.children[0].color = "B";

                        q.children[1].color = "B";

                    }

      

                    if (isRed(q) && isRed(p)) 

                    {

      

                        // Разрешаем красно-красный

                        // нарушение

                        int dir2;

                        if (t.children[1] == g) 

                        {

                            dir2 = 1;

                        }

                        else 

                        {

                            dir2 = 0;

                        }

      

                        // Если дети и родитель

                        // лево-лево или

                        // право-право прародителя

                        if (q == p.children[last]) 

                        {

                            t.children[dir2] = 

                              SingleRotate(g, last == 0 ? 1 : 0);

                        }

      

                        // Если они противоположны

                        // дочерние элементы, т.е. слева направо

                        // или вправо-влево

                        else 

                        {

                            t.children[dir2] = 

                              DoubleRotate(g, last == 0 ? 1 : 0);

                        }

                    }

      

                    // Проверка на правильность

                    // положение узла

                    if (q.data.Equals(data)) 

                    {

                        break;

                    }

                    last = dir;

      

                    // Находим путь к

                    // traverse [Любой слева

                    // или право ]

                    dir = q.data.CompareTo(data) < 0 ? 1 : 0;

      

                    if (g != null

                    {

                        t = g;

                    }

      

                    // Переставляем указатели

                    g = p;

                    p = q;

                    q = q.children[dir];

                }

                tree.Root = temp.children[1];

            }

      

            // Назначаем черный цвет

            // к корневому узлу

            tree.Root.color = "B";

      

            return tree.Root;

        }

      

        // Печать узлов на каждом

        // уровень в порядке уровней

        // обход

        public void PrintLevel(TreeNode root, int i)

        {

            if (root == null)

            {

                return;

            }

      

            if (i == 1)

            {

                Console.Write("| " + root.data +

                             " | " + root.color + " |");

      

                if (root.children[0] != null

                {

                    Console.Write(" "

                       root.children[0].data + " |");

                }

                else 

                {

                    Console.Write(" " + "NULL" + " |");

                }

                if (root.children[1] != null)

                {

                    Console.Write(" "

                       root.children[1].data + " |");

                }

                else 

                {

                    Console.Write(" " + "NULL" + " |");

                }

      

                Console.Write(" ");

      

                return;

            }

      

            PrintLevel(root.children[0], i - 1);

            PrintLevel(root.children[1], i - 1);

        }

      

        // Полезная функция для выполнения

        // уровень прохождения заказа

        public void LevelOrder(TreeNode root)

        {

            int i;

      

            for (i = 1; i < HeightT(root) + 1; i++)

            {

                PrintLevel(root, i);

                Console.Write("\n\n");

            }

        }

    }

      
    // Класс для представления
    // узел дерева

    public class TreeNode 

    {

      

        // переменные класса

        public String data, color;

        public TreeNode []children;

      

        public TreeNode(String data)

        {

            // Цвет R- Красный

            // и B - черный

            this.data = data;

            this.color = "R";

            children = new TreeNode[2];

            children[0] = null;

            children[1] = null;

        }

    }

      
    // Код драйвера

    public class Driver 

    {

        public static void Main(String[] args)

        {

            // Представление узла дерева

            // -------------------------------------------

            // ДАННЫЕ | ЦВЕТ | ЛЕВЫЙ РЕБЕНОК | ПРАВЫЙ РЕБЕНОК |

            // -------------------------------------------

            RbTree Tree = new RbTree();

            String Sentence, Word;

            Sentence = "old is gold";

            char[] spearator = { ' ', ' ' }; 

            String []Word_Array = Sentence.Split(spearator, 

                    StringSplitOptions.RemoveEmptyEntries);

      

            for (int i = 0; i < Word_Array.Length; i++)

            {

                Tree.Root = Tree.Insert(Tree,

                                Word_Array[i]);

            }

      

            // Печать уровня обхода заказа

            Console.WriteLine("The Level"

                              "Order Traversal"

                              "of the tree is:");

            Tree.LevelOrder(Tree.Root);

            Console.WriteLine("\nInserting a"

                              " word in the tree:");

            Word = "forever";

            Tree.Root = Tree.Insert(Tree, Word);

      

            Console.WriteLine("");

            Tree.LevelOrder(Tree.Root);

        }

    }

      
    // Этот код предоставлен Rajput-Ji

    Выход:

    The LevelOrder Traversalof the tree is:
    | is | B | gold | old | 
    
    | gold | R | NULL | NULL | | old | R | NULL | NULL | 
    
    
    Inserting a word in the tree:
    
    | is | B | gold | old | 
    
    | gold | B | forever | NULL | | old | B | NULL | NULL | 
    
    | forever | R | NULL | NULL | 
    

    Ссылки:
    Красные Черные Деревья — UMBC CSEE

    Рекомендуемые посты:

    Красно-Черные Деревья | Вставка сверху вниз

    0.00 (0%) 0 votes