С учебными целями создаю собственные реализации некоторых структур данных. Надо создать обычное бинарное дерево поиска, затем от него унаследовать красно-чёрное и другие самосбалансированные. Для каждого типа дерева есть два класса: собственно дерево и узел (поскольку узлы обычного и красно-чёрного деревьев различаются — второй содержит ещё информацию о цвете). Соответственно просто унаследовать от обычного дерева красно-чёрное не получится.
Я пытаюсь решить это проблему при помощи обобщённых классов. Класс 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
(который мне кажется оптимальным) я придумал уже в процессе когда писал.