code = 139 Ошибка [Ошибка сегментации] Вставка дерева AVL - PullRequest
Новая
       145

code = 139 Ошибка [Ошибка сегментации] Вставка дерева AVL

0 голосов
/ 07 августа 2020

У меня есть функция add_node, которая добавляет узлы в дерево, но когда я иду с перекосом, скажем правильно, это дает ошибку сегментации. 

template<class T>
class avl{
   private:
      Node<T>* root;
    public:
    //CONSTRUCTOR
       avl(){
           root=nullptr;
       }
//HEIGHT FUNCTION
    int get_height(){
       return get_height(this->root);   
    }
    int get_height(Node<T>* node){
        int l_height,r_height;
        if(node==nullptr){return -1;}
        else{
        l_height=get_height(node->m_left);
        r_height=get_height(node->m_right);

        if(l_height>=r_height){return l_height+1;}
        else{return r_height+1;}
        }
    }
    //BALANCE_FACTOR
    int balance_factor(Node<T>* node){
        return get_height(node->m_left)- get_height(node->m_right);
    }
    Node<T>* ll_rotate(Node<T>* &node){
        Node<T>* temp=nullptr;
        temp=node->m_right;
        node->m_right=temp->m_left;
        temp->m_left=node;
        return temp;
   }
 Node<T>* rr_rotate(Node<T>* &node){
        Node<T>* temp=nullptr;
        temp=node->m_left;
        node->m_left=temp->m_right;
        temp->m_right=node;
        return temp;
    }
    Node<T>* rl_rotate(Node<T>* &node){
        node->m_right=rr_rotate(node->m_right);
        return ll_rotate(node);
    }
        Node<T>* lr_rotate(Node<T>* &node){
        node->m_left=ll_rotate(node->m_left);
        return rr_rotate(node);
    }

//Rebalance Tree
    Node<T>* rebalance(Node<T>* &node){
        int bf= balance_factor(node);
        
        if(bf>1){
            if(balance_factor(node->m_left)>1){
               return rr_rotate(node);
            }else{
               return lr_rotate(node);
            }
        }else if(bf<-1){
            if(balance_factor(node->m_right)<-1){
              return  ll_rotate(node);
            }else{
               return rl_rotate(node);
            }
        }
        return node;
    }
   void add_node(T data){
     add_node(data,this->root);
           }
   Node<T>* add_node(T data,Node<T>* node){
            if(node==nullptr){
                Node<T>* new_node= new Node<T>(data);
                 return new_node;
            }
            if(data>node->m_data){
                node->m_right=add_node(data,node->m_right);
            } else if(data<node->m_data){
                node->m_left=add_node(data,node->m_left);
            }
        /*    int bf= balance_factor(node);
            //ll case
            if(bf>1 && data<node->m_left->m_data){
                return rr_rotate(node);
            }//rr case
            if(bf<-1 && data>node->m_right->m_data){
                return ll_rotate(node);
            }//lr case
            if(bf>1 && data>node->m_left->m_data){
                  return lr_rotate(node);
            }//rl case
             if(bf<-1 && data<node->m_right->m_data){
                  return rl_rotate(node);
            }*/
            return rebalance(node);
    }

node.h 

template<class T>
class Node{
  private:
  public:
     T m_data;
     Node<T>* m_left;
     Node<T>* m_right;
     
     Node(T data){
        m_data =data;
        m_left=nullptr;
        m_right=nullptr;
     }
};

main. cpp

#include<iostream>
#include"avl.h"

using namespace std;

int main(){
  avl<int> a1;
  a1.add_node(20);
  a1.add_node(25);
  a1.add_node(30);  //Error is happening at this point

}

Cra sh происходит, когда я добавляю 30. В этот момент у меня есть дерево 

20
 \
  25
   \
    30

add_node вызывает ребалансировку на 20 узле. Коэффициент баланса равен -2, а коэффициент баланса узла 25 равен -1, что означает, что он вызывает rr_rotate (node) на узле 20. Это немедленно вызывает ll_rotate (node-> m_right), который находится на 25 узле. Эта функция имеет эти две строки:

temp = node-> m_left; node-> m_left = temp-> m_right;

, поскольку узел - это 25 узлов, поэтому node-> m_left имеет значение null, поэтому temp равно нулю, поэтому temp-> m_right - это cra sh.

Как мне столкнуться с этой проблемой?

1 Ответ

0 голосов
/ 08 августа 2020

Проблема кроется в проверке узла на ребалансировку. В функции Rebalance Tree, когда я проверяю коэффициент баланса родителя, а затем проверяю левый или правый дочерний элемент родителя, используемое значение неверно. Он не должен быть -1 или 1, он должен быть 0. Так как не обязательно, чтобы дочерний узел узла, на котором мы выполняем вращение, имел коэффициент баланса больше 1 или меньше -1. Но он всегда будет больше 0, поэтому, если он больше 0 в случае левого тяжелого родителя, тогда мы должны выполнить rr_rotation [для левого-левого случая] и аналогично ll_rotation для правого тяжелого поддерева. Ниже приводится рабочая функция: 

Node<T>* rebalance(Node<T>* &node){
       int bf= balance_factor(node);
       if(bf>1){
           if(balance_factor(node->m_left)>0){
               return rr_rotate(node);
           }else{return lr_rotate(node);}
       }
       if(bf<-1){
           if(balance_factor(node->m_right)>0){
               return rl_rotate(node);
           }else{return ll_rotate(node);}
       }
       return node;
   }
...