, чтобы узнать, сбалансировано ли бинарное дерево или нет.

Question

Бинарное дерево считается сбалансированным по высоте, если правое поддерево его левого поддерева & сбалансировано и разница между высотой левого поддерева и правый подрезок меньше или равен 1.

Мне нужно выяснить, сбалансировано ли данное двоичное дерево или нет!

на основе выше концепции я использовал следующий код:

bool isbalanced(struct node *root) 
{ 
    int left,right; 
    if(root==NULL) 
    return true; 
    else 
    { 
     left=height(root->left); 
     right=height(root->right); 
     if(abs(left-right)<=1 && isbalanced(root->right)==true && isbalanced(root->left)==true) 
     return true; 
     else 
     { 
      return false; 
     } 
    } 
} 

Я вычислил высоту, используя отдельную высоту() функции:

int height(struct node *root) 
{ 
    if(root==NULL) 
    return 0; 
    int left=height(root->left); 
    int right=height(root->right); 
    if(left>right) 
    return 1+left; 
    else 
    return 1+right; 
} 

Я получаю правильное решение, если дерево сбалансировано или несбалансировано. Но если данное дерево искажено, сложность времени будет O (n^2).

Может ли быть способ, чтобы я мог выполнить эту задачу более эффективным способом?

Answer 1

Вы просматриваете левое и правое поддеревья дважды: один раз, чтобы получить их высоту и снова, чтобы проверить, сбалансированы ли они. Вы можете исключить половину работы, используя структуру, которая содержит как высоту, так и сбалансированный флаг, передавая одну структуру вниз для заполнения левым поддеревом, а другая справа.

Вы можете улучшить это еще больше, используя информацию из левого поддерева при сканировании справа (или наоборот). Можно использовать левую информацию поддерева (с соответствующей бухгалтерией), чтобы срезать правильный поиск поддерева во многих случаях, когда общее дерево несбалансировано, но каждое поддерево сбалансировано.

_{детали бухгалтерское остается в качестве упражнения для читателя}

Answer 2

Учитывая данное дерево как корни дерева, мы можем вычислить высоту всех узлов с одной глубиной первого поиска на данном дереве. Эскиз предлагаемого решения:

int isbalanced(struct node *root) 
{ 
    int left,right; 
    if(root==NULL) 
    return 0; 
    else 
    { 
     left=isbalanced(root->left); 
     right=isbalanced(root->right); 
     if(left==-1||right==-1||fabs(left-right)>1){ 
      return -1; // it indicates the tree rooted at root or below is imbalanced 
     }else{ 
      return max(right,left)+1; 
     } 
    } 
} 

Дерева несбалансированный, если функция указана выше возвращает -1, сбалансировано в противном случае. Ему не нужна функция высоты.

время выполнения: O (V + E)

Обратите внимание: код не протестирован