如何生成最大不平衡的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
回答 3
Stack Overflow用户
发布于 2018-02-06 17:15:39
基本解
Fibonacci树有几个属性，可以用来形成紧凑的Fibonacci树：
- Fibonacci树中的每个节点本身就是Fibonacci树。
- 高度为n的Fibonacci树的节点数等于fn+2-1.
- 节点与其左子节点之间的节点数等于节点的左子节点的右子节点数。
- 节点与其右子节点之间的节点数等于该节点的右子节点的左子节点数。
在不失去通用性的情况下，我们将假设Fibonacci树具有以下附加属性：
- 如果节点的高度为n，则左子具有n-2，右子具有高度n-1。结合这些性质，我们发现在n高的节点与其左、右子节点之间的节点数等于FN-1-1，我们可以利用这个事实生成紧致Fibonacci树：static int fibs[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170}; void fibonacci_subtree(int root, int height, int *fib) { if (height == 1) { insert_into_tree(root); } else if (height == 2) { insert_into_tree(root + *fib); } else if (height >= 3) { fibonacci_subtree(root - *fib, height - 2, fib - 2); fibonacci_subtree(root + *fib, height - 1, fib - 1); } } ... for (height = 1; height <= max_height; height++) { fibonacci_subtree(0, height, fibs + max_height - 1); }该算法生成给定高度下可能的最小节点数，并产生最小可能范围。可以通过使根节点不是零来改变范围。紧填充算法基本解决方案只产生Fibonacci树，它总是有fn+2-1节点.。如果想要生成一个具有不同节点数的不平衡树，同时仍然最小化范围，那该怎么办？在这种情况下，需要生成下一个更大的Fibonacci树，只需做一些修改：
- 序列末尾的一些元素将不会被插入。
- 这些因素将造成差距，需要跟踪这些差距的位置。
- 节点之间的差异需要适当地缩小。
这里有一种方法仍然利用了解决方案的递归特性：
void fibonacci_subtree(int root, int height, int *fib, int num_gaps, bool prune_gaps)
{
if(height < 1)
return;
if(prune_gaps && height <= 2) {
if(!num_gaps) {
if(height == 1) {
insert_into_tree(root);
} else if(height == 2) {
insert_into_tree(root + *fib);
}
}
return;
}
if(height == 1) {
insert_into_tree(root);
} else {
int max_rr_gaps = *(fib - 1);
int rr_gaps = num_gaps > max_rr_gaps ? max_rr_gaps : num_gaps;
num_gaps -= rr_gaps;
int max_rl_gaps = *(fib - 2);
int rl_gaps = num_gaps > max_rl_gaps ? max_rl_gaps : num_gaps;
num_gaps -= rl_gaps;
int lr_gaps = num_gaps > max_rl_gaps ? max_rl_gaps : num_gaps;
num_gaps -= lr_gaps;
int ll_gaps = num_gaps;
fibonacci_subtree(root - *fib + lr_gaps, height - 2, fib - 2, lr_gaps + ll_gaps, prune_gaps);
fibonacci_subtree(root + *fib - rl_gaps, height - 1, fib - 1, rr_gaps + rl_gaps, prune_gaps);
}
}主循环稍微复杂一些，以适应任意范围的键：
void compact_fill(int min_key, int max_key)
{
int num_nodes = max_key - min_key + 1;
int *fib = fibs;
int max_height = 0;
while(num_nodes > *(fib + 2) - 1) {
max_height++;
fib++;
}
int num_gaps = *(fib + 2) - 1 - num_nodes;
int natural_max = *(fib + 1) - 1;
int max_r_gaps = *(fib - 1);
int r_gaps = num_gaps > max_r_gaps ? max_r_gaps : num_gaps;
natural_max -= r_gaps;
int root_offset = max_key - natural_max;
for (int height = 1; height <= max_height; height++) {
fibonacci_subtree(root_offset, height, fibs + max_height - 1, num_gaps, height == max_height);
}
}闭形解
如果查看基本解决方案生成的每一对单词之间的差异，会发现它们在Fibonacci序列的两个顺序元素之间交替。此交替模式Fibonacci word:
Fibonacci字是二进制数字(或来自任何两个字母的字母的符号)的特定序列.。斐波那契词是由重复级联形成的，就像斐波那契数是由重复加法形成的一样。
结果发现Fibonacci字的闭形解:
static double phi = (1.0 + sqrt(5.0)) / 2.0;
bool fibWord(int n)
{
return 2 + floor(n * phi) - floor((n + 1) * phi);
}可以使用这个封闭的解决方案来使用两个嵌套循环来解决这个问题：
// Used by the outer loop to calculate the first key of the inner loop
int outerNodeKey = 0;
int *outerFib = fibs + max_height - 1;
for(int height = 1; height <= max_height; height++) {
int innerNodeKey = outerNodeKey;
int *smallFib = fibs + max_height - height + 3; // Hat tip: @WalterTross
for(int n = fibs[height] - 1; n >= 0; n--) {
insert_into_tree(innerNodeKey);
// Use closed-form expression to pick between two elements of the Fibonacci sequence
bool smallSkip = 2 + floor(n * phi) - floor((n + 1) * phi);
innerNodeKey += smallSkip ? *smallFib : *(smallFib + 1);
}
if(height & 0x1) {
// When height is odd, add *outerFib.
outerNodeKey += *outerFib;
} else {
// Otherwise, backtrack and reduce the gap for next time.
outerNodeKey -= (*outerFib) << 1;
outerFib -= 2;
}
}Stack Overflow用户
发布于 2018-02-06 17:38:22
我已经找到了我的问题的答案，但我仍然希望能够找到一个更简单的，特别是更节省时间的算法，而不是更少的空间效率算法，希望它也具有更好的关键范围属性。
其思想是生成Fibonacci树，直到给定的高度(必须事先知道)，完全避免所有树的旋转。中间树通过选择插入顺序保持AVL平衡。因为它们有两个Fibonacci树的下部的高度，所以它们都是最大不平衡的。
插入是通过在Fibonacci树序列中插入几乎所有节点来完成的，但是对于每个虚拟树，只有效地插入高度为1的子树的节点。这些是两个连续斐波纳契树之间的“增量”节点。
下面是它在这种情况下的工作原理max_height = 5:
insert 0
=> Fibonacci tree of height 1 (1 node):
0
insert 8
=> Fibonacci tree of height 2 (2 nodes):
0
8
insert -8
insert 12
=> Fibonacci tree of height 3 (4 nodes):
0
-8 8
12
insert -4
insert 4
insert 14
=> Fibonacci tree of height 4 (7 nodes):
0
-8 8
-4 4 12
14
insert -12
insert -2
insert 6
insert 10
insert 15
=> Fibonacci tree of height 5 (12 nodes):
0
-8 8
-12 -4 4 12
-2 6 10 14
15下面是代码(简化)：
void fibonacci_subtree(int root, int height, int child_delta)
{
if (height == 1) {
insert_into_tree(root);
} else if (height == 2) {
insert_into_tree(root + child_delta);
} else if (height >= 3) {
fibonacci_subtree(root - child_delta, height - 2, child_delta >> 1);
fibonacci_subtree(root + child_delta, height - 1, child_delta >> 1);
}
}
...
for (height = 1; height <= max_height; height++) {
fibonacci_subtree(0, height, 1 << (max_height - 2));
}更新
由godel9解决解决了该方案密钥的扩散问题。以下是godel9代码的输出：
insert 0
=> Fibonacci tree of height 1 (1 node):
0
insert 3
=> Fibonacci tree of height 2 (2 nodes):
0
3
insert -3
insert 5
=> Fibonacci tree of height 3 (4 nodes):
0
-3 3
5
insert -2
insert 1
insert 6
=> Fibonacci tree of height 4 (7 nodes):
0
-3 3
-2 1 5
6
insert -4
insert -1
insert 2
insert 4
insert 7
=> Fibonacci tree of height 5 (12 nodes):
0
-3 3
-4 -2 1 5
-1 2 4 6
7下面是最接近我的版本中的代码(这里有一个静态的fibs数组)：
static int fibs[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170 };
void fibonacci_subtree(int root, int height, int *fib)
{
if (height == 1) {
insert_into_tree(root);
} else if (height == 2) {
insert_into_tree(root + *fib);
} else if (height >= 3) {
fibonacci_subtree(root - *fib, height - 2, fib - 2);
fibonacci_subtree(root + *fib, height - 1, fib - 1);
}
}
...
for (height = 1; height <= max_height; height++) {
fibonacci_subtree(0, height, fibs + max_height - 1);
}最后一棵高度为H的斐波那契树有FH+2-1节点，键值之间没有“洞”，并且具有kmax-kroot=fh+1-1。如果有必要，可以通过偏移根的键值，并在算法中可选择地交换左右键，方便地定位密钥范围。
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
复制相似问题