我一直在使用代码来实现插入到 AVL 平衡二叉树中，该二叉树将用于大型项目。我选择了 AVL 而不是红黑和其他平衡方法，因为它简单，因为我需要确信它是正确的。我的测试代码工作正常 - 但是我被引导相信可以使用可变余额限制/容差。我还没有看到这是作为 AVL 的一部分实现的，是的，我真的不需要它，但作为调试的一部分，我测试过它失败了。看起来更高的平衡限制可能需要在经过一些旋转后向上传播树以降低树的高度。
有没有其他人成功尝试过可变余额限制？注意：如果可以的话，我不想走树来重新计算平衡因子。在这个阶段，除非有人有一些有用的想法，否则我可能只会坚持 1 的余额限制。
在下面的测试代码中，如果 BALANCELIMIT 为 1，则所有似乎都有效 - 但如果更高则无效
#include <stdio.h>
#define BALANCELIMIT 1 // 1 is good - anything else seems bad
#define MINI(a, b) (a<=b ? a : b)
#define MAXI(a, b) (a>=b ? a : b)
struct TREE { // Standard binary tree structure with a SIGNED balance factor (normally -1, 0, or 1)
struct TREE *left;
struct TREE *right;
signed char balance;
int key;
} *root = NULL;
int count = 0; // Keep a count of created nodes for debugging purposes
struct TREE *rotateLeft(struct TREE *r) { // Rotate left routine to replace node with node->left
struct TREE *n = r->left;
r->left = n->right;
n->right = r;
r->balance += 1 - MINI(0, n->balance); // Balance calculation sourced from:-
n->balance += 1 + MAXI(0, r->balance); // http://oopweb.com/Algorithms/Documents/AvlTrees/Volume/AvlTrees.htm
return n;
}
struct TREE *rotateRight(struct TREE *r) { // Rotate right routine to replace node with node->right
struct TREE *n = r->right;
r->right = n->left;
n->left = r;
r->balance += -1 - MAXI(0, n->balance); // Balance calculation sourced from:-
n->balance += -1 + MINI(0, r->balance); // http://oopweb.com/Algorithms/Documents/AvlTrees/Volume/AvlTrees.htm
return n;
}
int insert(struct TREE **pnode, int key) {
struct TREE *node = *pnode;
if (node == NULL) { // If no node then create one and initialise it to contain new value
node = malloc(sizeof(struct TREE));
if (node == NULL) exit(0);
node->left = NULL;
node->right = NULL;
node->balance = 0;
node->key = key;
*pnode = node;
count++;
return 1; // Recursion exit - signal tree height change (for new node)
}
int cmp = key - node->key;
if (cmp == 0) return 0;
if (cmp < 0) { // Decide if we need to recurse to the left or to the right
if (insert(&node->left, key)) { // For smaller item recurse left - finish unless a height change was signalled
if (--node->balance < 0) { // Adjust node balance - if it got worse then we need to do something...
if (node->balance >= -BALANCELIMIT) return 1; // If height change is within limit just propagate it upward
if (node->left->balance > 0) { // If left path heavy to right then do a double rotation
printf("rotateRightLeft node %d to replace %d around %d\n", node->left->right->key, node->key, node->left->key);
node->left = rotateRight(node->left); // Double rotate by first rotating left right node up one level
*pnode = rotateLeft(node); // replacing left - and then rotate it again to replace current node
} else {
printf("rotateLeft node %d to replace %d\n", node->left->key, node->key);
*pnode = rotateLeft(node); // Left path heavy to left so just rotate left node up one level
}
}
}
} else {
if (insert(&node->right, key)) { // For larger item recurse right - finish unless a height change was signalled
if (++node->balance > 0) { // Adjust node balance - if it got worse then we need to do something...
if (node->balance <= BALANCELIMIT) return 1; // If height change is within limit just propagate it upward
if (node->right->balance < 0) { // If right path heavy to left then do a double rotation
printf("rotateLeftRight node %d to replace %d around %d\n", node->right->left->key, node->key, node->right->key);
node->right = rotateLeft(node->right); // Double rotate by first rotating right left node up one level
*pnode = rotateRight(node); // replacing right - and then rotate it again to replace current node
} else {
printf("rotateRight node %d to replace %d\n", node->right->key, node->key);
*pnode = rotateRight(node); // Right path heavy to right so just rotate right node up one level
}
}
}
}
return 0; // Recursion exit - signal no further action required
}
void tree_print(struct TREE *node, int depth) { // Recursive tree print routine
if (node != NULL) {
tree_print(node->left, depth+1);
printf("%*.s%d (%d)\n", depth * 5, "", node->key, node->balance);
tree_print(node->right, depth+1);
}
}
int check_count; // node count while checking tree
int check(struct TREE *node) { // Recursive tree check routine - check count, balance factor and key order
int lh = 0, rh = 0;
if (node != NULL) {
check_count++;
if (node->left != NULL) {
if (node->key < node->left->key) {
printf("ERROR node key %d smaller than left node\n", node->key);
exit(0);
}
lh = check(node->left); // check left subtree and get its height
}
if (node->right != NULL) {
if (node->key > node->right->key) {
printf("ERROR node key %d bigger than right node\n", node->key);
exit(0);
}
rh = check(node->right); // check right subtree and get its height
}
if (node->balance != rh - lh) {
printf("ERROR balance %d for %d should be %d\n", node->balance, node->key, rh-lh);
exit(0);
}
}
return MAXI(lh, rh) + 1; // Return tree height
}
void tree_check(struct TREE *r) { // wrapper function for tree check routine
check_count = 0;
check(r);
if (check_count != count) {
printf("ERROR Check count is %d not %d \n", check_count, count);
exit(0);
}
}
main() {
int i;
for (i=0; i<10; i++) insert(&root, rand() % 30000);
for (i=0; i<10; i++) {
int r = rand() % 30000;
insert(&root, r);
insert(&root, r+1);
insert(&root, r+2);
insert(&root, r-1);
insert(&root, r-2);
}
tree_print(root, 0);
tree_check(root);
printf("-- Done ------- %d\n\n\n", count);
}