#c #binary-tree #binary-search-tree #avl-tree
#c #двоичное дерево #двоичное дерево поиска #avl-tree
Вопрос:
У меня есть функция add_node, которая добавляет узлы в дерево, но когда я говорю неправильно, это приводит к ошибке сегментации.
template<class T&&t;
class avl{
private:
Node<T&&t;* root;
public:
//CONSTRUCTOR
avl(){
root=nullptr;
}
//HEIGHT FUNCTION
int &et_hei&ht(){
return &et_hei&ht(this-&&t;root);
}
int &et_hei&ht(Node<T&&t;* node){
int l_hei&ht,r_hei&ht;
if(node==nullptr){return -1;}
else{
l_hei&ht=&et_hei&ht(node-&&t;m_left);
r_hei&ht=&et_hei&ht(node-&&t;m_ri&ht);
if(l_hei&ht&&t;=r_hei&ht){return l_hei&ht 1;}
else{return r_hei&ht 1;}
}
}
//BALANCE_FACTOR
int balance_factor(Node<T&&t;* node){
return &et_hei&ht(node-&&t;m_left)- &et_hei&ht(node-&&t;m_ri&ht);
}
Node<T&&t;* ll_rotate(Node<T&&t;* amp;node){
Node<T&&t;* temp=nullptr;
temp=node-&&t;m_ri&ht;
node-&&t;m_ri&ht=temp-&&t;m_left;
temp-&&t;m_left=node;
return temp;
}
Node<T&&t;* rr_rotate(Node<T&&t;* amp;node){
Node<T&&t;* temp=nullptr;
temp=node-&&t;m_left;
node-&&t;m_left=temp-&&t;m_ri&ht;
temp-&&t;m_ri&ht=node;
return temp;
}
Node<T&&t;* rl_rotate(Node<T&&t;* amp;node){
node-&&t;m_ri&ht=rr_rotate(node-&&t;m_ri&ht);
return ll_rotate(node);
}
Node<T&&t;* lr_rotate(Node<T&&t;* amp;node){
node-&&t;m_left=ll_rotate(node-&&t;m_left);
return rr_rotate(node);
}
//Rebalance Tree
Node<T&&t;* rebalance(Node<T&&t;* amp;node){
int bf= balance_factor(node);
if(bf&&t;1){
if(balance_factor(node-&&t;m_left)&&t;1){
return rr_rotate(node);
}else{
return lr_rotate(node);
}
}else if(bf<-1){
if(balance_factor(node-&&t;m_ri&ht)<-1){
return ll_rotate(node);
}else{
return rl_rotate(node);
}
}
return node;
}
void add_node(T data){
add_node(data,this-&&t;root);
}
Node<T&&t;* add_node(T data,Node<T&&t;* node){
if(node==nullptr){
Node<T&&t;* new_node= new Node<T&&t;(data);
return new_node;
}
if(data&&t;node-&&t;m_data){
node-&&t;m_ri&ht=add_node(data,node-&&t;m_ri&ht);
} else if(data<node-&&t;m_data){
node-&&t;m_left=add_node(data,node-&&t;m_left);
}
/* int bf= balance_factor(node);
//ll case
if(bf&&t;1 amp;amp; data<node-&&t;m_left-&&t;m_data){
return rr_rotate(node);
}//rr case
if(bf<-1 amp;amp; data&&t;node-&&t;m_ri&ht-&&t;m_data){
return ll_rotate(node);
}//lr case
if(bf&&t;1 amp;amp; data&&t;node-&&t;m_left-&&t;m_data){
return lr_rotate(node);
}//rl case
if(bf<-1 amp;amp; data<node-&&t;m_ri&ht-&&t;m_data){
return rl_rotate(node);
}*/
return rebalance(node);
}
node.h
template<class T&&t;
class Node{
private:
public:
T m_data;
Node<T&&t;* m_left;
Node<T&&t;* m_ri&ht;
Node(T data){
m_data =data;
m_left=nullptr;
m_ri&ht=nullptr;
}
};
main.cpp
#include<iostream&&t;
#include"avl.h"
usin& namespace std;
int main(){
avl<int&&t; a1;
a1.add_node(20);
a1.add_node(25);
a1.add_node(30); //Error is happenin& at this point
}
Сбой происходит, когда я добавляю 30. На этом этапе у меня есть дерево
20
25
30
add_node вызывает перебалансировку на 20 узле. Коэффициент баланса равен -2, а коэффициент баланса узла 25 равен -1, что означает, что он вызывает rr_rotate (узел) на узле 20. Это немедленно вызывает ll_rotate(узел-&&t; m_ri&ht), который находится на 25 узле. Эта функция содержит эти две строки
temp=узел-&&t; m_left; узел-&&t; m_left=temp-&&t;m_ri&ht;
поскольку узел состоит из 25 узлов, поэтому значение node-&&t; m_left равно нулю, поэтому temp равно нулю, поэтому temp-&&t; m_ri&ht — сбой.
Как я могу столкнуться с этой проблемой?
Комментарии:
1. Пожалуйста, узнайте, как использовать отладчик для обнаружения сбоев и определения того, когда и где в вашем коде это происходит. Это также позволит вам проверить переменные и их значения в момент сбоя.
2. Я узнал об этом факте с помощью отладчика, но я в замешательстве, поскольку node-&&t; m_left== nullptr, так как мне назначить ему право временного узла!
3. Если бы вы могли прочитать вопрос, вы бы знали, что речь идет не о ошибке сегментации, а о том, как происходит эта ошибка! @Somepro&rammerdude
4. Затем используйте отладчик для пошагового выполнения кода, оператор за оператором.
5. это уже было сделано, вот как я узнал, в чем проблема, и я не знаю решения, поэтому я разместил его здесь!
Ответ №1:
Проблема заключается в проверке узла на перебалансировку. В функции дерева перебалансировки, когда я проверяю коэффициент баланса родительского элемента, а затем проверяю левый или правый дочерний элемент родительского элемента, используемое значение неверно. Это не должно быть -1 или 1, это должно быть 0. Поскольку необязательно, чтобы дочерний узел узла, на котором мы выполняем ротацию, должен иметь коэффициент баланса больше 1 или меньше -1. Но оно всегда будет больше 0. поэтому, если оно больше 0 в случае левого тяжелого родительского элемента, тогда мы должны выполнить rr_rotation[Для левого-левый регистр] и аналогично ll_rotation для правого тяжелого поддерева. Ниже приведена рабочая функция:
Node<T&&t;* rebalance(Node<T&&t;* amp;node){
int bf= balance_factor(node);
if(bf&&t;1){
if(balance_factor(node-&&t;m_left)&&t;0){
return rr_rotate(node);
}else{return lr_rotate(node);}
}
if(bf<-1){
if(balance_factor(node-&&t;m_ri&ht)&&t;0){
return rl_rotate(node);
}else{return ll_rotate(node);}
}
return node;
}