0

我正在尝试创建一个平衡的三元树。为此，我想以确保构建树的顺序插入键，以便每个节点均匀地划分其下方的字符范围。所以理想情况下，第一个节点是“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);
        }
    }
4

0 回答 0