Я успешно реализовал ранговое дерево AVL, которое содержит дополнительное поле, содержащее сумму всех ключей в поддереве этого узла (например, для конкретного узла, этот узел имеет sum_of_sub_tree_keys + node_key)
Я хочу реализовать метод, который возвращает сумму всех больших ключей от определенного узла (включая ключ этого узла), то, что делает функция, это обратный переход от данного узла в дереве (вызов родителя), и:
1) если узел происходит с левой стороны этого родителя, тогда я добавляю ключ родителя плюс его правую сумму поддерева.
2) если узел происходит с правой стороны этого родителя, я ничего не добавляю, я просто продолжаю идти по этому пути назад.
В конце концов внешняя функция добавляет ключ узла к результату этой функции, но, похоже, он не работает, может кто-нибудь сказать мне, что не так с моим кодом:
int auxSumOfMaxKeys(Node* node) {
if (node->parent == NULL)
return sumForNode(root->right);
if (node->parent == root && node->parent->left == node)
return sumForNode(root->right) + root->key;
if (node->parent == root && node->parent->right == node)
return sumForNode(node->right);
if (node->parent->left == node)
return auxSumOfMaxKeys(node->parent) + sumForNode(node->parent->right) + node->parent->key;
if (node->parent->right == node)
return auxSumOfMaxKeys(node->parent);
}
int sumOfMaxKeys(Node* node) {
int node_key = node->key;
return node_key + auxSumOfMaxKeys(node);
}
ПРИМЕЧАНИЕ: дерево работает отлично, со всеми добавлениями и родительскими обновлениями, и тому подобное, я протестировал остальное, я почти уверен, что проблема в самой функции.
Любая помощь приветствуется,
Спасибо