Java: реализация параллельной иерархии деревьев и ее узлов

Question

Чтобы попрактиковаться в структурах данных, я реализую свою собственную библиотеку деревьев.Я начал с BST и в следующем я собираюсь реализовать AVL Tree, Red-Black Tree и, возможно, больше.AVL и RBT также являются деревьями BST, поэтому некоторая иерархия классов довольно очевидна.Проблема, с которой я столкнулся, состоит в том, что у всех этих деревьев есть другие типы узлов - у AvlNode есть флаг коэффициента баланса, у RgbNode есть цветной флаг, BstNode не требуется никакой дополнительной информации (несмотря на ссылки на parent, children и value, которые нужны всем узлам),Итак, у меня есть иерархия узлов и иерархия деревьев.Я мог бы дать некоторый атрибут флага BstNode и использовать его в расширении классов, но это, безусловно, не очень хороший способ сделать это.

Проблема в том, как справиться с тем фактом, что, например, Bst.findNode () будетвернуть BstNode, но в Avl мне нужен AvlNode, несмотря на то, что методы findNode () будут одинаковыми в обоих (кроме возвращаемого типа).

Мне нужна помощь в планировании иерархий или, если эти параллельные иерархии (как запах кода) вообще плохая идея, мне нужен обходной путь, потому что я понятия не имею, как это сделать правильно.

BstTree Class:

public class BstTree<T extends Comparable> implements Iterable
{
    private BstNode<T> root;

    public void addValue(T value)
    {
        BstNode node = new BstNode(value);
        addNode(node);
    }

    public void addNode(BstNode<T> node)
    {
        ...
    }

    public boolean removeNode(T value)
    {
       ...
    }


    public BstNode findNode(T value)
    {
        ...
    }
    //other less significant methods
}

BstNode class:

public class BstNode<T extends Comparable>
{
    private static int lastId = 0;
    private int id;
    private T value;
    private BstNode parent = null;
    private BstNode leftChild = null;
    private BstNode rightChild = null;

    public BstNode(T value) {
        this.id = ++lastId;
        this.value = value;
    }

    public boolean isGreaterThan(BstNode n)
    {
        //...
    }

    public boolean hasLeftChild()
    {
        //...
    }

    public boolean hasRightChild()
    {
        //...
    }

    public boolean hasParent()
    {
        //...
    }

    public boolean isLeaf()
    {
        //...
    }

    public boolean hasOnlyOneChild()
    {
        //...
    }

    public BstNode getOnlyChild(BstNode node)
    {
        ...
    }

    public boolean isLeftChildren()
    {
        ...
    }

    public BstNode getConsequentNode()
    {
        ...
    }
}

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

Answer 1

Я бы сделал что-то вроде этого:

public abstract class BstTree<T extends Comparable,N extends BstNode<T,N>> {
    private N root;
...

    public void addValue(T value)
    {
        N node = newNode(value);
        addNode(node);
    }

    public abstract N newNode(T value);

    public void addNode(N node)
    {
        // ...
    }
}

public class BstNode<T extends Comparable,N extends BstNode<T,N>>
{
    private T value;
    private N parent = null;
    private N leftChild = null;
    private N rightChild = null;

    public BstNode(T value) {
        this.value = value;
    }

    public N getOnlyChild(N node)
    {
        // ...
    }
...
}

public class AVLTree<T extends Comparable> extends BstTree<T,AVLNode<T>> {
    ...
    @Override
    public AVLNode<T> newNode(T value) {
        return new AVLNode<>(value);
    }
}

public class AVLNode<T extends Comparable> extends BstNode<T,AVLNode<T>> {
    ...

    public AVLNode(T value) {
        super(value);
    }

    @Override
    public AVLNode<T> getOnlyChild(AVLNode<T> node) {
        return super.getOnlyChild(node);
    }
    ...
}