问题

我这里有一个AVL树的代码：

#include <iostream>
#include <cstdlib>
using namespace std;

typedef struct avl {
    avl *left;
    avl* right;
    avl* parent;
    int data;
} avl;

class AVL{
    avl* root;
    
public:
    void insert(int d);
    void inorder(avl*);
    void preorder();
    void rr_rotation(avl*);
    void ll_rotation(avl*, int);
    void rl_rotation(avl*);
    void lr_rotation(avl*);
    int height(avl *t);
    int getbalance(avl *parent);
    void check_avl(avl*);
    avl* getroot();
    AVL(){
        root=NULL;
    }
};

avl* AVL::getroot(){
    return root;
}

int AVL::height(avl *p){
    int l_height=0, r_height=0;
    int h=0;
    if(p!=nullptr){
        l_height=height(p->left);
        r_height=height(p->right);
        h= l_height>r_height ? l_height : r_height;
    }
    return ++h;
}

int AVL::getbalance(avl *p){
    int l_height=0, r_height=0;
    if(p!=nullptr){
        l_height=height(p->left);
        r_height=height(p->right);
    }
    int b= l_height-r_height;
    return b;
}

void AVL:: rr_rotation(avl *tree){
    cout<<"RR rotation"<<endl;
    avl* t=tree->left;
    t->right=tree;
    if(root==tree)
        root=t;
    else{
        tree=t;
    }
}

void AVL:: ll_rotation(avl *tree, int l=0){
    cout<<"LL rotation"<<endl;
    avl* t=tree->right;
    t->left=tree;
    if(root==tree)
        root=t;
    else{
        tree=t;
    }
}

void AVL:: lr_rotation(avl *tree){
    cout<<"LR rotation"<<endl;
    ll_rotation(tree->left,1);
    rr_rotation(tree);
}

void AVL:: rl_rotation(avl *tree){
    cout<<"RL rotation"<<endl;
    rr_rotation(tree->right);
    ll_rotation(tree);
}

void AVL::insert(int d){
    cout<<"Inserting "<<d<<endl;
    int c=0;
    avl *t = (avl*)malloc(sizeof(avl));
    t->data=d;
    t->parent=t->left=t->right=NULL;
    if(root==NULL){
        root=t;
    }
    else{
        avl* tree;
        avl* sample;
        tree=root;
        while(tree!=NULL){
            if(d<tree->data){
                sample=tree;
                tree=tree->left;
                c=1;
            }
            else{
                sample=tree;
                tree=tree->right;
                c=2;
            }
        }
        switch(c){
            case 1:
                sample->left=t;
                (sample->left)->parent=sample;
                break;
            case 2:
                sample->right=t;
                t->parent=sample;
        }
    }
    check_avl(root);
}

void AVL::check_avl(avl * t){
    if(t!=NULL){
        int balance=getbalance(t);
        if(balance>1){
            avl* child=t->left;
            if((child!=NULL) && (child->left!=NULL))
                rr_rotation(t);
            else if((child!=NULL) && (child->right!=NULL))
                lr_rotation(t);
        }
        else if(balance<-1){
            avl* child=t->right;
            if((child!=NULL) && (child->left!=NULL))
                rl_rotation(t);
            else if((child!=NULL) && (child->right!=NULL))
                ll_rotation(t);
        }
        check_avl(t->left);
        check_avl(t->right);
    }
}

void AVL::inorder(avl* t){
    if(t!=NULL){
        inorder(t->left);
        cout<<t->data<<" ";
        inorder(t->right);
    }
}

int main()
{
    AVL a;
    a.insert(10);
    a.insert(6);
    a.insert(3);
    a.insert(20);
    a.insert(15);
    a.insert(8);
    a.insert(5);
    a.insert(9);
    a.inorder(a.getroot());
}

我尝试插入3时，出现了分段错误。请帮我找出问题。

英文:

I have a code for AVL tree here:

#include&lt;iostream&gt;
#include&lt;cstdlib&gt;
using namespace std;
typedef struct avl {
avl *left;
avl* right;
avl* parent;
int data;
} avl;
class AVL{
avl* root;
public:
void insert(int d);
void inorder(avl*);
void preorder();
void rr_rotation(avl*);
void ll_rotation(avl*, int);
void rl_rotation(avl*);
void lr_rotation(avl*);
int height(avl *t);
int getbalance(avl *parent);
void check_avl(avl*);
avl* getroot();
AVL(){
root=NULL;
}
};
avl* AVL::getroot(){
return root;
}
int AVL::height(avl *p){
int l_height=0, r_height=0;
int h=0;
if(p!=nullptr){
l_height=height(p-&gt;left);
r_height=height(p-&gt;right);
h= l_height&gt;r_height ? l_height : r_height;
}
return ++h;
}
int AVL::getbalance(avl *p){
int l_height=0, r_height=0;
if(p!=nullptr){
l_height=height(p-&gt;left);
r_height=height(p-&gt;right);
}
int b= l_height-r_height;
return b;
}
void AVL:: rr_rotation(avl *tree){
cout&lt;&lt;&quot;RR rotation&quot;&lt;&lt;endl;
avl* t=tree-&gt;left;
t-&gt;right=tree;
if(root==tree)
root=t;
else{
tree=t;
}
}
void AVL:: ll_rotation(avl *tree, int l=0){
cout&lt;&lt;&quot;LL rotation&quot;&lt;&lt;endl;
avl* t=tree-&gt;right;
t-&gt;left=tree;
if(root==tree)
root=t;
else{
tree=t;
}
}
void AVL:: lr_rotation(avl *tree){
cout&lt;&lt;&quot;LR rotation&quot;&lt;&lt;endl;
ll_rotation(tree-&gt;left,1);
rr_rotation(tree);
}
void AVL:: rl_rotation(avl *tree){
cout&lt;&lt;&quot;RL rotation&quot;&lt;&lt;endl;
rr_rotation(tree-&gt;right);
ll_rotation(tree);
}
void AVL::insert(int d){
cout&lt;&lt;&quot;Inserting &quot;&lt;&lt;d&lt;&lt;endl;
int c=0;
avl *t = (avl*)malloc(sizeof(avl));
t-&gt;data=d;
//cout&lt;&lt;t-&gt;data;
t-&gt;parent=t-&gt;left=t-&gt;right=NULL;
if(root==NULL){
root=t;
}
else{
avl* tree;
avl* sample;
tree=root;
while(tree!=NULL){
if(d&lt;tree-&gt;data){
sample=tree;
tree=tree-&gt;left;
c=1;
}
else{
sample=tree;
tree=tree-&gt;right;
c=2;
}
}
switch(c){
case 1:
sample-&gt;left=t;
(sample-&gt;left)-&gt;parent=sample;
break;
case 2:
sample-&gt;right=t;
t-&gt;parent=sample;
}
}
check_avl(root);
}
void AVL::check_avl(avl * t){
if(t!=NULL){
int balance=getbalance(t);
if(balance&gt;1){
avl* child=t-&gt;left;
if((child!=NULL) &amp;&amp; (child-&gt;left!=NULL))
rr_rotation(t);
else if((child!=NULL) &amp;&amp; (child-&gt;right!=NULL))
lr_rotation(t);
}
else if(balance&lt;-1){
avl* child=t-&gt;right;
if((child!=NULL) &amp;&amp; (child-&gt;left!=NULL))
rl_rotation(t);
else if((child!=NULL) &amp;&amp; (child-&gt;right!=NULL))
ll_rotation(t);
}
check_avl(t-&gt;left);
check_avl(t-&gt;right);
}
}
void AVL::inorder(avl* t){
if(t!=NULL){
inorder(t-&gt;left);
cout&lt;&lt;t-&gt;data&lt;&lt;&quot; &quot;;
inorder(t-&gt;right);
}
}
int main()
{
AVL a;
a.insert(10);
a.insert(6);
a.insert(3);
a.insert(20);
a.insert(15);
a.insert(8);
a.insert(5);
a.insert(9);
a.inorder(a.getroot());
}

When I'm trying to insert 3, I'm getting a segmentation fault.

Help to figure out my issue

答案1

得分: 1

你在进行旋转或插入节点时没有正确更新父节点指针。在旋转函数（rr_rotation、ll_rotation、lr_rotation 和 rl_rotation）以及插入函数中，请正确更新父节点指针。

经过你所做的更改后的代码如下：

#include <iostream>
#include <cstdlib>
using namespace std;

typedef struct avl {
    avl* left;
    avl* right;
    avl* parent;
    int data;
} avl;

class AVL {
    avl* root;

public:
    void insert(int d);
    void inorder(avl*);
    void preorder();
    void rr_rotation(avl*);
    void ll_rotation(avl*); // changed from void ll_rotation(avl*, int);
    void rl_rotation(avl*);
    void lr_rotation(avl*);
    int height(avl* t);
    int getbalance(avl* parent);
    void check_avl(avl*);
    avl* getroot();
    AVL() {
        root = NULL;
    }
};

avl* AVL::getroot() {
    return root;
}

int AVL::height(avl* p) {
    int l_height = 0, r_height = 0;
    int h = 0;
    if (p != nullptr) {
        l_height = height(p->left);
        r_height = height(p->right);
        h = l_height > r_height ? l_height : r_height;
    }
    return ++h;
}

int AVL::getbalance(avl* p) {
    int l_height = 0, r_height = 0;
    if (p != nullptr) {
        l_height = height(p->left);
        r_height = height(p->right);
    }
    int b = l_height - r_height;
    return b;
}

/* 当我们将左子树 t 移动到替换原始节点树时，
   我们需要更新新树的左子树的父指针和树本身的父指针。 */
void AVL::rr_rotation(avl* tree) {
    cout << "RR rotation" << endl;
    avl* t = tree->left;
    tree->left = t->right;
    if (t->right != NULL) {
        t->right->parent = tree;  // 修正：更新右子树的父指针
    }
    t->right = tree;
    t->parent = tree->parent;
    tree->parent = t;
    if (root == tree)
        root = t;
    else {
        if (t->parent->left == tree)
            t->parent->left = t;
        else
            t->parent->right = t;
    }
}

/* 当我们将右子树 t 移动到替换原始节点树时，
   我们需要更新新树的右子树的父指针和树本身的父指针。 */
void AVL::ll_rotation(avl* tree) {
    cout << "LL rotation" << endl;
    avl* t = tree->right;
    tree->right = t->left;
    if (t->left != NULL) {
        tree->left->parent = tree;  // 修正：更新左子树的父指针
    }
    t->left = tree;
    t->parent = tree->parent;
    tree->parent = t;
    if (root == tree)
        root = t;
    else {
        if (t->parent->left == tree)
            t->parent->left = t;
        else
            t->parent->right = t;
    }
}

void AVL::lr_rotation(avl* tree) {
    cout << "LR rotation" << endl;
    ll_rotation(tree->left);
    rr_rotation(tree);
}

void AVL::rl_rotation(avl* tree) {
    cout << "RL rotation" << endl;
    rr_rotation(tree->right);
    ll_rotation(tree);
}

void AVL::insert(int d) {
    cout << "Inserting " << d << endl;
    int c = 0;
    avl* t = new avl; // 改为 new (c++ 风格)
    t->data = d;
    t->parent = t->left = t->right = NULL;

    if (root == NULL) {
        root = t;
    }
    else {
        avl* tree;
        avl* sample;
        tree = root;
        while (tree != NULL) {
            sample = tree; // 它曾经在 if (d < tree->data) 中
            if (d < tree->data) {
                tree = tree->left;
                c = 1;
            }
            else {
                tree = tree->right;
                c = 2;
            }
        }
        switch (c) {
        case 1:
            sample->left = t; // 不需要第二行 (sample->left)->parent=sample;
            break;
        case 2:
            sample->right = t;
            break;
        }
        t->parent = sample;
    }
    check_avl(root);
}

void AVL::check_avl(avl* t) {
    if (t != NULL) {
        int balance = getbalance(t);
        if (balance > 1) {
            avl* child = t->left;
            if (child != NULL && getbalance(child) >= 0) // 替换为 getbalance
                rr_rotation(t);
            else if (child != NULL && getbalance(child) < 0) // 替换为 getbalance
                lr_rotation(t);
        }
        else if (balance < -1) {
            avl* child = t->right;
            if (child != NULL && getbalance(child) <= 0) // 替换为 getbalance
                ll_rotation(t);
            else if (child != NULL && getbalance(child) > 0) // 替换为 getbalance
                rl_rotation(t);
        }
        check_avl(t->left);
        check_avl(t->right);
    }
}

void AVL::inorder(avl* t) {
    if (t != NULL) {
        inorder(t->left);
        cout << t->data << " ";
        inorder(t->right);
    }
}

int main() {
    AVL a;
    a.insert(10);
    a.insert(6);
    a.insert(3);
    a.insert(20);
    a.insert(15);
    a.insert(8);
    a.insert(5);
    a.insert(9);
    a.inorder(a.getroot());
    return 0;
}

输出：

Inserting 10
Inserting 6
Inserting 3
RR rotation
Inserting 20
Inserting 15
LL rotation
Inserting 8
Inserting 5
Inserting 9
3 5 6 8 9 10 15 20

英文:

You are not properly updating the parent pointer when performing rotations or inserting nodes.

Update the parent pointers correctly in your rotation functions (rr_rotation, ll_rotation, lr_rotation, and rl_rotation) as well as when inserting nodes in the insert function.

Here is the code after the changes that I made:

#include&lt;iostream&gt;
#include&lt;cstdlib&gt;
using namespace std;
typedef struct avl {
avl* left;
avl* right;
avl* parent;
int data;
} avl;
class AVL {
avl* root;
public:
void insert(int d);
void inorder(avl*);
void preorder();
void rr_rotation(avl*);
void ll_rotation(avl*); // changed from void ll_rotation(avl*, int);
void rl_rotation(avl*);
void lr_rotation(avl*);
int height(avl* t);
int getbalance(avl* parent);
void check_avl(avl*);
avl* getroot();
AVL() {
root = NULL;
}
};
avl* AVL::getroot() {
return root;
}
int AVL::height(avl* p) {
int l_height = 0, r_height = 0;
int h = 0;
if (p != nullptr) {
l_height = height(p-&gt;left);
r_height = height(p-&gt;right);
h = l_height &gt; r_height ? l_height : r_height;
}
return ++h;
}
int AVL::getbalance(avl* p) {
int l_height = 0, r_height = 0;
if (p != nullptr) {
l_height = height(p-&gt;left);
r_height = height(p-&gt;right);
}
int b = l_height - r_height;
return b;
}
/* when we move the left child t up to replace the original node tree, 
we need to update the parent pointers of the left child of the
new tree and the parent pointer of tree itself. */
void AVL::rr_rotation(avl* tree) {
cout &lt;&lt; &quot;RR rotation&quot; &lt;&lt; endl;
avl* t = tree-&gt;left;
tree-&gt;left = t-&gt;right;
if (t-&gt;right != NULL) {
t-&gt;right-&gt;parent = tree;  // Fix: Update parent pointer of the right child
}
t-&gt;right = tree;
t-&gt;parent = tree-&gt;parent;
tree-&gt;parent = t;
if (root == tree)
root = t;
else {
if (t-&gt;parent-&gt;left == tree)
t-&gt;parent-&gt;left = t;
else
t-&gt;parent-&gt;right = t;
}
}
/* when we move the right child t up to replace the original node tree, 
we need to update the parent pointers of the right child of the
new tree and the parent pointer of tree itself. */
void AVL::ll_rotation(avl* tree) {
cout &lt;&lt; &quot;LL rotation&quot; &lt;&lt; endl;
avl* t = tree-&gt;right;
tree-&gt;right = t-&gt;left;
if (t-&gt;left != NULL) {
tree-&gt;left-&gt;parent = tree;  // Fix: Update parent pointer of the left child
}
t-&gt;left = tree;
t-&gt;parent = tree-&gt;parent;
tree-&gt;parent = t;
if (root == tree)
root = t;
else {
if (t-&gt;parent-&gt;left == tree)
t-&gt;parent-&gt;left = t;
else
t-&gt;parent-&gt;right = t;
}
}
void AVL::lr_rotation(avl* tree) {
cout &lt;&lt; &quot;LR rotation&quot; &lt;&lt; endl;
ll_rotation(tree-&gt;left);
rr_rotation(tree);
}
void AVL::rl_rotation(avl* tree) {
cout &lt;&lt; &quot;RL rotation&quot; &lt;&lt; endl;
rr_rotation(tree-&gt;right);
ll_rotation(tree);
}
void AVL::insert(int d) {
cout &lt;&lt; &quot;Inserting &quot; &lt;&lt; d &lt;&lt; endl;
int c = 0;
avl* t = new avl; // changed to new (c++ style)
t-&gt;data = d;
t-&gt;parent = t-&gt;left = t-&gt;right = NULL;
if (root == NULL) {
root = t;
}
else {
avl* tree;
avl* sample;
tree = root;
while (tree != NULL) {
sample = tree; // it was in if (d &lt; tree-&gt;data)
if (d &lt; tree-&gt;data) {
tree = tree-&gt;left;
c = 1;
}
else {
tree = tree-&gt;right;
c = 2;
}
}
switch (c) {
case 1:
sample-&gt;left = t; // no need second line (sample-&gt;left)-&gt;parent=sample;
break;
case 2:
sample-&gt;right = t;
break;
}
t-&gt;parent = sample;
}
check_avl(root);
}
void AVL::check_avl(avl* t) {
if (t != NULL) {
int balance = getbalance(t);
if (balance &gt; 1) {
avl* child = t-&gt;left;
if (child != NULL &amp;&amp; getbalance(child) &gt;= 0) // replaced with getbalance
rr_rotation(t);
else if (child != NULL &amp;&amp; getbalance(child) &lt; 0) // replaced with getbalance
lr_rotation(t);
}
else if (balance &lt; -1) {
avl* child = t-&gt;right;
if (child != NULL &amp;&amp; getbalance(child) &lt;= 0) // replaced with getbalance
ll_rotation(t);
else if (child != NULL &amp;&amp; getbalance(child) &gt; 0) // replaced with getbalance
rl_rotation(t);
}
check_avl(t-&gt;left);
check_avl(t-&gt;right);
}
}
void AVL::inorder(avl* t) {
if (t != NULL) {
inorder(t-&gt;left);
cout &lt;&lt; t-&gt;data &lt;&lt; &quot; &quot;;
inorder(t-&gt;right);
}
}
int main() {
AVL a;
a.insert(10);
a.insert(6);
a.insert(3);
a.insert(20);
a.insert(15);
a.insert(8);
a.insert(5);
a.insert(9);
a.inorder(a.getroot());
return 0;
}

Output:

Inserting 10
Inserting 6
Inserting 3
RR rotation
Inserting 20
Inserting 15
LL rotation
Inserting 8
Inserting 5
Inserting 9
3 5 6 8 9 10 15 20

通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。

在AVL树的代码中遇到了分段错误。

问题

答案1

Multiple definition error when importing c++23 standard library module in multiple files.

为什么我在下面的归并排序程序中得到了错误的输出（0 4 0 0 0 0 0 0）？

“co_spawn”的成本和替代方案

在Visual Studio中编译此代码时没有错误。

What's the correct way to type hint an empty list as a literal in python?

如何在Highcharts Gantt中更改本地化的星期名称

如何在同一个流中使用多个过滤器和映射函数？

如何使用Map/Set来将代码优化到O(n)？

.NET MAUI Android在GitHub Actions上构建失败，错误代码为1。

如何在Playwright视觉比较中屏蔽多个定位器？

在C++中，可以使用可变模板参数来检索类型的内部类型。

selenium.common.exceptions.StaleElementReferenceException: Message: stale element reference: stale element not found

Creating and opening a URL to log in to Website via Basic Auth with Robot Framework/Selenium (Python)

AG Grid 在上下文菜单中以大文本形式打开

发表评论