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

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

如果您不关心以后更改树，最简单的方法可能是先创建骨架树图，然后输入适合该位置的值。

也就是说，由于您想要介于 0 和 INT_MAX 之间的值，因此根将为 INT_MAX/2。如果左边有一个child，就是INT_MAX/4；如果有一个正确的child是3*INT_MAX/4。位模式应该很明显：100....、010...,110...`。显然这仅限于 N 级，因为在深度 D 处必须设置第 (N-D) 位。

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

Best way to half fill binary search tree for test

c++

algorithm

tree

binary-tree