C : Cannot access memory error, when finding recursively an AVL tree height

Question

So i tried to implement an AVL tree in C. I use recursion for the insertions, and while i get some good results for small number of items, i get a "cannot access memory at..." at big input as shown below.

Before i post the code. The problem seems to be in height() calculation. Used gdb and stepped through the rotations to see if anything goes wrong, but it seemed to behave well. (no uninitialized pointers, no trash remaining after changes). The avl_insert() code is kind of messy but i spent 2 days double checking it, i'm pretty sure it's correct.

So, here goes the code :

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>


typedef struct _avl{
    long int value;
    int index;
    struct _avl *parent;
    struct _avl *left;
    struct _avl *right;
} avl_node;

//Allocating memory for a new node
avl_node *avl_new_node(long int val, int index)
{
    avl_node *t;
    t = (avl_node *)malloc(sizeof(avl_node));
    t->index = index;
    t->parent = NULL;
    t->left = NULL;
    t->right = NULL;
    t->value = val;
    return t;
}

//Calculate subtree hight recursively
int height(avl_node *t)
{
    if(t == NULL)   return 0;
    int leftH = height(t->left);
    int rightH = height(t->right);
    if(leftH > rightH)  return leftH + 1;
    else    return rightH + 1;
}


//Pain in the butt, but works
avl_node *avl_insert(avl_node *t, long int val, int index)
{
    avl_node *ans;
    if(t == NULL)   t = avl_new_node(val, index);
    else if(val < t->value){
        t->left = avl_insert(t->left, val, index);
        t->left->parent = t;
        if((height(t->left) - height(t->right)) == 2){
            //Left Rotation
            if(val < t->left->value){
                avl_node *tmp;
                if(t->parent != NULL){
                    tmp = (t == t->parent->right)?(t->parent->right):(t->parent->left);
                    tmp = t->left;
                }
                t->left->parent = t->parent;
                t->parent = t->left;
                t->left = t->parent->right;
                t->parent->right = t;
                if(t->left != NULL) t->left->parent = t;
                t = t->parent;
            }
            //Left-Right Rotation
            else if(val > t->left->value){
                avl_node *l;
                avl_node *lr;
                l = t->left;
                lr = t->left->right;
                //Additional startup rotation for the others to work correct
                if(lr->left != NULL){
                    lr->left->right = lr;
                    lr->parent = lr->left;
                    l->right = lr->left;
                    l->right->parent = l;
                }
                l->parent = l->right;
                t->left = l->parent;
                t->left->parent = l;
                t->left->left = l;
                l->right = NULL;

                avl_node *tmp;
                if(t->parent != NULL){
                    tmp = (t == t->parent->right)?(t->parent->right):(t->parent->left);
                    tmp = t->left;
                }
                t->left->parent = t->parent;
                t->parent = t->left;
                t->left = t->parent->right;
                t->parent->right = t;
                if(t->left != NULL) t->left->parent = t;
                t = t->parent;
            }
        }
    }
    else if(val > t->value){
        t->right = avl_insert(t->right, val, index);
        t->right->parent = t;
        if((height(t->right) - height(t->left)) == 2){
            //Right Rotation
            if(val > t->right->value){
                avl_node *tmp;
                if(t->parent != NULL){
                    tmp = (t == t->parent->right)?(t->parent->right):(t->parent->left);
                    tmp = t->right;
                }
                t->right->parent = t->parent;
                t->parent = t->right;
                t->right = t->parent->left;
                t->parent->left = t;
                if(t->right != NULL)    t->right->parent = t;
                t=t->parent;
            }
            //Right-left Rotation
            else if(val < t->right->value){
                avl_node *r;
                avl_node *rl;
                r = t->right;
                rl = t->right->left;
                //Additional startup rotation for the others to work correct
                if(rl->right != NULL){
                    rl->right->left = rl;
                    rl->parent = rl->right;
                    r->left = rl->right;
                    rl->right = NULL;
                    r->left->parent = r;
                }
                r->parent = r->left;
                t->right = r->parent;
                t->right->parent = t;
                t->right->right = r;
                r->left = NULL;

                avl_node *tmp;
                if(t->parent != NULL){
                    tmp = (t == t->parent->right)?(t->parent->right):(t->parent->left);
                    tmp = t->right;
                }               t->right->parent = t->parent;
                t->parent = t->right;
                t->right = t->parent->left;
                t->parent->left = t;
                if(t->right != NULL)    t->right->parent = t;
                t = t->parent;
            }
        }
    }
    return t;
}    



int main(int argc, const char *argv[])
{
    int i;
    int v[100];// = {97, 10, 96, 109, 77, 70, 128, 64, 93, 45, 30, 65, 37, 46, 54, 30, 123, 112, 109, 49, 109};
    avl_node *avlRoot;
    avlRoot = avl_new_node(97, 0);
    srand( 180 );
    for(i = 1; i<100; i++){
        v[i] = rand()%130;
    }
    for(i=1; i < 100; i++){
        printf("I : %d and k : %d\n", i, v[i]);
        avlRoot = avl_insert(avlRoot, v[i], i);
    }
    return 0;
}

I compile it with :

gcc -o c.out my_avl.c -Wall -g

Νο worthy warnings...

Running this main i get from gdb :

Program received signal SIGSEGV, Segmentation fault.
0x000000000040066d in height (t=0x6020d0) at my_avl.c:33
33      int leftH = height(t->left);
(gdb) bt 10
#0  0x000000000040066d in height (t=0x6020d0) at my_avl.c:33
#1  0x0000000000400672 in height (t=0x602730) at my_avl.c:33
#2  0x0000000000400672 in height (t=0x602550) at my_avl.c:33
#3  0x0000000000400672 in height (t=0x602430) at my_avl.c:33
#4  0x0000000000400685 in height (t=0x602730) at my_avl.c:34
#5  0x0000000000400672 in height (t=0x602550) at my_avl.c:33
#6  0x0000000000400672 in height (t=0x602430) at my_avl.c:33
#7  0x0000000000400685 in height (t=0x602730) at my_avl.c:34
#8  0x0000000000400672 in height (t=0x602550) at my_avl.c:33
#9  0x0000000000400672 in height (t=0x602430) at my_avl.c:33
(More stack frames follow...)

Running the code in another main with about 210,000 long int items, i get the following error :

Program received signal SIGSEGV, Segmentation fault.
0x0000000000401607 in height (
t=<error reading variable: Cannot access memory at address 0x7fffff7fefe8>)
    at bookstore.h:338
338 {
(gdb) bt 10
#0  0x0000000000401607 in height (
    t=<error reading variable: Cannot access memory at address 0x7fffff7fefe8>)
    at bookstore.h:338
#1  0x0000000000401629 in height (t=0x1855f70) at bookstore.h:341
#2  0x0000000000401629 in height (t=0x1855fa0) at bookstore.h:341
#3  0x0000000000401629 in height (t=0x1856030) at bookstore.h:341
#4  0x0000000000401629 in height (t=0x1855b50) at bookstore.h:341
#5  0x0000000000401629 in height (t=0x1855e20) at bookstore.h:341
#6  0x000000000040163c in height (t=0x1856030) at bookstore.h:342
#7  0x0000000000401629 in height (t=0x1855b50) at bookstore.h:341
#8  0x0000000000401629 in height (t=0x1855e20) at bookstore.h:341
#9  0x000000000040163c in height (t=0x1856030) at bookstore.h:342
(More stack frames follow...)

Watching the arguments of height in backtrace they seem to be repeating. I thought maybe some "parents" or "childs" are not cleared correctly during the rotations, creating an infinite loop or something, but after hours of testing i was unable find such an error in the code. I'm really badly stuck here... Thanks in advance for any help.

Segmentation fault usually means that you are trying to access a memory out of your program scope — Brian, Jul 28 '13 at 20:55
...but in this case it means that you are running out of stack space, as OP has already understood. — jlahd, Jul 28 '13 at 20:58
So i should check for a an infinite loop that takes me out of stack space? If it is not a logical error, and it actually does need that much space, are there ways i can fix it? I'm kinda new to memory allocation. — Alek Sobczyk, Jul 28 '13 at 21:03
"an infinite loop or something" - rather infinite recursion: somewhere you forgot to write `leaf->left = NULL; leaf->right = NULL;`. — , Jul 28 '13 at 21:03
@AlekSobczyk Ah, and [don't cast the return value of `malloc()`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc/605858#605858). — , Jul 28 '13 at 21:04
@H2CO3: Indeed - and that location is in the "additional startup location" branches, where `lr->left` and `rl->right` are copied to `l->right` and `r->left`, but the original contents are not cleared. Add `lr->left = NULL;` and `rl->right = NULL;` to the correct places and it works. — jlahd, Jul 28 '13 at 21:16
"In such cases, it makes sense to look for an optimization in the base case for the recursive function." @jlahd there you go, you found it! — sgun, Jul 28 '13 at 21:32

score 0 · Answer 1 · answered Jul 28 '13 at 21:25

Your avl_insert function is a recursive one and your program is running out of stack memory. Using smaller sized variables will help you a little (using short instead of long int etc.) but you will encounter the same issue a little later again.

In such cases, it makes sense to look for an optimization in the base case for the recursive function.

C : Cannot access memory error, when finding recursively an AVL tree height

1 Answers1