如何生成最大不平衡的AVL树？
我写了一个作为通用排序容器的AVL树的C语言库为了测试，我想要有一种方法来填充一棵树，使它最大程度地不平衡，也就是说，它包含的节点数有最大的高度。
AVL树具有这样的优点：如果从空树开始，按升序(或降序)插入节点，则树总是完全平衡的(也就是说，对于给定的节点数，树有其最小高度)。从空树T0开始，为每个节点n生成精确平衡的AVL树TN的整数键序列是简单的。
- K1=0
- Kn+1=kn+1，即kn=n-1
我正在寻找一个(希望是简单的)整数键序列，当插入到最初的空树T0中时，生成的AVL树T0，...，TN都是最大的联合国平衡。
我也会对一个解感兴趣，其中只有最后一棵树TN是最大不平衡的(节点数n将是算法的一个参数)。
满足约束条件的解
- 最大(K1，...，kn)-min(K1，...，kn)+1≤2n
Stack Overflow用户
发布于 2018-02-06 19:11:16
假设：
- 设U(N)表示高度为n的最大不平衡AVL树中的节点数。
- U(0)=0
- U(1)=1
- U(N)=U(n-1)+U(n-2)+1(n>=2)(即一个根节点加两个最大不平衡子树)
- 为了方便起见，让我们假设U(n-1)总是左子树，U(n-2)总是右边的。
- 让每个节点由一个唯一的字符串表示，该字符串表示从根到节点的路径。根节点是空字符串，级别1节点是“L”和“R”，级别2节点是“LL”、“LR”、“RL”和“RR”等等。
结论：
- U(N)中A级节点的有效字符串是A字符，且满足不等式：n-count(“L”)-2*计数(“R”)>=1
- 计数(“L”)+计数(“R”)=A或计数(“L”)=A-计数(“R”)
- 因此计数(“R”)<=n-A-1
- 我们可以使用以下函数生成给定级别上的所有有效路径，并确定每个节点的键值。
void GeneratePaths(int height, int level) { int rLimit = height - level - 1; GeneratePaths(height, rLimit, level, string.Empty, 0); } void GeneratePaths(int height, int rLimit, int level, string prefix, int prefixlen) { if (prefixlen + 1 < level) { GeneratePaths(height, rLimit, level, prefix + "L", prefixlen + 1); if (rLimit > 0) GeneratePaths(height, rLimit - 1, level, prefix + "R", prefixlen + 1); } else if (prefixlen + 1 == level) { InsertNode(prefix + "L", height) if (rLimit > 0) InsertNode(prefix + "R", height); } } void InsertNode(string path, int height) { int key = fibonacci(height); int index = height - 2; for (int i=0; i < path.length(), i++) { int difference = fibonacci(index); char c = path.charAt(i); if (c == 'L') { key -= difference; index -= 1; } else if (c == 'R') { key += difference; index -= 2; } } InsertKey(key); }
如果使用这些函数生成U(5)树，就会得到这个结果。(注意，树左侧的键遵循Fibonacci序列，从1到5，)
5
3 7
2 4 6 8
1 3 4 6
1https://stackoverflow.com/questions/-100007353
复制相似问题