0

さて、私は作成した基本的な二分探索ツリー クラスを取得しました。これは、データを格納する内部ノード クラスに依存します。これは次のようになります (ここでは基本的な部分のみを示しています)。

public class TreeSet<T> where T : IComparable<T>
{
    private Node root = null;

    public void Insert(T t)
    {
        if (root == null)
            root = new Node(t);
        else
            root.Insert(t);
    }

    internal class Node
    {
        protected Node left, right;
        private T data;

        public Node(T t)
        {
            data = t;
        }

        public virtual void Insert(T t)
        {
            int compare = t.CompareTo(data);
            if (compare < 0)
            {
                if (left == null)
                    left = new Node(t);
                else
                    left.Insert(t);
            }
            else if (compare > 0)
            {
                if (right == null)
                    right = new Node(t);
                else
                    right.Insert(t);
            }
        }
    }
}

明らかに検索メソッド、列挙子などがありますが、これらは関連するビットです。現在、これは単なる基本的な BST であり、バランスが取れているかどうかを確認するための努力は何もしていませんが、すべての挿入および検索ロジックを処理しています。これを拡張して AVL ツリーや Red-Black などを作ろうとすると、問題が発生します...

public class AvlTree<T> : TreeSet<T> where T : IComparable<T>
{
    internal new class Node : TreeSet<T>.Node
    {
        public Node(T t) : base(t) {}

        public int Depth
        {
            get
            {
                if (left == null && right == null)
                    return 0;
                else if (left == null)
                    return right.Depth + 1;
                else if (right == null)
                    return left.Depth + 1;
                else
                    return Max(left.Depth, right.Depth) + 1;
            }
        }

        public override void Insert(T t)
        {
            base.Insert(t);

            //Do the AVL balancing stuff
        }
    }
}

すでに問題があります -親クラスでは 変数leftとright変数が であると宣言されておりTreeSet<T>.Node、 ではありませんAvlTree<T>.Node。しかしDepth、バランシングが必要かどうかを判断するには変数が必要です。もちろん、それらをキャストできますが、ノードは親のノードで作成されるため、うまくいきませんInsert()関数であり、適切なクラスではありません。もちろん、すべてのコードを新しい拡張されていないクラスにコピーすることもできますが、それは多くの重複コードであり、そのほとんどは同じです。(Red-Black ツリーまたは Splay ツリーを作成することもできますが、これもバランシング アルゴリズムを除いてほとんど同じです。) そして最終的には、そのようなすべての BST に対して 1 つの親クラスを持つと便利な場合があるため、どのツリーを変更するかを決めることができます。ツリーを使用してコードを変更せずに使用している型。(これが本格化するまでは、どのバランシング アルゴリズムのパフォーマンスが優れているかを判断するのは困難です。)

このようなことを処理する良い方法はありますか？つまり、親クラスによって作成された場合でも、変数leftとright変数が適切なサブクラスを格納し、正しいクラスとして作成されていることを確認しますか? それとも、この場合、コードを再利用しようとすることさえ間違いであり、コードが重複しているにもかかわらず、AvlTree を TreeSet から完全に分離したほうがよいでしょうか?

4

0 に答える 0