C # родовое дерево B + - PullRequest
Новая
       1

C # родовое дерево B +

1 голос
/ 26 июня 2011

Я реализую дерево B + с использованием C #.

Теперь, насколько я понимаю, узел дерева должен содержать несколько ключей (порядок-1) и порядковый номер указателей на записи или другие узлы, т. Е. Только конечные узлы будут содержать действительные указатели на записи и внутренние узлы будут содержать указатели на другие узлы.

Проблема, с которой я столкнулся в этой реализации, связана с обобщением C #

Класс узла объявлен как: 

class Node< K,V >
{
    K [] keys ;
    V [] values;
}

Теперь, когда я пытаюсь поместить узел в массив значений как таковой 

_root.Values[0] = left ; // left being of type Node<K,V>

Я получаю следующую ошибку:

Невозможно неявно преобразовать тип 'BTree_Library.Node' в 'V'

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

Итак, в заключение:

  1. В C я бы использовал: ( void* values; ) Я ищу эквивалент этого в C #.

  2. Пока мы обсуждали тему, правильно ли я понял структуру дерева B + в отношении узлов и записей взаимозаменяемы для указателей узлов?

Ответы [ 2 ]

3 голосов
/ 26 июня 2011

Вы хотите, чтобы ваши конечные узлы и ваши внутренние узлы работали по-разному, при этом все еще имея возможность ссылаться на них обоих как на узлы.Это описывает иерархию наследования: 

abstract class Node<K, V>
{
    public K[] Keys { get; protected set; }
}

class LeafNode<K, V> : Node<K, V>
{
    public V[] Values { get; protected set; }
}

class InnerNode<K, V> : Node<K, V>
{
    public Node<K, V> Children { get; protected set; }
}

Другой вариант - использовать C # эквивалент void*, то есть object, но это будет означать, что код больше не является типобезопасным, и вы могли быдолжны быть повсюду.Я бы не рекомендовал делать это.

При этом, почему вы создаете свое собственное B-дерево?Это полезно только при хранении данных на диске, а не в памяти.Если вы делаете это только для того, чтобы иметь ассоциативный массив, в .Net есть классы, которые уже реализуют его (например, Dictionary<K,V> или SortedDictionary<K,V>), и они прекрасно работают.

1 голос
/ 26 июня 2011

Предполагается, что _root.Values[0] = left выполняется изнутри класса и что Values является свойством, эквивалентным values.

Если V всегда будет типом Node, вы можете попробовать что-то вроде 

interface INode {
}

class Node<K, V> : INode where V : INode {

}

Это заставит V наследовать от BTree_Library.Node, что позволит компилировать эту строку без каких-либо ошибок.

Если V не всегда будет производным от Node, то я думаю, что дженерики могут быть неправильным способом решения этой проблемы.

...