算法导论06--红黑树构建算法

一、目的

1．熟悉算法设计的基本思想
2．掌握构建红黑树的方法

二、内容与设计思想

1. 编写随机整数生成算法，生成S到T范围内的N个随机整数并输出；
2. 编写红黑树构建算法，中序遍历各节点，输出颜色和值；
3. 随机生成1e2、1e3、1e4、1e5、1e6个不同的数，使用红黑树构建算法，并画图描述不同情况下的运行时间差异；

三、使用环境

推荐使用C/C++集成编译环境。

四、实验过程

1、写出红黑树构建算法的源代码

#include
using namespace std;
#define RED 0
#define BLACK 1
#define MAXN 100000001int a[MAXN];typedef struct RBTreeNode
{char color;int key; struct RBTreeNode *lchild;struct RBTreeNode *rchild;struct RBTreeNode *parent;
}Node,*RBTree;typedef struct rb_root
{Node *node; 
} RBRoot;RBRoot* creat_rbtree()
{RBRoot *root=(RBRoot*)malloc(sizeof(RBRoot));root->node=NULL; return root;
}Node*  creat_rbtree_node(int key,Node *parent,Node *lchild,Node *rchild)
{Node* p;p=(Node*)malloc(sizeof(Node));p->key=key;p->lchild=lchild;p->rchild=rchild;p->color=BLACK;return p;
}void rbtree_left_rotate(RBRoot *root,Node *x)
{Node *y=x->rchild;x->rchild=y->lchild;if (y->lchild!= NULL)y->lchild->parent = x;y->parent=x->parent;if(x->parent==NULL){root->node=y; }else{if(x->parent->lchild==x)  {x->parent->lchild=y;    }else{x->parent->rchild=y;}}y->lchild=x; x->parent=y;
}void rbtree_right_rotate(RBRoot *root,Node *y)
{Node *x=y->lchild;y->lchild=x->rchild;if(x->rchild!=NULL){x->rchild->parent=y;} x->parent=y->parent;if(y->parent==NULL){root->node=x;} else{if(y->parent->rchild==y) {y->parent->rchild=x;    }else{y->parent->lchild=x;}}x->rchild=y; y->parent=x;
}void rbtree_insert_fixup(RBRoot *root, Node *node)
{Node *parent, *gparent;while ((parent = node->parent) && (parent->color==RED)){gparent = parent->parent;if (parent == gparent->lchild){{Node *uncle = gparent->rchild;if (uncle && uncle->color==RED){uncle->color=BLACK;parent->color=BLACK;gparent->color=RED;node = gparent;continue;}}if (parent->rchild == node){Node *tmp;rbtree_left_rotate(root, parent); tmp = parent;parent = node;node = tmp;}parent->color=BLACK;gparent->color=RED;rbtree_right_rotate(root, gparent);} else{{Node *uncle = gparent->lchild;if (uncle && (uncle->color==RED)){uncle->color=BLACK;parent->color=BLACK;gparent->color=RED;node = gparent;continue;}}if (parent->lchild == node){Node *tmp;rbtree_right_rotate(root, parent);tmp = parent;parent = node;node = tmp;}parent->color=BLACK;gparent->color=RED;rbtree_left_rotate(root, gparent);}}root->node->color=BLACK;
}void rbtree_insert(RBRoot *root,Node *node)
{Node *y=NULL;Node *x=root->node;while(x!=NULL){y=x;if(x->key>node->key){x=x->lchild;}else{x=x->rchild;}}node->parent=y;if(y!=NULL){if(node->key<y->key){y->lchild=node;}else {y->rchild=node;}}else{root->node=node;}node->color=RED;rbtree_insert_fixup(root, node);} int insert_rbtree(RBRoot *root,int key)
{Node *node;node=creat_rbtree_node(key,NULL,NULL,NULL); if(node==NULL) return -1;else rbtree_insert(root,node);return 0;
}void inorder(RBTree tree)
{if(tree != NULL){inorder(tree->lchild);cout<<tree->key;if(tree->color==0){cout<<"(RED)"<<" ";}else {cout<<"(BLACK)"<<" ";}inorder(tree->rchild);}
}void inorder_rbtree(RBRoot *root) 
{if (root)inorder(root->node);
}int main()
{int i,S,T,N;cin>>N>>S>>T;srand(time(0));for (i=0;i<N;i++){a[i]=rand()%(T-S)+S;}int key;RBRoot *root=NULL;root=creat_rbtree();for(i=0;i<N;i++){insert_rbtree(root,a[i]);} inorder_rbtree(root);return 0;
}

2、截取各个实验的实验结果
1e2 1e3 1e4 1e5 1e6 1e7
单位(ms) 0 0 2 53 2008 32826

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！