免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › Size Balance Tree和Treap的ADT接口和实现
12下一页
最近访问板块 发新帖
查看: 9425 | 回复: 12
打印 上一主题 下一主题

[算法] Size Balance Tree和Treap的ADT接口和实现 [复制链接]

augustusqing

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2007-12-08 12:04 |只看该作者 |倒序浏览
1M个整数插入删除，不优化的情况下， SBT费时5.2秒，Treap才2.1秒，说SBT比Treap快，怎么不觉得了，不明白
文件：include/Item.h

  2. /*-----------------------------------------------------------
  3.         Item.h
  4.         作者： QingXiaoming, 12-03, 2007([url]http://www.cublog.com/augustusqing/[/url])
  5.         您可以自由的传播，修改这份代码，转载处请注明原作者
  6. -------------------------------------------------------------*/

  8. #ifndef ITEM_H
  9. #define ITEM_H

  11. typedef int Item;

  13. #endif
复制代码

文件：include/SBTree_ADT.h

  2. /*-----------------------------------------------------------
  3.         SBT的ADT接口
  4.         Author: QingXiaoming, 12-05, 2007([url]http://www.cublog.com/augustusqing/[/url]
  5.         您可以自由拷贝，修改，传播这份代码，但请注明原作者
  6. -------------------------------------------------------------*/

  8. #ifndef SBTREE_ADT_H
  9. #define SBTREE_ADT_H
  10. #include "Item.h"
  11. typedef struct SBTree *SBTree;
  12. typedef struct SBTreeNode *SBTreeLink;

  14. SBTree initSBTree(void);
  15. int emptySBTree(SBTree);
  16. int sizeSBTree(SBTree);
  17. void showSBTreeNode(SBTreeLink);
  18. void destroySBTree(SBTree);
  19. void pretravseSBTree(SBTree);
  20. void midtravseSBTree(SBTree);
  21. int rankSBTree(SBTree, SBTreeLink);

  23. Item seqSBTree(SBTree, int);
  24. SBTreeLink findSBTree(SBTree, Item);
  25. Item preSBTree(SBTree, Item);
  26. Item sucSBTree(SBTree, Item);
  27. Item minSBTree(SBTree);
  28. Item maxSBTree(SBTree);
  29. void insertSBTree(SBTree, Item);
  30. SBTreeLink deleteSBTree(SBTree, Item);

  32. #endif
复制代码


文件：include/Treap_ADT.h

  2. /*-----------------------------------------------------------
  3.         Treap的ADT接口
  4.         作者： QingXiaoming, 12-04, 2007([url]http://www.cublog.com/augustusqing/[/url])
  5.         您可以自由的传播，修改这份代码，转载处请注明原作者
  6. -------------------------------------------------------------*/

  8. #ifndef TREAP_ADT_H
  9. #define TREAP_ADT_H
  10. #include "Item.h"
  11. typedef struct treap *Treap;
  12. typedef struct treapnode *TreapLink;

  14. Treap initTreap(int);
  15. int emptyTreap(Treap);
  16. TreapLink findTreapNode(Treap, Item);
  17. void insertTreap(Treap, Item);
  18. TreapLink deleteTreap(Treap, Item);
  19. void midtravseTreap(Treap);
  20. void pretravseTreap(Treap);
  21. void destroyTreap(Treap);
  22. #endif

复制代码


文件：include/SBTree_ADT_user.c

  2. /*-----------------------------------------------------------
  3.         SBTree的ADT客户程序
  4.         Author: QingXiaoming, 12-05, 2007([url]http://www.cublog.com/augustusqing/[/url]
  5.         您可以自由拷贝，修改，传播这份代码，但请注明原作者
  6. -------------------------------------------------------------*/
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <time.h>
  10. #include "include/SBTree_ADT.h"

  12. int main(int argc, char *argv[])
  13. {
  14.     int i, N = atoi(argv[1]);//, M = atoi(argv[2]);
  15.     Item t;//,ta;
  16.     SBTree tree = initSBTree();
  17.     //SBTreeLink x;
  18.     long start, stop;
  19.     srand((unsigned)clock());
  20.     start = clock();
  21.     for (i = 0; i < N; i++)
  22.     {
  23.         t = rand() + i;
  24.         insertSBTree(tree, t);
  25.     }
  26.     //pretravseSBTree(tree);
  27.     printf("\n");
  28.     //midtravseSBTree(tree);
  29.     //printf("\n");
  30.     /*
  31.     t = seqSBTree(tree, M);
  32.     ta = sucSBTree(tree, t);
  33.     printf("Size:%d, Rank %d is : %d, Min:%d, Max:%d, Pre:%d, Suc:%d\n",
  34.            sizeSBTree(tree), M, t, minSBTree(tree), maxSBTree(tree), preSBTree(tree, t), sucSBTree(tree, t));
  35.     x = deleteSBTree(tree, t);
  36.     free(x);
  37.     x = findSBTree(tree, ta);
  38.     showSBTreeNode(x);
  39.     printf("After delete %d,Size:%d,  Min:%d, Max:%d, Rank of suc:%d\n",
  40.            t, sizeSBTree(tree), minSBTree(tree), maxSBTree(tree), rankSBTree(tree, x));
  41.    
  42.     printf("Befor destroy, Tree is %s\n", emptySBTree(tree) ? "Empty" : "Not Empty");
  43.     */
  44.     destroySBTree(tree);
  45.    
  46.     printf("After destroy, Tree is %s\n", emptySBTree(tree) ? "Empty" : "Not Empty");
  47.     stop = clock();
  48.     printf("Time :%ld", stop - start);
  49.     return 0;
  50. }

复制代码


文件：include/Treap_ADT_user.c

  2. /*-----------------------------------------------------------
  3.         Treap的ADT客户程序
  4.         作者： QingXiaoming, 12-04, 2007([url]http://www.cublog.com/augustusqing/[/url])
  5.         您可以自由的传播，修改这份代码，转载处请注明原作者
  6. -------------------------------------------------------------*/
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <time.h>
  10. #include "include/Treap_ADT.h"

  12. int main(int argc, char *argv[])
  13. {
  14.     int i, N = atoi(argv[1]);
  15.     Item t;
  16.     Treap tree = initTreap(N);
  17.     //TreapLink x;
  18.     long start, stop;
  19.     start = clock();
  20.     for (i = 0; i < N; i++)
  21.     {
  22.         t = i;
  23.         insertTreap(tree, t);
  24.     }
  25.     //pretravseTreap(tree);
  26.     printf("\n");
  27.     //midtravseTreap(tree);
  28.     /*
  29.     for (i = 2;i < N; i += 2)
  30.     {
  31.         x = deleteTreap(tree, i);
  32.         free(x);
  33.         printf("\n");
  34.         pretravseTreap(tree);
  35.         printf("\n");
  36.         midtravseTreap(tree);  
  37.         system("pause");   
  38.     }
  39.     */
  40.     destroyTreap(tree);
  41.     stop = clock();
  42.     printf("Time :%ld", stop - start);
  43.     return 0;
  44. }
复制代码
augustusqing

论坛徽章:
0
2楼 [报告]
发表于 2007-12-08 12:05 |只看该作者
文件：SBTree_ADT.c

  2. /*-----------------------------------------------------------
  3.         SBTree的ADT实现
  4.         作Author: QingXiaoming, 12-05, 2007([url]http://www.cublog.com/augustusqing/[/url]
  5.         您可以自由拷贝，修改，传播这份代码，但请注明原作者
  6. -------------------------------------------------------------*/

  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include "include/SBTree_ADT.h"

  12. struct SBTreeNode {
  13.        Item item;
  14.        SBTreeLink lchild;
  15.        SBTreeLink rchild;
  16.        int size;
  17.        };
  18. struct SBTree {
  19.        SBTreeLink root;
  20.        };
  21.       
  22. static SBTreeLink NEW(Item item)
  23. {
  24.        SBTreeLink x = NULL;
  25.        x = malloc(sizeof(*x));
  26.        if (!x){perror("Get memory for Node error");return NULL;}
  27.        x->item = item;
  28.        x->lchild = x->rchild = NULL;
  29.        x->size = 1;
  30.        return x;
  31. }

  33. SBTree initSBTree()
  34. {
  35.        SBTree x = NULL;
  36.        x = malloc(sizeof(*x));
  37.        if (!x){perror("Get memory for tree error");return NULL;}
  38.        x->root = NULL;
  39.        return x;
  40. }

  42. int emptySBTree(SBTree tree)
  43. {
  44.     return tree->root == NULL;
  45. }
  46. void showSBTreeNode(SBTreeLink x)
  47. {
  48.      printf("Item=%d, Size=%d, Left=%d, Right=%d\n",x->item, x->size, (NULL != x->lchild)?x->lchild->item:-1,(NULL != x->rchild)?x->rchild->item:-1);
  49. }

  51. int sizeSBTree(SBTree tree)
  52. {
  53.     if(!tree || !tree->root){perror("Size a NULL tree");return -1;}
  54.     return tree->root->size;
  55. }

  57. Item maxSBTree(SBTree tree)
  58. {
  59.      if(!tree || !tree->root){perror("Max a NULL tree");return -1;}
  60.      return seqSBTree(tree, sizeSBTree(tree));
  61. }

  63. Item minSBTree(SBTree tree)
  64. {
  65.      if(!tree || !tree->root){perror("Min a NULL tree");return -1;}
  66.      return seqSBTree(tree, 1);
  67. }

  69. SBTreeLink findSBTree(SBTree tree, Item item)
  70. {
  71.     SBTreeLink x  = tree->root;
  72.     while (x && item != x->item)
  73.     {
  74.           x = (item < x->item) ? x->lchild : x->rchild;
  75.     }
  76.     return x;
  77. }

  79. Item preSBTree(SBTree tree, Item item)
  80. {
  81.      int r;
  82.      SBTreeLink x = findSBTree(tree, item);
  83.      if (!x){printf("No item %d in the tree", item);return -1;}
  84.      r = rankSBTree(tree, x);
  85.      if (1 == r){printf("item %d is No.1, Can't Pre this item", item);return -1;}
  86.      return seqSBTree(tree, r - 1);  
  87. }

  89. Item sucSBTree(SBTree tree, Item item)
  90. {
  91.      int r;
  92.      SBTreeLink x = findSBTree(tree, item);
  93.      if (!x){printf("No item %d in the tree", item);return -1;}
  94.      r = rankSBTree(tree, x);
  95.      if (sizeSBTree(tree) == r){printf("item %d is No.MAX, Can't Suc this item", item);return -1;}
  96.      return seqSBTree(tree, r + 1);
  97. }

  99. static void pretravseSBTreeNode(SBTreeLink link)
  100. {
  101.        if (link)
  102.        {
  103.            showSBTreeNode(link);
  104.            pretravseSBTreeNode(link->lchild);
  105.            pretravseSBTreeNode(link->rchild);
  106.        }
  107. }

  109. void pretravseSBTree(SBTree tree)
  110. {
  111.      return pretravseSBTreeNode(tree->root);
  112. }

  114. static void midtravseSBTreeNode(SBTreeLink link)
  115. {
  116.        if (link)
  117.        {
  118.            midtravseSBTreeNode(link->lchild);
  119.            showSBTreeNode(link);
  120.            midtravseSBTreeNode(link->rchild);
  121.        }
  122. }
  123. void midtravseSBTree(SBTree tree)
  124. {
  125.      return midtravseSBTreeNode(tree->root);
  126. }

  128. static void Left_Rotate(SBTreeLink *link)
  129. {
  130.        SBTreeLink y, x = *link;
  131.        if (!x || !x->rchild){perror("Cant Right Rotate NULL node or NULL lchild");return;}
  132.        y = x->rchild;
  133.        x->rchild = y->lchild;
  134.        *link = y;
  135.        y->lchild = x;
  136.        y->size = x->size;
  137.        x->size = ((x->lchild != NULL) ? x->lchild->size: 0) + ((x->rchild != NULL) ? x->rchild->size: 0) + 1;
  138. }

  140. static void Right_Rotate(SBTreeLink *link)
  141. {
  142.        SBTreeLink y, x = *link;
  143.        if (!x || !x->lchild){perror("Cant Right Rotate NULL node or NULL lchild");return;}
  144.        y = x->lchild;
  145.        x->lchild = y->rchild;
  146.        *link = y;
  147.        y->rchild = x;
  148.        y->size = x->size;
  149.        x->size = ((x->lchild != NULL) ? x->lchild->size: 0) + ((x->rchild != NULL) ? x->rchild->size: 0) + 1;
  150. }

  152. static void maintainSBTree(SBTreeLink *link, int flag)
  153. {
  154.        SBTreeLink t = *link;
  155.        if(!t)return;
  156.        if (!flag)
  157.        {
  158.            if (t->lchild && t->lchild->lchild && (!t->rchild || t->lchild->lchild->size > t->rchild->size))
  159.            {
  160.                 Right_Rotate(link);
  161.            }
  162.            else if (t->lchild && t->lchild->rchild && (!t->rchild || t->lchild->rchild->size > t->rchild->size))
  163.            {
  164.                 Left_Rotate(&(t->lchild));
  165.                 Right_Rotate(link);
  166.            }
  167.            else return;
  168.        }
  169.        else
  170.        {
  171.            if (t->rchild && t->rchild->rchild && (!t->lchild || t->rchild->rchild->size > t->lchild->size))
  172.            {
  173.                 Left_Rotate(link);
  174.            }
  175.            else if (t->rchild && t->rchild->lchild && (!t->lchild || t->rchild->lchild->size > t->lchild->size))
  176.            {
  177.                 Right_Rotate(&(t->rchild));
  178.                 Left_Rotate(link);
  179.            }
  180.            else return;
  181.        }
  182.        maintainSBTree(&(t->lchild), 0);
  183.        maintainSBTree(&(t->rchild), 1);
  184.        maintainSBTree(link, 0);
  185.        maintainSBTree(link, 1);
  186. }
  187. static void insertSBTreeNode(SBTreeLink *link, Item item)
  188. {
  189.       SBTreeLink x = *link;
  190.       if (!x)
  191.       {
  192.           *link = NEW(item);
  193.           return;
  194.       }
  195.       else
  196.       {
  197.           x->size += 1;
  198.           insertSBTreeNode((item < x->item) ? &(x->lchild) : &(x->rchild), item);
  199.           maintainSBTree(link, item > x->item);
  200.       }
  201. }

  203. void insertSBTree(SBTree tree, Item item)
  204. {
  205.       SBTreeLink x = findSBTree(tree, item);
  206.       if (x)
  207.       {
  208.           //printf("Cant insert a Exist item into tree!\n");
  209.           return;
  210.       }
  211.       return insertSBTreeNode(&tree->root, item);
  212. }

  214. SBTreeLink deleteSBTree(SBTree tree, Item item)
  215. {
  216.     Item t;
  217.     SBTreeLink n, m, z, y, x = tree->root;
  218.     if (!x){perror("Cant delete node from NULL tree");return NULL;}
  219.     if (item == x->item && !x->rchild)
  220.     {
  221.         tree->root = x->lchild;
  222.         return x;
  223.     }// find the node with item
  224.     while (x && (item != x->item))
  225.     {
  226.           z = x;
  227.           x = (item < x->item) ? x->lchild : x->rchild;        
  228.     }//find the x's father node
  229.     if (x)
  230.     {
  231.           if (x->rchild)
  232.           {
  233.               z = x;
  234.               y = x->rchild;
  235.               while (y->lchild)
  236.               {
  237.                     z = y;
  238.                     y = y->lchild;
  239.               }
  240.           }// find y, the node will really be deleted, and his father
  241.           else
  242.           {
  243.               y = x;
  244.           }
  245.     }
  246.     else
  247.     {
  248.         printf("No item %d in the SBTree\n", item);
  249.         return NULL;
  250.     }
  251.     //handle the y's child
  252.     m = y->lchild ? y->lchild : y->rchild;
  253.     if (y == z->lchild)
  254.     {
  255.           z->lchild = m;
  256.     }
  257.     else
  258.     {
  259.           z->rchild = m;
  260.     }
  261.     n = tree->root;
  262.     while (n != z)
  263.     {
  264.           n->size--;
  265.           n = item < n->item ? n->lchild : n->rchild;
  266.     }//modify the size, from root the the y's parent
  267.     z->size--;// also y's father
  268.     if(x != y)
  269.     {
  270.          t = x->item; x->item = y->item; y->item = t;
  271.     }
  272.     return y;
  273. }

  275. static Item seqSBTreeNode(SBTreeLink link, int i)
  276. {
  277.     int r;
  278.     if (!link){perror("You want to Seq a non-exist number Node");return -1;}
  279.     r = (NULL != link->lchild) ? (link->lchild->size + 1) : 1;
  280.     if (i == r){return  link->item;}
  281.     else return (i < r) ? seqSBTreeNode(link->lchild, i) : seqSBTreeNode(link->rchild, i-r);
  282. }
  283. Item seqSBTree(SBTree tree, int i)
  284. {
  285.     return seqSBTreeNode(tree->root, i);
  286. }

  288. int rankSBTree(SBTree tree , SBTreeLink link)
  289. {
  290.     int r = 0;
  291.     SBTreeLink x = tree->root;
  292.     if(!tree->root || !link){perror("You want to Rank a non-exist Node or NULL tree");return -1;}
  293.     while (x != link)
  294.     {
  295.           if (link->item > x->item)
  296.           {
  297.               r += (NULL != x->lchild) ? (x->lchild->size + 1) : 1;
  298.               x = x->rchild;
  299.           }
  300.           else
  301.           {
  302.               x = x->lchild;
  303.           }   
  304.     }
  305.     r += (NULL != x->lchild) ? (x->lchild->size + 1) : 1;
  306.     return r;
  307. }

  309. void destroySBTree(SBTree tree)
  310. {
  311.      SBTreeLink y, x = tree->root;
  312.      while (x)
  313.      {
  314.            y = deleteSBTree(tree, x->item);
  315.            free(y);
  316.            x = tree->root;
  317.      }
  318. }
复制代码


文件：Treap_ADT.c

  2. /*-----------------------------------------------------------
  3.         Treap的ADT实现
  4.         作者： QingXiaoming, 12-04, 2007([url]http://www.cublog.com/augustusqing/[/url])
  5.         您可以自由的传播，修改这份代码，转载处请注明原作者
  6. -------------------------------------------------------------*/

  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include "include/Treap_ADT.h"

  12. struct treapnode {
  13.        Item item;
  14.        TreapLink parent;
  15.        TreapLink lchild;
  16.        TreapLink rchild;
  17.        int prio;
  18.        };
  19. struct treap {
  20.        TreapLink root;
  21.        };

  23. static int priobase = 1;
  24. static TreapLink NEW(Item item, TreapLink parent);
  25. static void Left_Rotate(Treap tree, TreapLink x);
  26. static void Right_Rotate(Treap tree, TreapLink x);
  27. static void pretravseTreapNode(TreapLink root);
  28. static void midtravseTreapNode(TreapLink root);

  30. static TreapLink NEW(Item item, TreapLink parent)
  31. {
  32.        TreapLink x = NULL;
  33.        x = malloc(sizeof(*x));
  34.        if (!x){perror("Get memory for Node error");return NULL;}
  35.        x->item = item;
  36.        x->parent = parent;
  37.        x->lchild = NULL;
  38.        x->rchild = NULL;
  39.        x->prio = rand()%priobase;
  40.        return x;
  41. }

  43. Treap initTreap(int N)
  44. {
  45.       Treap x = NULL;
  46.       x = malloc(sizeof(*x));
  47.       if (!x){perror("Get memory for Treap error");return NULL;}
  48.       x->root = NULL;
  49.       priobase = N;
  50.       return x;
  51. }

  53. int emptyTreap(Treap tree)
  54. {
  55.     return tree->root == NULL;
  56. }

  58. TreapLink findTreapNode(Treap tree, Item item)
  59. {
  60.     TreapLink x = tree->root;
  61.     while (NULL != x && item != x->item)
  62.     {
  63.           x = (item < x->item) ? x->lchild : x->rchild;
  64.     }
  65.     return x;
  66. }

  68. static void Left_Rotate(Treap tree, TreapLink x)
  69. {
  70.        TreapLink y;
  71.        if (!x || !x->rchild){perror("Cant Left_Rotate NULL  or NULL rchild");exit(-1);}
  72.        y = x->rchild;
  73.        x->rchild = y->lchild;
  74.        if (y->lchild)
  75.        {
  76.            y->lchild->parent = x;
  77.        }
  78.        y->parent = x->parent;
  79.        if (x == tree->root)
  80.        {
  81.            tree->root = y;
  82.        }
  83.        else
  84.        {
  85.            if ( x == x->parent->lchild)
  86.            {
  87.                 x->parent->lchild = y;
  88.            }
  89.            else
  90.            {
  91.                x->parent->rchild = y;
  92.            }
  93.        }
  94.        y->lchild = x;
  95.        x->parent = y;
  96. }

  98. static void Right_Rotate(Treap tree, TreapLink x)
  99. {
  100.        TreapLink y;
  101.        if (!x || !x->rchild){perror("Cant Right_Rotate NULL  or NULL rchild");exit(-1);}
  102.        y = x->lchild;
  103.        x->lchild = y->rchild;
  104.        if (y->rchild)
  105.        {
  106.            y->rchild->parent = x;
  107.        }
  108.        y->parent = x->parent;
  109.        if (x == tree->root)
  110.        {
  111.            tree->root = y;
  112.        }
  113.        else
  114.        {
  115.            if ( x == x->parent->lchild)
  116.            {
  117.                 x->parent->lchild = y;
  118.            }
  119.            else
  120.            {
  121.                x->parent->rchild = y;
  122.            }
  123.        }
  124.        y->rchild = x;
  125.        x->parent = y;
  126. }

  128. static void fixinsertTreap(Treap tree, TreapLink link)
  129. {

  131.     while (NULL != link->parent && link->prio < link->parent->prio)
  132.     {
  133.           if (link == link->parent->lchild)
  134.           {
  135.               Right_Rotate(tree, link->parent);
  136.           }
  137.           else
  138.           {
  139.               Left_Rotate(tree, link->parent);
  140.           }
  141.     }
  142. }

  144. void insertTreap(Treap tree, Item item)
  145. {
  146.      TreapLink y, x = tree->root;
  147.      if (!tree->root)
  148.      {
  149.          x = tree->root = NEW(item, tree->root);
  150.          return;
  151.      }
  152.      while (NULL != x)
  153.      {
  154.            y = x;
  155.            x = (item < x->item) ? x->lchild : x->rchild;
  156.      }
  157.      if (item < y->item)
  158.      {
  159.          x = y->lchild = NEW(item, y);
  160.      }
  161.      else
  162.      {
  163.          x = y->rchild = NEW(item, y);
  164.      }
  165.      fixinsertTreap(tree, x);
  166. }

  168. TreapLink deleteTreap(Treap tree, Item item)
  169. {
  170.     TreapLink z, y, x = findTreapNode(tree, item);
  171.     Item t;
  172.     if (!x){printf("Cant find item:%d to delete!\n", item);return NULL;}
  173.     if (NULL != x->rchild)
  174.     {
  175.         y = x->rchild;
  176.         while (NULL != y->lchild)
  177.         {
  178.               y = y->lchild;
  179.         }
  180.     }
  181.     else
  182.     {
  183.         y = x;
  184.     }
  185.     z = (NULL != y->lchild) ? y->lchild : y->rchild;
  186.     if (NULL != z)
  187.     {
  188.         z->parent = y->parent;
  189.     }
  190.     if (NULL != y->parent)
  191.     {
  192.         if (y == y->parent->lchild)
  193.         {
  194.             y->parent->lchild = z;
  195.         }
  196.         else
  197.         {
  198.             y->parent->rchild = z;
  199.         }
  200.     }
  201.     else
  202.     {
  203.         tree->root = z;
  204.     }
  205.     if (y != x)
  206.     {
  207.           t = x->item;
  208.           x->item = y->item;
  209.           y->item = t;
  210.     }
  211.     return y;
  212. }

  214. static void midtravseTreapNode(TreapLink root)
  215. {
  216.      if (NULL != root)
  217.      {
  218.          midtravseTreapNode(root->lchild);
  219.          printf("Item:%5d, Prio:%5d\n", root->item, root->prio);
  220.          midtravseTreapNode(root->rchild);        
  221.      }
  222. }

  224. static void pretravseTreapNode(TreapLink root)
  225. {
  226.      if (NULL != root)
  227.      {
  228.          printf("Item:%5d, Prio:%5d\n", root->item, root->prio);
  229.          pretravseTreapNode(root->lchild);
  230.          pretravseTreapNode(root->rchild);        
  231.      }
  232. }

  234. void midtravseTreap(Treap tree)
  235. {
  236.      midtravseTreapNode(tree->root);
  237. }

  239. void pretravseTreap(Treap tree)
  240. {
  241.      pretravseTreapNode(tree->root);
  242. }

  244. void destroyTreap(Treap tree)
  245. {
  246.      TreapLink x;
  247.      for (x = tree->root; NULL != x; x = tree->root)
  248.      {
  249.            x = deleteTreap(tree, x->item);
  250.            free(x);
  251.      }
  252.      free(tree);
  253. }
复制代码
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
converse

论坛徽章:
0
3楼 [报告]
发表于 2007-12-08 12:34 |只看该作者
做个保留,以后看看.
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
hotjuly

论坛徽章:
0
4楼 [报告]
发表于 2007-12-08 22:29 |只看该作者
A Disquisition on The Performance Behaviour of Binary Search Tree Data Structures
http://www.upgrade-cepis.org/issues/2004/5/up5-5Mosaic.pdf
---------------------
performance comparison of binary search trees.        Treap       was found to have the best average performance, while              red-black tree            was found to have the smallest amount of performance fluctuations.

[ 本帖最后由 hotjuly 于 2007-12-8 22:33 编辑 ]
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
augustusqing

论坛徽章:
0
5楼 [报告]
发表于 2007-12-11 16:55 |只看该作者

回复 #4 hotjuly 的帖子

多谢提供这么好的文章！
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
TiGEr.zZ

论坛徽章:
0
6楼 [报告]
发表于 2009-06-24 17:51 |只看该作者
楼主的实现稍有问题，Treap中删除未做旋转，插入好像也是有问题的，同时SBT实现效率稍差了些。
测试Treap插入的数据没有调用rand()，Treap自身必须的随机运算不能算。当然这一点对Treap影响不大，rand()也只需很少的时间而已。
还有实际测试中的插入和删除操作，都要随机化才能表现的比较清楚平均水平。

个人看了一下，大概SBT的插入效率要稍差于Treap（可能还有其他一些树），但删除因为可以不作旋转，要远高于Treap，平均数高也有保证。不同实现的差异也很大，要经过比较成熟的测试才可能说明一些问题。

[ 本帖最后由 TiGEr.zZ 于 2009-6-24 17:55 编辑 ]
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
anders0913

论坛徽章:
0
7楼 [报告]
发表于 2009-06-24 20:34 |只看该作者
这种测试，和数据也有一定关系~~
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
anders0913

论坛徽章:
0
8楼 [报告]
发表于 2009-06-24 20:35 |只看该作者
还有那个SBT实现，可以去维基百科上找找，那里有一些不错的实现~~
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
TiGEr.zZ

论坛徽章:
0
9楼 [报告]
发表于 2009-06-30 18:04 |只看该作者
化了些功夫做了一个完整的测试，对比了红黑树，Treap和SBT，结果显示红黑树总体性能最优。
为了仅仅考察树的性能，采用预先分配节点内存，树的实现不参与节点内存管理。节点中都包含指向父节点的指针，这样实现删除测试中分为按节点删除，和按关键字删除。

测试方法是先插入大量节点，查询所有节点值，然后按2的指数方从少至多的删除节点，同时再查询，重新插入那些节点。再做一遍按关键字的递增删除和插入，最后是清除所有节点。

插入：红黑树领先不少，Treap和SBT差不太多，在做了删除后，SBT的插入性能似乎稍稍下降，原因未知。

查找：红黑树和SBT相差不大，处于领先，Treap要落后很多，毕竟树高度没有保证，也可能是随机数不够好。在删除了少量节点后，前两者查询时间还似乎微微上涨，也许是节点中重复关键字减少了。SBT树删除虽然没有做平衡，但仍然随着节点的大量减少保持着类似性能（在删除实现中，虽然没做平衡也有意根据左右子树的size来选择使用前驱节点还是后继节点来替换当前节点）

删除：按节点删除时，红黑树和Treap因为不需要遍历树，所以有着很高的性能，SBT因为要维护所有父辈的size而导致落后。在按关键字删除，相当于搜索节点再删除，SBT因为不作树的平衡维护性能要领先一些。

附件是代码，把树的实现和测试放在的一个文件中，基本采用较传统的c编程风格，除了变量定义以及在SBT中为了简化代码而不降低性能使用了bool型模板（否则可以作为函数参数传递）。可以提取那些非static函数和类型定义形成树头文件。SBT的代码参考了：http://www.nocow.cn/index.php/Code:SBT_C，而红黑树的代码参考了linux内核中的实现，相对而言后者实现难度最大。

[ 本帖最后由 TiGEr.zZ 于 2009-6-30 18:06 编辑 ]

test.7z

3.5 KB, 下载次数: 64
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
luoleicn

论坛徽章:
0
10楼 [报告]
发表于 2009-06-30 18:42 |只看该作者
楼主是内存里读写速度的比较？
平衡树是为磁盘读写而生的

如果是内存的话哈希应该更快吧为什么用树？
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP