Красно-черное дерево, удаляющее проблему C #

Question

Я пытаюсь реализовать красно-черное дерево в C #. Я уже создал объект с именем sRbTreeNode, который имеет свойства String key, Color, Left, Right и Parent. Мне удалось успешно реализовать методы Insert, InsertFixUp, LeftRotate, RightRotate, Delete, и теперь у меня возникли проблемы с методом DeleteFixUp.

DeleteFixUp отвечает за балансировку дерева снова (используя повороты и изменяя цвета узлов) после удаления.

Я пытался реализовать метод из псевдокода, который я нашел в книге под названием «Введение в алгоритмы».

Вот мой код:

private static void DeleteFixup(ref sRbTreeNode root, sRbTreeNode x)
    {
        sRbTreeNode y;

        while (x != root && x.Color == BLACK)
        {
            if (x == x.Parent.Left)         // determine sub tree from parent
            {
                y = x.Parent.Right;         // y is x's sibling 
                if (y.Color == RED)
                {   // x is black, y is red - make both black and rotate
                    y.Color = BLACK;
                    x.Parent.Color = RED;
                    LeftRotate(ref root, x.Parent);
                    y = x.Parent.Right;
                }
                if (y.Left.Color == BLACK &&
                    y.Right.Color == BLACK)
                {   // children are both black
                    y.Color = RED;      // change parent to red
                    x = x.Parent;                   // move up the tree
                }
                else
                {
                    if (y.Right.Color == BLACK)
                    {
                        y.Left.Color = BLACK;
                        y.Color = RED;
                        RightRotate(ref root, y);
                        y = x.Parent.Right;
                    }
                    y.Color = x.Parent.Color;
                    x.Parent.Color = BLACK;
                    y.Right.Color = BLACK;
                    LeftRotate(ref root, x.Parent);
                    x = root;
                }
            }
            else
            {   // right subtree - same as code above with right and left swapped
                y = x.Parent.Left;
                if (y.Color == RED)
                {
                    y.Color = BLACK;
                    x.Parent.Color = RED;
                    RightRotate(ref root, x.Parent);
                    y = x.Parent.Left;
                }
                if (y.Right.Color == BLACK &&
                    y.Left.Color == BLACK)
                {
                    y.Color = RED;
                    x = x.Parent;
                }
                else
                {
                    if (y.Left.Color == BLACK)
                    {
                        y.Right.Color = BLACK;
                        y.Color = RED;
                        LeftRotate(ref root, y);
                        y = x.Parent.Left;
                    }
                    y.Color = x.Parent.Color;
                    x.Parent.Color = BLACK;
                    y.Left.Color = BLACK;
                    RightRotate(ref root, x.Parent);
                    x = root;
                }
            }
        }

        x.Color = BLACK;
    }

Я продолжаю сталкиваться с ошибкой "Ссылка на объект не установлена ​​на экземпляр объекта" каждый раз в разных местах ...

Я искал в Интернете реализации этого, только что нашел одну статью о CodeProject, которая реализовала его точно так же, как и я. Я попытался скопировать их код, надеясь, что мне что-то не хватает, но это не сработало ...

Может кто-нибудь помочь мне, прежде чем я начну рвать на себе волосы !! ... ?? :)

Answer 1

После некоторого исследования я обнаружил, что проблема была в том, как я обращался с красно-черными деревьями, которые я построил.

Согласно книгам по этому предмету (включая ту, из которой я учусь!), Каждый узел в нижней части дерева должен вести к «нулевому узлу». Нулевой узел - это узел, который не имеет значения и имеет черный цвет. Я думал, что мне не нужно будет реализовывать нулевые узлы в моем дереве, и в каждом месте, где проводилась проверка черного узла, я добавлял «|| node == null», потому что это может быть проверка на нулевой узел. Проблема заключалась в том, что иногда вам нужно проверять родительский узел нулевого узла, и если вы на самом деле не реализуете «нулевой узел», вы получите ошибку при попытке получить его свойство Parent.

Я реализовал «нулевой узел», просто добавив узел с пустыми значениями и черной окраской к каждому узлу без дочерних элементов. Потребовалось немного доработать большинство методов манипулирования на дереве, но в итоге это решило (почти) все мои проблемы.

Спасибо всем за попытку помочь мне !! :)

Answer 2

Хотя, возможно, и не прямой ответ на ваш вопрос, вы узнаете невероятную сумму, просто пройдя свой код в отладчике. Плюс Вы, вероятно, решите проблему самостоятельно! Если вам нужна помощь в установке точки останова, проверке переменных или пошаговом режиме, пожалуйста, дайте мне знать. Visual Studio настолько прост в использовании, что почти безмозглый.

Answer 3

Посмотрим ...

   while (x != root && (x == null || x.Color == BLACK))
    {
        if (x == x.Parent.Left)         // determine sub tree from parent

Итак, если x в начале имеет значение null, вы пытаетесь разыменовать x.Parent, который выдаст исключение, которое вы получаете. Я посмотрел на две строки и уже нашел одну ошибку.

Вам нужно проверить каждую ссылку на ноль в какой-то момент перед разыменованием.

Answer 4

Нулевые параметры проскальзывают где-то.

Если x == null, то мы терпим крах, как только мы проверяем if.

Если кто-либо из детей x.Parent равен нулю, мы также потерпим крах.

Вам необходимо проверить эти нулевые условия и правильно их обработать.