Как пройти назад в дереве AVL от определенного узла? - PullRequest
0 голосов
/ 13 июня 2019

Я успешно реализовал ранговое дерево 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);
}

ПРИМЕЧАНИЕ: дерево работает отлично, со всеми добавлениями и родительскими обновлениями, и тому подобное, я протестировал остальное, я почти уверен, что проблема в самой функции.

Любая помощь приветствуется,

Спасибо

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...