红黑树及生成超过32768随机数

/*-----------------------------------------------------------
    RB-Tree的插入和删除操作的实现算法

    红黑树的几个性质:
    1) 每个结点只有红和黑两种颜色
    2) 根结点是黑色的
    3)空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
    4) 如果一个结点是红色的,那么它的左右两个子结点的颜色是黑色的
    5) 对于每个结点而言,从这个结点到叶子结点的任何路径上的黑色结点
    的数目相同
-------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <conio.h>
#include <map>
using namespace std;

typedef int key_t;
typedef int data_t;

typedef enum color_t
{
RED = 0,
BLACK = 1
}color_t;

typedef struct rb_node_t
{
    struct rb_node_t *left, *right, *parent;
    key_t key;
    data_t data;
    color_t color;
}rb_node_t;

/* forward declaration */
rb_node_t* rb_insert(key_t key, data_t data, rb_node_t* root);
rb_node_t* rb_search(key_t key, rb_node_t* root);
rb_node_t* rb_erase(key_t key, rb_node_t* root);

int tmpValue = 0;
int useCount = 0;

#define GetRdm(min, max) (rand()*((float)((max)-(min)))/(float)(RAND_MAX)+(min))

int main()
{
    int i, count = 99999999;
    int sizes = 10000000;
    key_t key;
    rb_node_t* root = NULL, *node = NULL;

    map<key_t,data_t> mapInfo;
    map<key_t,data_t>::iterator iter;

    srand((unsigned int)time(NULL));
    //插入测试
    for (i = 1; i < sizes; ++i)
    {
        key = GetRdm(0,10000)*GetRdm(0,10000)*GetRdm(0,10);
        if(useCount==32768)
            srand((unsigned int)time(NULL));

        iter = mapInfo.find(key);
        root = rb_insert(key, i, root);
        if(iter != mapInfo.end())
        {
            if( tmpValue!= iter->second)
                printf("%d\n",i);
        }
        else
        {
            mapInfo[key] = i;
        }
    }

    //查找测试
    for(iter = mapInfo.begin();iter!=mapInfo.end();++iter)
    {
        node = rb_search(iter->first, root);
        if(node==NULL )
        {
            printf("not find!\n");
        }
        else if(node->data!=iter->second)
        {
            printf("value=%d!=%d\n",node->data,iter->second);
        }
    }

    //删除测试
    for(iter = mapInfo.begin();iter!=mapInfo.end();++iter)
    {
        root = rb_erase(iter->first, root);
    }

    printf("[%d]end.\n",useCount);
    getch();
    return 0;
}

static rb_node_t* rb_new_node(key_t key, data_t data)
{
    rb_node_t *node = (rb_node_t*)malloc(sizeof(struct rb_node_t));
    ++useCount;
    if (!node)
    {
        printf("malloc error!\n");
        exit(-1);
    }
    node->key = key, node->data = data;

return node;
}

/*-----------------------------------------------------------
|   node           right
|   / \    ==>     / \
|   a right     node y
|       / \           / \
|       b y         a   b
-----------------------------------------------------------*/
static rb_node_t* rb_rotate_left(rb_node_t* node, rb_node_t* root)
{
    rb_node_t* right = node->right;

    if ((node->right = right->left))
    {
        right->left->parent = node;
    }
    right->left = node;

    if ((right->parent = node->parent))
    {
        if (node == node->parent->right)
        {
            node->parent->right = right;
        }
        else
        {
            node->parent->left = right;
        }
    }
    else
    {
        root = right;
    }
    node->parent = right;

return root;
}

/*-----------------------------------------------------------
|       node           left
|       / \            / \
|    left y   ==>    a   node
|   / \               / \
| a   b      &

补充：软件开发 , C语言 ,