C ++ Повышена ли эффективность проверки, сбалансирован ли BST по высоте? - PullRequest
Новая
       1

C ++ Повышена ли эффективность проверки, сбалансирован ли BST по высоте?

1 голос
/ 23 апреля 2020

Я пытаюсь реализовать функцию isOk(Node*, int&), которая проверяет, соблюдается ли следующее свойство для каждого узла BST:

- Высота его левого и правого поддеревьев может отличаться максимум на 1 уровень .

Один пример может быть:

example

Это функция, которую я написал: 

    bool isOk(Node* tree, int& maxH)
    {
        //if leaf, property is respected
        if(!tree->left_ && !tree->right_) return true;

        //otherwise
        int hL = 0;
        int hR = 0;
        bool propL = isOk(tree->left_, hL);
        bool propR = isOk(tree->right_, hR);

        if(propL) hL++;
        if(propR) hR++;
        if(hL - hR => -1 && hL - hR <= 1) {
                maxH = max(hL, hR);
                return true;
        }
        else return false;
    }

Мы Предположим, что структурный узел выглядит примерно так: 

struct Node
{
    Node* left_;
    Node* right_;
    int label_;

    //no constructor or destructor, this is not the focus
};

Первоначально я написал эту часть: 

/*...*/
    int hL = 0;
    int hR = 0;
    bool propL = isOk(tree->left_, hL);
    bool propR = isOk(tree->right_, hR);

    if(propL) hL++;
    if(propR) hR++;
/*...*/

следующим образом: 

int hL = height(tree->left_);
int hR = height(tree->right_);
bool propL = isOk(tree->left_, hL);
bool propR = isOk(tree->right_, hR);

где function height(Node*) is: 

int height( Node* tree)
{
    if(tree== NULL) return 0;
    int leftH = 0;
    int rightH = 0;
    leftH = height(tree->left_);
    rightH = height(tree->right_);
    return 1 + max(leftH, rightH);
}

Теперь, сложность height должна быть O (n), если я не ошибаюсь. Итак, если использовать его внутри моей функции isOk, его общая сложность должна значительно возрасти, верно?

Тем не менее, я пытался отслеживать высоту каждого поддерева, увеличивающегося при каждом hL и hR включении. каждый вызов isOk.

Это что-то не так я сделал? Пожалуйста, поправьте меня, где я не прав.

Спасибо!

1 Ответ

0 голосов
/ 23 апреля 2020

Можно получить isOk, возвращающее pair<bool, int>, где bool представляет, следует ли узлу, возвращающему это значение, указанное свойство или нет, а int представляет его высоту в дереве.

Предположим, pair<boor, int> propL, propR являются значениями, возвращаемыми левым и правым потомками текущего узла соответственно, тогда текущий узел будет удовлетворять указанному свойству iff propL->first == true && propR->first == true && (int)abs(propL->second-propR->second) <= 1. Затем это значение вместе с высотой текущего узла (равной max(propL->second, propR->second) + 1) будет возвращено родителю текущего узла.

...