一半填充二进制搜索树进行测试的最佳方法

Question

我想设置一个测试，以查看多个线程可以更改树的速度，以便我需要在范围内设置带有键的初始树0 - （（2^n）-1）说所有插入的均匀节点以形成平衡树。
说n = 4;我们需要插入0,2,4,6,8,10,12,14，但按照此顺序；[8]，[4,12]，[0,2,6,10,14]。或[6]，[2,10]，[0,4,8,14,12]会产生同样平衡的树。
目前，我只是添加2^（n-1），即[8]然后，每秒2^（n-2）的每一倍数，即[4,12]，然后每秒2^（n-3）的每一倍数，即[2，6,10,14]等等，然后我在最后添加0。
这是C 中的代码，但我不太担心语言具体算法本身。

        BST tree = BST();           
        INT64 diff = HMK;//HMK = Half Max Key
        INT64 arrayN[HMK];
        INT64 cur = diff;
        INT64 i = 0;
        Node aNode[HMK];
        while (diff >= 2) {
            cur = diff;
            while (cur < MAX_KEY) {
                aNode[i] = Node();
                aNode[i].key=cur;
                tree.add(&aNode[i]);
                i++;
                cur += 2*diff;
            }
            diff = diff / 2;
        }
        aNode[i] = Node();
        aNode[i].key = 0;
        tree.add(&aNode[i]);

有更好的方法吗？

Answer 1

如果您不在乎以后更改树，则首先创建骨架树图可能最容易，然后放入适合该位置的值。p>也就是说，由于您想要0和 INT_MAX之间的值，因此根为 INT_MAX/2。如果有一个左孩子，那是 INT_MAX/4;如果有一个正确的孩子，那是3*INT_MAX/4。位模式应该很明显：100....，010 ... , 110 ...`。显然，这仅限于n个级别，因为在深度D时必须设置（n-d）'位。