Блог

Главная - Вопросы по программированию - Литкод-1382. Сбалансируйте двоичное дерево поиска

Литкод-1382. Сбалансируйте двоичное дерево поиска

#c #binary-tree #avl-tree

Вопрос:

 struct TreeNodeC {
    int val;
    int height;
    struct TreeNodeC *left;
    struct TreeNodeC *right;
};

struct TreeNodeC *avl = NULL;

int check_balance_factor(struct TreeNodeC *root) {
    int balance_factor = 0;
    if (root->left == NULL amp;amp; root->right == NULL) {
        balance_factor = 0;
    } else
    if (root->left == NULL amp;amp; root->right != NULL) {
        balance_factor = (root->right)->height;
    } else
    if (root->left != NULL amp;amp; root->right == NULL) {
        balance_factor = (root->left)->height;
    } else {
        balance_factor = ((root->left)->height) - ((root->right)->height);
        balance_factor = (balance_factor >= 0) ? (balance_factor) :(balance_factor * (-1));
    }
    return balance_factor;
}

struct TreeNodeC *heightImbalancingNode(struct TreeNodeC *root, bool *isFound) {
    struct TreeNodeC *TempB = NULL;
    if (root != NULL) {
        TempB = heightImbalancingNode(root->right, isFound);
        if ((*isFound) == false) {
            int bal_f = check_balance_factor(root);
            if (bal_f > 1) {
                *isFound = true;
                TempB = root;
                return TempB;
            }
        }
    }
    return TempB;
}

struct TreeNodeC *LLRotation(struct TreeNodeC *root, int val) {
    int val_temp = root->val;
    struct TreeNodeC *TempZ = (struct TreeNodeC *)malloc(sizeof(struct TreeNodeC));
    TempZ->val = root->val;
    TempZ->left = root->left;
    TempZ->right = root->right;
    TempZ->height = root->height;
    struct TreeNodeC *Temp = root->right;
    struct TreeNodeC *TempA = Temp->left;
    Temp->left = TempZ;
    (Temp->left)->right = TempA;
    if (val_temp == val) {
        avl = Temp;
    } else {
        *root = *Temp;
    }
    return Temp;
}

int maximum(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}

int height(struct TreeNodeC *root) {
    if (root == NULL) {
        return 0;
    }
    return 1   maximum(height(root->left), height(root->right));
}

int updateHeight(struct TreeNodeC **root) {
    if (*root == NULL) {
        return 0;
    }
    (*root)->height = height((*root));
    updateHeight(amp;((*root)->left));
    updateHeight(amp;((*root)->right));
    return 0;
}

struct TreeNodeC *createNode(int val) {
    struct TreeNodeC *newNode = (struct TreeNodeC *)malloc(sizeof(struct TreeNode));
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->val = val;
    return newNode;
}

struct TreeNodeC *insertion(int val, struct TreeNodeC *root) {
    struct TreeNodeC *Temp = root;
    if (Temp == NULL) {
        struct TreeNodeC *newNode = createNode(val);
        return newNode;
    }
    while (1) {
        if (val < Temp->val) {
            if (Temp->left == NULL) {
                struct TreeNodeC *newNode = createNode(val);
                Temp->left = newNode;
                return root;
            }
            Temp = Temp->left;
        } else {
            if (Temp->right == NULL) {
                struct TreeNodeC *newNode = createNode(val);
                Temp->right = newNode;
                return root;
            }
            Temp = Temp->right;
        }
    }
}

struct TreeNodeC *avlTreeInsertion(int val) {
    bool isFound = false;
    avl = insertion(val, avl);
    updateHeight(amp;avl);
    struct TreeNodeC *ll = heightImbalancingNode(avl, amp;isFound);
    if (isFound) {
        struct TreeNodeC *rotated = LLRotation(ll, avl->val);
        return avl;
    }
    return avl;
}

void inOrderTraversal(struct TreeNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        avlTreeInsertion(root->val);
        inOrderTraversal(root->right);
    }
}
struct TreeNodeC *balanceBST(struct TreeNode *root) {
    inOrderTraversal(root);
    return avl;
}

Я написал этот код, чтобы сбалансировать высоту двоичного дерева поиска. Это решение работает нормально. В коде leet я получаю превышение лимита времени для больших входных данных. Может ли кто-нибудь помочь мне, где я могу сделать это лучше, чтобы избежать ошибки TLE. Пожалуйста, не публикуйте совершенно новое решение для решения этой проблемы. Я хочу, чтобы проблема была решена в том подходе, который я выбрал, но с большей сложностью во времени

Комментарии:

1. Похоже, вы пропустили несколько глав о функциях в своей книге для начинающих. C не имеет вложенных функций. И почему вы определяете структуру в функции? Если это единственное определение, то нет смысла возвращать указатели на него из balanceBST функции. В противном случае, зачем его переопределять?

2. Отредактировал код заново. Теперь это должно иметь для вас смысл

3. Прежде чем реализовывать инвариантные операторы, такие как вращения, лучше сначала освоить язык программирования.

4. Вы выяснили, какова временная сложность существующего кода? Знаете ли вы, что это должно быть вместо этого?

Ответ №1:

 
 
struct TreeNodeC* balanceBST(struct TreeNode* root){    
    struct TreeNodeC
{
     int val;
     int height;
     struct TreeNodeC *left;
     struct TreeNodeC *right;
 };
    struct TreeNodeC* avl=NULL;
    int check_balance_factor(struct TreeNodeC * root)
{
    int balance_factor = 0;
    if(root->left==NULL amp;amp; root->right==NULL)
    {
        balance_factor = 0;
    }
    else if(root->left==NULL amp;amp; root->right!=NULL)
    {
        balance_factor =  (root->right)->height;
    }
    else if(root->left!=NULL amp;amp; root->right==NULL)
    {
        balance_factor = (root->left)->height;
    }
    else
    {
        balance_factor =((root->left)->height) - ((root->right)->height);
        balance_factor=(balance_factor>=0)?(balance_factor):(balance_factor*(-1));
    }
    return balance_factor;
}   
struct TreeNodeC* heightImbalancingNode(struct TreeNodeC* root,bool* isFound)
{
          struct TreeNodeC* Temp=NULL; 
        if(root!=NULL)
        {    
            Temp= heightImbalancingNode(root->right,isFound);
            if((*isFound)==false)
            {
            int bal_f=check_balance_factor(root); 
                if(bal_f>1)
                {
                *isFound=true;
                Temp=root;
                return Temp;
                }
            }
        }
        return Temp;      
}
    void LLRotation(struct TreeNodeC* root,int val){
        int val_temp=root->val;
        struct TreeNodeC* TempZ=(struct TreeNodeC* )malloc(sizeof(struct TreeNodeC));
        TempZ->val=root->val;
        TempZ->left=root->left;
        TempZ->right=root->right;
        TempZ->height=root->height;
        struct TreeNodeC* Temp=root->right;
        struct TreeNodeC* TempA=Temp->left;
        Temp->left=TempZ;
        (Temp->left)->right=TempA; 
        if(val_temp==val){
           avl=Temp; 
        }
        else{
            *root=*Temp;
        }    
}
    int maximum(int a,int b)
    {
        if(a>b){
            return a;
        }
        return b;
    }
    int updateHeight(struct TreeNodeC* root)
    {
        if(root==NULL)
        {
            return 0;
        }
        root->height= 1 maximum(updateHeight(root->left),updateHeight(root->right));
        return root->height;
       
    }
    struct TreeNodeC* createNode(int val)
    {
        struct TreeNodeC* newNode=(struct TreeNodeC*) malloc(sizeof(struct TreeNode));
        newNode->left=NULL;
        newNode->right=NULL;
        newNode->val=val;
        return newNode;
    }
   
     struct TreeNodeC* insertion(int val,struct TreeNodeC* root)
     {
       struct TreeNodeC* Temp=root; 
        if(Temp==NULL){
            struct TreeNodeC* newNode=createNode(val);
            return newNode;    
    }
       while(1)
       {
           if(val<Temp->val)
           { 
               if(Temp->left==NULL)
               {
                   struct TreeNodeC* newNode=createNode(val);
                   Temp->left=newNode;
                   return root;
               }
               Temp=Temp->left;
           }
           else{
              
               if(Temp->right==NULL){
                   struct TreeNodeC* newNode=createNode(val);
                   Temp->right=newNode;
                   return root;
               }
                Temp=Temp->right;
           }
       }
    }
   void avlTreeInsertion(int val)
   {
       bool isFound=false;
       avl= insertion(val,avl);
        updateHeight(avl);
       struct TreeNodeC* ll= heightImbalancingNode(avl,amp;isFound);
       if(isFound){
        LLRotation(ll,avl->val);
       }
   }
  void inOrderTraversal(struct TreeNode* root){
      if(root!=NULL){
      inOrderTraversal(root->left);  
      avlTreeInsertion(root->val);
      inOrderTraversal(root->right);
      }   
  }    
   inOrderTraversal(root);
    return avl;      
}

Внес некоторые небольшие изменения в программу. Сейчас это работает

Метки: