algorithm - バランスの取れた三分木を作成するための順序付け

Question

バランスの取れた三分木を作成しようとしています。そのためには、各ノードがその下の文字の範囲を均等に分割するように、ツリーが構築される順序でキーを挿入したいと考えています。したがって、理想的には、最初のノードが「M」で、両側が「F」と「T」のようになり、各キーが各パーティションの中間点になります。

これを実現するコードを以下に示します。明らかに、考えられるすべての文字のインデックスを事前に計算して保存することもできますが、ルックアップ配列ではなく順序を計算するための算術またはビット操作のアプローチが優れているかどうか疑問に思っています。「M」で正確にバランスをとる必要はありません。最初に中間点をソートする公平なバイナリ再帰分割が必要です。

編集:はい、アルファベットではなくキーを均等に分割できればよいのですが、実行時にこのツリーに追加します。

    /// <summary>
    /// A midpoint first comparison of two strings, 
    /// earliest sort = closest to middle, then middle of each side
    /// and so on down. Designed to create a balanced TernaryTree.
    /// </summary>
    private class MiddleOutComparer : IComparer<string>
    {
        public static readonly MiddleOutComparer Instance = new MiddleOutComparer();
        const string MidPointFirst = "MFTIPCWKRHUGEYBXNOJLQSDVAZ5271368490";
        private int Compare(string a, string b, int index)
        {
            if (index == a.Length && index == b.Length) return 0;
            if (index >= a.Length) return -1;
            if (index >= b.Length) return +1;
            int aValue = MidPointFirst.IndexOf(char.ToUpperInvariant(a[index]));
            int bValue = MidPointFirst.IndexOf(char.ToUpperInvariant(b[index]));
            if (aValue == bValue) return Compare(a, b, index + 1);
            return aValue.CompareTo(bValue);
        }
        public int Compare(string x, string y)
        {
            return Compare(x, y, 0);
        }
    }