所以我尝试在 C 中实现 AVL 树。我对插入使用递归，虽然我对少量项目获得了一些好的结果，但在大输入时我得到了“无法访问内存...”，如下所示。
在我发布代码之前。问题似乎在于 height() 计算。使用 gdb 并逐步进行旋转以查看是否有任何问题，但它似乎表现良好。（没有未初始化的指针，更改后没有垃圾）。avl_insert() 代码有点乱，但我花了 2 天时间仔细检查它，我很确定它是正确的。
所以，这里是代码：
#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;
}
我编译它：
gcc -o c.out my_avl.c -Wall -g
值得警告...
运行这个我从 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...)
在另一个包含大约 210,000 个长 int 项的主程序中运行代码，我收到以下错误：
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...)
在回溯中观察身高的争论，他们似乎在重复。我想也许一些“父母”或“孩子”在旋转过程中没有被正确清除，创建了一个无限循环或其他东西，但经过数小时的测试，我无法在代码中找到这样的错误。我真的被困在这里......提前感谢您的帮助。