Getting segmentation fault in a code of AVL tree

Question

I have a code for AVL tree here:

#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;
    //cout<<t->data;
    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());
}

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

Help to figure out my issue

You do know C++ does not initialize variables do you? Set all your pointers to nullptr before you continue. — Pepijn Kramer, May 10 '23 at 18:08
notes, don't use `using namespace std;` And no need to do typedef with a struct that's "C" not C++. Learn C++ from a [recent C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or have a go at https://www.learncpp.com/ (that's pretty decent, and pretty up-to-date). For C++ reference material use : [cppreference](https://en.cppreference.com/w/). And after you learned the C++ basics from those sources, look at the [C++ coreguidelines](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines) regularely to keep up-to-date with the latest guidelines. — Pepijn Kramer, May 10 '23 at 18:09
I would have KILLED to have had tools like I have today back when I was learning to program: https://godbolt.org/z/nzqEfWcf3 Thou hast overflowed thine stack. A run through the program [with a debugger](https://en.wikipedia.org/wiki/Debugger) should show you exactly how within a few minutes. — user4581301, May 10 '23 at 18:14
If you have not already been exposed to debuggers, here's [the basic how-to for the one built into Visual Studio](https://learn.microsoft.com/en-us/visualstudio/debugger/debugger-feature-tour?view=vs-2022) all of the modern IDEs have something very like it built in. I did have this sort of tool, TD, back when I was a kid, and learning to use it early in my schooling was likely the only reason I got to run RPG sessions on the weekends. That may not be your cup of tea, but whatever. It's your free time, so use it as you will. — user4581301, May 10 '23 at 18:18
@user4581301 - on the bright side, in between walking to school 10 miles through the snow uphill both ways, we also learned how to single-step through code in our mind or on paper without even needing a debugger :) . — Dave S, May 10 '23 at 18:20
@DaveS That's how I started., but the debugger was better. It shows what is, not whatever bad assumptions I have about the code. That's the real problem. No one goes out and writes faulty code without a good reason. They made a bad assumption or two about what a line of code did, and those assumptions generally follow through to in-mind debugging sessions. The debugger doesn't have a mind and doesn't make assumptions. Ego-crushing sometimes, but the bug lurks in the difference between what is and what you expected, so seeing what is is an awesome advantage. — user4581301, May 10 '23 at 18:25
@user4581301 - oh definitely. I learned that way because I had to. Single-stepping, watches, breakpoints, and being able to go up and down the stack while single-stepping or at a breakpoint are all much better than by hand. — Dave S, May 10 '23 at 18:45
`typedef struct avl {} avl;` creates a potential issue: `avl` the typedef hides `avl` the class (struct). — Swift - Friday Pie, May 10 '23 at 23:30

gera verbun · Answer 1 · 2023-05-10T18:32:46.050

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<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;
}

/* 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 << "RR rotation" << endl;
    avl* t = tree->left;
    tree->left = t->right;
    if (t->right != NULL) {
        t->right->parent = tree;  // Fix: Update parent pointer of the right child
    }
    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;
    }
}

/* 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 << "LL rotation" << endl;
    avl* t = tree->right;
    tree->right = t->left;
    if (t->left != NULL) {
        tree->left->parent = tree;  // Fix: Update parent pointer of the left child
    }
    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; // changed to new (c++ style)
    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; // it was in 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; // no need second line (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) // replaced with getbalance
                rr_rotation(t);
            else if (child != NULL && getbalance(child) < 0) // replaced with getbalance
                lr_rotation(t);
        }
        else if (balance < -1) {
            avl* child = t->right;
            if (child != NULL && getbalance(child) <= 0) // replaced with getbalance
                ll_rotation(t);
            else if (child != NULL && getbalance(child) > 0) // replaced with 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;
}

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

Getting segmentation fault in a code of AVL tree

1 Answers1