4

С учебными целями создаю собственные реализации некоторых структур данных. Надо создать обычное бинарное дерево поиска, затем от него унаследовать красно-чёрное и другие самосбалансированные. Для каждого типа дерева есть два класса: собственно дерево и узел (поскольку узлы обычного и красно-чёрного деревьев различаются — второй содержит ещё информацию о цвете). Соответственно просто унаследовать от обычного дерева красно-чёрное не получится.

Я пытаюсь решить это проблему при помощи обобщённых классов. Класс GenTree выглядит следующим образом:

package BasicTrees;

public abstract class GenTree<KeyType extends Comparable, Type,
        NodeType extends GenNode<KeyType, Type, NodeType>> 
    implements Iterable<NodeType> {

    protected NodeType root;

    protected abstract NodeType newNode(KeyType key, Type value);
    ...
}

в этом классе реализованы операции вставки, поиска, удаления, итератор для обычного дерева. Метод newNode реализуется уже в каждом конкретном типе дерева, и служит в дальнейшем вместо конструктора для создания новых узлов. Класс GenNode выглядит следующим образом:

package BasicTrees;

public class GenNode<KeyType extends Comparable, Type,
            NodeType extends GenNode<KeyType, Type, NodeType>> {

    protected final KeyType key;
    protected Type value;
    protected NodeType left;
    protected NodeType right;
    protected NodeType parent;

    protected GenNode(KeyType key, Type value) {
        this.key = key;
        this.value = value;
    }
}

После этого обычное дерево создаётся тривиально классами Tree:

package BasicTrees;

public class Tree<KeyType extends Comparable, Type>
        extends GenTree<KeyType, Type, Node<KeyType, Type>> {

    @Override
    protected Node<KeyType, Type> newNode(KeyType key, Type value) {
        return new Node<>(key, value);
    }
}

и Node:

package BasicTrees;

public class Node<KeyType extends Comparable, Type>
        extends GenNode<KeyType, Type, Node<KeyType, Type>> {

    protected Node(KeyType key, Type value) {
        super(key, value);
    }
}

пакет BasicTree также содержит класс TreeIterator.

Для создания красно-чёрного и других самосбалансированных деревьев требуется создать отдельный пакет RBTrees, чтобы они не путались. Классы RBTree и RBNode наследуются от GenTree и GenNode аналогично. В классе RBNode добавляется поле, отвечающее за цвет узла. В классе RBTree требуется переписать методы, отвечающие за вставку и удаление узлов, метод поиска и итератор остаются теми же. Для этого переписанные методы класса RBTree должны иметь доступ к protected полям left, right, parent, объявленным в классе GenNode и унаследованным RBNode. Но модификатор protected доступа к ним не даёт, так как RBTree не является наследником GenNode и не находится с ним в одном пакете.

Можно ли как-то дать доступ к защищённым полям наследников GenNode для наследников GenTree, не давая его всей программе? Или единственным выходом будет создание в классе RBNode геттеров и сеттеров с видимостью пакета, а классе RBTree их использовать? Но тогда придётся их создавать каждый раз при создании нового типа дерева. Имеет ли смысл создание этих геттеров и сеттеров с модификатором protected в классе GenNode? В таком случае они создаются один раз.

Хотелось бы услышать мнение сообщества на этот счёт, а также замечания по структуре программы в целом. Был бы рад узнать, можно ли мою задумку реализовать проще.

Спасибо за возможность задать вопрос и подумать над ним в процессе написания. Вариант с геттерами и сеттерами в GenTree (который мне кажется оптимальным) я придумал уже в процессе когда писал.

3
  • 1
    Как-то все мудрёно. 13 авг 2015 в 12:33
  • Немного не понял, как то всё сложно. Чем отличается красно чёрное дерево от обычного? Это вроде просто нодой и способом хранения данных? Разве не достаточно наследоваться от обычного дерева, и обычной ноды, и переопределить те методы которые различаются?
    – Чад
    13 авг 2015 в 12:59
  • Просто унеследовать не получится, потому если наследовать красно-чёрный узел от обычного узла, то его поля left, right, parent по-прежнему будут типа обычного узла. То же самое касается поля root в дереве. Можно, конечно, использовать явное приведение типов, но это небезопасно, придётся всегда явно отслеживать, что в полях left, right, parent содержатся ссылки на объекты нужных классов. 14 авг 2015 в 14:33

2 ответа 2

1

Я бы всё разместил в одном пакете, а классы, связанные с конкретным типом дерева, сделал бы вложенными классами. И активно бы использовал package-private доступ. Именно так реализованы, например, HashMap и LinkedHashMap в OpenJDK. Они довольно интенсивно переиспользуют код друг друга, переиспользуемые поля, методы и классы все объявлены package-private.

В целом package-private и организация кода с помощью вложенных классов — это очень хорошо. Не факт, например, что вы вообще хотите выставлять на публику базовый класс GenTree. Опубликовав его одиножды, вы навсегда будете привязаны к нему. А вдруг в дальнейшем рефакторинге вы захотите его сильно переделать (например, добавить поддержку небинарных деревьев) или вообще от него отказаться? По большому счёту это деталь реализации. Поэтому его тоже можно сделать package-private.

0

Раз уж одному типу дерева соответствует один тип узлов, то можно делать конкретную реализацию узла внутренним классом его дерева.

Тогда данный тип дерева будет иметь доступ к его закрытым (private) полям и методам. Узел при этом по-прежнему может наследоваться от абстрактного узла.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.