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

2 ответа 2

1

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

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

0

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

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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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