Вычисление коэффициента баланса для дерева 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);
}
1 ответ
Да, я успешно пробовал переменные ограничения баланса на деревьях AVL. Шахта поднялась по дереву после вставки, корректируя факторы баланса. Я также постоянно отслеживал высоту каждого узла (больше из-за лени, чем из-за чего-либо).
Несмотря на то, что формулы, которые вы используете (для корректировки балансовых коэффициентов на пониженных и повышенных узлах после поворота), верны, их недостаточно! (когда BALANCELIMIT больше 1). Вращение (примененное к вершине поддерева) уменьшает высоту поддерева, только если оно делает его более сбалансированным.
В случае двойного вращения, когда BALANCELIMIT равен 1, первое вращение всегда применяется к вершине поддерева с коэффициентом баланса +/- 1, и это переключает знак дисбаланса (это не меняет высоту поддерева, поэтому он не делает недействительным коэффициент баланса узла над поддеревом).
Но когда BALANCELIMIT равен 2 или более, первый поворот (в сценарии двойного вращения) может фактически уменьшить высоту поддерева, к которому он применяется. Простейший пример показан здесь.
- first rotate second rotate
- input output output
- 1 1 3
- \ \ / \
- 4 3 1 4
- / / \ \
- 3 2 4 2
- /
-2
Проблема возникает в результате первого поворота (на 2,3,4 поддереве). Он не только изменяет коэффициенты баланса узлов с номерами 3 и 4. Поскольку это приводит к лучшему балансу поддерева (2,3,4), он улучшает коэффициент баланса узла 1 (с +3 до +2). Ваш код не позволяет этого. Вот почему это ломается. Чтобы продемонстрировать, начните с пустого дерева и вставьте входные данные 1,4,3,2 в указанном порядке в ваше дерево. Первый поворот должен изменить коэффициент баланса узла 1, но это не так. После второго поворота узел 1 должен иметь коэффициент баланса 1, но будет иметь неправильный коэффициент баланса 2.
Добавление кода для коррекции коэффициентов баланса, когда повороты "неожиданно" улучшают высоты поддерева (что, как показано выше, может происходить, когда BALANCELIMIT больше 1), возможно, но я подозреваю, что это будет гораздо сложнее, чем отслеживание и регулировка высот и пересчитывать коэффициенты баланса после каждого оборота.