StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POC : Cannot access memory error, when finding recursively an AVL tree height
primarykey
Id
17912785
data
AcceptedAnswerId
0
AnswerCount
1
ClosedDate
CommentCount
9
CommunityOwnedDate
CreationDate
2013-07-28T20:52:49.627
FavoriteCount
0
LastActivityDate
2013-07-28T21:25:58.003
LastEditDate
LastEditorUserId
0
OwnerUserId
2594883
ParentId
0
PostTypeId
1
Score
0
ViewCount
343
LastEditorDisplayName
text
Body
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 : <pre><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; } </code></pre> I compile it with : <pre><code>gcc -o c.out my_avl.c -Wall -g </code></pre> Νο worthy warnings... Running this main i get from gdb : <pre><code>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...) </code></pre> Running the code in another main with about 210,000 long int items, i get the following error : <pre><code>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...) </code></pre> 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.
Tags
<c><recursion><segmentation-fault><avl-tree>
Title
C : Cannot access memory error, when finding recursively an AVL tree height
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USAlek Sobczyk
plurals
PostLinksPostIdRelatedPostId
1. PL
 singulars
 LinkTypeLinkTypeId
 LTLinked
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POC : Cannot access memory error, when finding recursively an AVL tree height
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTModeratorReview
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.