0
Я играл с кодом для внедрения вставки в сбалансированное двоичное дерево AVL, которое будет использоваться в довольно большом проекте. Я выбрал 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);
}