二叉平衡树AVL的插入和删除的C实现源码

converse

原帖由 win_hate 于 2007-11-4 17:32 发表
红黑树不是 AVL 的特例

AVL 的左子树和右子树高度最多相差 1， 而红黑的最长路径可以是最短路径的两倍， AVL 比红黑树要平衡。

AVL 的删除最多需要 O(lg n) 次旋转，而红黑树的删除需要不多于 3 次旋转， ...

是的,今天也正找这方面的资料,前面的理解是不对的.

这里有几篇文章进行比较的:
http://blog.chinaunix.net/u1/35281/showart_279925.html
http://blog.csdn.net/naivebaby/archive/2006/11/04/1366579.aspx

但是里面的解释:

AVL trees are actually easier to implement than RB trees because there are fewer cases.  And AVL trees require O(1) rotations on an insertion, whereas red-black trees require O(lg n).
In practice, the speed of AVL trees versus red-black trees will depend on the data that you're inserting.  If your data is well distributed, so that an unbalanced binary tree would generally be acceptable (i.e. roughly in random order), but you want to handle bad cases anyway, then red-black trees will be faster because they do less unnecessary rebalancing of already acceptable data.On the other hand, if a pathological insertion order (e.g. increasing order of key) is common, then AVL trees will be faster, because the stricter balancing rule will reduce the tree's height.
Splay trees might be even faster than either RB or AVL trees,depending on your data access distribution.  And if you can use a hash instead of a tree, then that'll be fastest of all.

并不能让我满意.

自己尝试了一下插入同样多的数据,红黑树的效率比AVL慢一倍.

augustusqing

Hi，我用你的程序测试了下
测试代码稍微修改了下，用随机数据，运行是带上参数20，如下所示，程序在pause暂停时就只输出了一个数，感觉你测试的数据太少了，^_^

1. 
   
2. int main(int argc, char *argv[])
   
3. {
   
4.   int t, i, N = atoi(argv[1]);
   
5.   int *data = malloc(N * sizeof(*data));
   
6.   for (i = 0; i < N; i++)
   
7.   {
   
8.         t = rand() + i;
   
9.         data[i] = t;
   
10.   }
    
11.   node* root;
    
12.   root = createAVL(data, sizeof(data)/sizeof(data[0]));
    
13. 
    
14.   printf("++++++++++++++++++++++++++++\n");
    
15.   traverseAVL1(root);
    
16.   printf("\n");
    
17.   traverseAVL2(root);
    
18.   system("pause");
    
19. 
    
20.   root = deleteNode(5, root);
    
21.   printf("++++++++++++++++++++++++++++\n");
    
22.   traverseAVL1(root);
    
23.   printf("\n");
    
24.   traverseAVL2(root);
    
25. 
    
26.   root = deleteNode(3, root);
    
27.   printf("++++++++++++++++++++++++++++\n");
    
28.   traverseAVL1(root);
    
29.   printf("\n");
    
30.   traverseAVL2(root);
    
31. 
    
32.   root = deleteNode(1, root);
    
33.   printf("++++++++++++++++++++++++++++\n");
    
34.   traverseAVL1(root);
    
35.   printf("\n");
    
36.   traverseAVL2(root);
    
37. 
    
38.   root = deleteNode(7, root);
    
39.   printf("++++++++++++++++++++++++++++\n");
    
40.   traverseAVL1(root);
    
41.   printf("\n");
    
42.   traverseAVL2(root);
    
43. 
    
44.   root = deleteNode(4, root);
    
45.   printf("++++++++++++++++++++++++++++\n");
    
46.   traverseAVL1(root);
    
47.   printf("\n");
    
48.   traverseAVL2(root);
    
49. 
    
50.   root = deleteNode(2, root);
    
51.   printf("++++++++++++++++++++++++++++\n");
    
52.   traverseAVL1(root);
    
53.   printf("\n");
    
54.   traverseAVL2(root);
    
55. 
    
56.   destroyAVL(root);
    
57.   
    
58.   return 0;
    
59. }
    

复制代码

ypxing

>>int *data;
>>...
>> root = createAVL(data, sizeof(data)/sizeof(data[0]));

你这样写代码是不对的

原帖由 augustusqing 于 2007-12-7 15:17 发表
Hi，我用你的程序测试了下
测试代码稍微修改了下，用随机数据，运行是带上参数20，如下所示，程序在pause暂停时就只输出了一个数，感觉你测试的数据太少了，^_^

int main(int argc, char *argv[])
{
  in ...

anthony1983

代码拷下来了。

记得以前看AVL树，自己只把插入实现了，删除有些复杂，就懒得实现了，现在正好学习一下

ypxing

>>root = createAVL(data, sizeof(data)/sizeof(data[0]));
替换成root = createAVL(data, N);

而且后面要删除key,你要修改一下

原帖由 anthony1983 于 2007-12-7 15:30 发表
代码拷下来了。

记得以前看AVL树，自己只把插入实现了，删除有些复杂，就懒得实现了，现在正好学习一下

[ 本帖最后由 ypxing 于 2007-12-7 15:37 编辑 ]

anthony1983

原帖由 ypxing 于 2007-12-7 15:34 发表
>>root = createAVL(data, sizeof(data)/sizeof(data[0]));
替换成root = createAVL(data, N);

为啥

ypxing

他前面是这样定义data的:

>>int t, i, N = atoi(argv[1]);
>> int *data = malloc(N * sizeof(*data));
>>  for (i = 0; i < N; i++)
>>  {
>>        t = rand() + i;
>>        data = t;
>>  }
>>  node* root;
>>  root = createAVL(data, sizeof(data)/sizeof(data[0]));

所以sizeof(data)为4, sizeof(data[0])也为4
他误把data作为数组了, 这就错了

原帖由 anthony1983 于 2007-12-7 15:35 发表

为啥

anthony1983

原帖由 ypxing 于 2007-12-7 15:40 发表
他前面是这样定义data的:

>>int t, i, N = atoi(argv[1]);
>> int *data = malloc(N * sizeof(*data));
>>  for (i = 0; i < N; i++)
>>  {
>>        t = rand() + i;
>>        data = t;
>>  }
>> ...

汗~~我拷下来的是数组~~int data[] = {1, 5, 7, 4, 3, 2, 11, 9, 10};

ypxing

误会了, 我回的是augustusqing的帖子,

原帖由 anthony1983 于 2007-12-7 15:54 发表


汗~~我拷下来的是数组~~int data[] = {1, 5, 7, 4, 3, 2, 11, 9, 10};

augustusqing

晕，不好意思啊，^_^，现在能跑对了，我再测测看，^_^