Справочная проблема C # - PullRequest
Новая
       11

Справочная проблема C #

5 голосов
/ 12 февраля 2010

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

Мое красно-черное дерево должно содержать строковые ключи, и объект, который я создал для каждого узла, выглядит следующим образом: 

class sRbTreeNode
{
    public sRbTreeNode Parent = null;
    public sRbTreeNode Right = null;
    public sRbTreeNode Left = null;
    public String Color;
    public String Key;

    public sRbTreeNode()
    {
    }

    public sRbTreeNode(String key)
    {
        Key = key;
    }
}

Я уже добавил несколько основных способов печати дерева, поиска корня, ключа min / max (по алфавиту) и т. Д. *

У меня проблемы со вставкой узлов (следовательно, построение дерева). Любой, кто знаком с красно-черными деревьями, знает, что при добавлении узла в одну сторону вы могли бы изменить баланс дерева. Чтобы это исправить, вам нужно «вращаться» вокруг узлов дерева, чтобы сбалансировать дерево.

Я написал метод RightRotate и LeftRotate в псевдокоде, а затем, когда попытался реализовать его в C #, я столкнулся с кучей проблем с ссылками с созданным объектом sRbTreeNode.

Это псевдокод, который я написал для метода LeftRotate: 

LeftRotate(root, node)
    y <- node.Right;
    node.Right <- y.Left;
    if (y.Left != null)
        y.Left.Parent <- node;
    y.Parent <- node.Parent;
    if (node.Parent = null)
        root <- y;
    else
        if (node = node.Parent.Left)
            node.Parent.Left = y;
        else
            node.Parent.Right = y;
    y.Left <- node;
    node.Parent <- y

Я получил предложение реализовать его прямо, но без использования ключевого слова ref, которое я попробовал сначала. Вот как я это сделал: 

public static void LeftRotate(sRbTreeNode root, sRbTreeNode node)
    {
        sRbTreeNode y = node.Right;
        node.Right = y.Left;
        if (y.Left != null)
            y.Left.Parent = node;
        y.Parent = node.Parent;
        if (node.Parent == null)
            root = y;
        else
            if (node == node.Parent.Left)
                node.Parent.Left = y;
            else
                node.Parent.Right = y;
        y.Left = node;
        node.Parent = y;
    }

Теперь, когда я отлаживаю, я вижу, что он работает нормально, но объекты, которые я передаю этому методу, вращаются только в рамках метода. Когда он покидает этот метод, кажется, что не было никаких изменений в реальных узлах. Вот почему я подумал об использовании ключевых слов 'ref'.

Что я делаю не так?

Ответы [ 3 ]

2 голосов
/ 12 февраля 2010

Потому что в теле вашего метода вы делаете это: 

root = y;

вам нужно передать root с модификатором ref. node не нужен, потому что сам node никогда не обновляется, чтобы указывать на другое ndoe. .

1 голос
/ 12 февраля 2010

Мои рекомендации:

  • Не включать родительские указатели. Они не важны для алгоритмов вставки или удаления и сделают ваш код более сложным. Например, LeftRotate может быть записано только с одним параметром и будет примерно вдвое длиннее, если вы не используете родительские указатели.
  • Используйте enum для свойства Color вместо string и инициализируйте его в конструкторе.
  • Прочитайте эту статью , если вы этого еще не сделали.
1 голос
/ 12 февраля 2010

Я не понимаю, почему у вас должны были возникнуть проблемы со ссылками - левый / правый / родительский узлы можно скопировать так же, как в этом псевдокоде.

Вы сможете расширить его до C # без особых хлопот - если только вы не используете ключевое слово 'ref', и в этом случае вы вполне можете получить непредсказуемые результаты.

Возможно, если бы вы могли показать код, который вы на самом деле написали до сих пор, и мы можем помочь отладить его.

...