数据结构动态选择求第k小元素问题

东北大学信息科学与工程学院数据结构课程设计报告题目 动态选择求第k小元素问题课题组长 肖瑶课题组成员 陈果 张帅专业名称 计算机科学与技术班级 计1307指导教师 杨雷2015 年 1月 课程设计任务书题目：B12、动态选择求第k小元素问题问题描述：一棵红黑树本身就是一棵二叉排序树。红黑树中的结点颜色是黑色或红色。从红黑树的根结点到叶子结点的路径上的黑色结点数目相同，最短的路径就是所有结点都是黑色。集合中的元素是动态构成的。要求对集合中的n个元素求解第k小的元素。设计要求：设计应用红黑平衡二叉树实现动态查找第k小的元素。（1）实现动态查找表的三种基本功能：查找、插入、删除。（2）实现红黑平衡二叉树的动态查找第k小的元素。（3）可以考虑与快速排序方法的实现做比较。指导教师签字：2014年12月24日 课题程序设计分工学号姓名程序设计函数原型、类功能说明20133995 肖瑶PRBTreeNode RBTREE_DELETE(PRBTree pTree, PRBTreeNode pDel)static void FIX_UP_RB_AFTER_DELETE(PRBTree pTree, PRBTreeNode pNode)void RBTREE_INSERT(PRBTree pTree, PRBTreeNode pNode)static void FIX_UP_RB_AFTER_INSERT(PRBTree pTree, PRBTreeNode pNode)红黑树的节点删除在红黑树删除动作后进行红黑性质恢复红黑树的节点插入在红黑树插入动作后进行红黑性质恢复20134002 陈果PRBTreeNode RBTREE_MAX(PRBTreeNode pRoot)PRBTreeNode RBTREE_MIN(PRBTreeNode pRoot)PRBTreeNode RBTREE_PREDECESSOR(PRBTreeNode pRoot)PRBTreeNode RBTREE_SUCCESSOR(PRBTreeNode pRoot)PRBTreeNode RBTREE_SEARCH(PRBTreeNode pRoot, int val_key)void K_min_elem(PRBTree pTree, int k) 查找最大键值节点 查找最小键值节点查找指定节点的前趋节点查找指定节点的后继节点查找指定键值的节点查找第K小元素,输出键值与颜色20133997 张帅typedef struct tagRBTree typedef struct tagRBTreeNodePRBTreeNode CreateRBTreeNode(int keyVal)void DeleteRBTreeNode(PRBTreeNode pDel)void InitRBTree(PRBTree pTree) void INORDER_RBTREE_WALK(PRBTreeNode pRoot)int main()static void LEFT_ROTATION(PRBTree pTree, PRBTreeNode pNode)static void RIGHT_ROTATION(PRBTree pTree, PRBTreeNode pNode)红黑树结构红黑树结点结构生成一个红黑树节点释放一个节点的内存 初始化一棵红黑树 中序遍历二叉树主函数对指定节点进行左旋对指定节点进行右旋 课题报告分工章节内容完成人1 课题概述1.1 课题任务1.2 课题原理 1.3 相关知识 张帅 2 需求分析2.1 课题调研 2.2 用户需求分析 肖瑶3 方案设计3.1 总体功能设计3.2 数据结构设计3.3 函数原型设计3.4 主算法设计3.5 用户界面设计 张帅4 方案实现4.1 开发环境与工具4.2 程序设计关键技术4.3 个人设计实现（按组员分工）4.3.1 4.3.2 4.3.3 陈果5 课题总结5.1 课题评价5.2 团队协作5.3 个人设计心得（按组员分工）5.3.1 5.3.2 5.3.3 肖瑶1 课题概述一棵红黑树本身就是一棵二叉排序树。红黑树中的结点颜色是黑色或红色。从红黑树的根结点到叶子结点的路径上的黑色结点数目相同，最短的路径就是所有结点都是黑色。集合中的元素是动态构成的。要求对集合中的n个元素求解第k小的元素。1.1 课题任务设计应用红黑平衡二叉树实现动态查找第k小的元素。（1）实现动态查找表的三种基本功能：查找、插入、删除。（2）实现红黑平衡二叉树的动态查找第k小的元素。 （3）可以考虑与快速排序方法的实现做比较。1.2 课题原理红黑二叉树是一种比较先进的二叉树，它的统计性能要好于平衡 二叉树。可以方便的用红黑树对大量数据进行快速的查找、添加、删除。1.3 相关知识红黑树的介绍:红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为对称二叉B树，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。红黑树的5个性质：1.每个结点要么是红的要么是黑的。 2.根结点是黑的。 3.每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。 4.如果一个结点是红的，那么它的两个儿子都是黑的。 5.对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。要知道为什么这些特性确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点不包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们使用 nil 叶子 或空(null)叶子，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好象同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。2 需求分析2.1 课题调研二叉排序树有3个性质：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； （3）左、右子树也分别为二叉排序树。平衡二叉树（Balanced Binary Tree）又被称为AVL树，是一种优化的二叉排序树，具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。（以上三段资料来源于教材，清华大学出版社，数据结构-C语言版，严蔚敏、吴伟民编著）红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。（来源于百度百科）下图所示，即是一颗红黑树：2.2 用户需求分析用户要求在一组数据中查找第K小元素，为了是查找效率最高，本算法用红黑二叉树实现，同时实现的还有元素的查找、添加与删除。3 方案设计3.1 总体功能设计实现动态查找表的三种基本功能：查找、插入、删除；实现红黑平衡二叉树的动态查找第k小的元素。3.2 数据结构设计建立树与结点的结构体，构造红黑二叉树，对元素进行查找，插入与删除以及查找、删除后进行红黑性质的恢复。3.3 函数原型设计生成一个红黑树节点，缺省的节点颜色是红黑。 PRBTreeNode CreateRBTreeNode(int keyVal)void InitRBTree(PRBTree pTree) / 初始化一棵红黑树 中序遍历二叉树，并输出键值与颜色void INORDER_RBTREE_WALK(PRBTreeNode pRoot)查找指定键值的节点 PRBTreeNode RBTREE_SEARCH(PRBTreeNode pRoot, int val_key)对指定节点进行左旋static void LEFT_ROTATION(PRBTree pTree, PRBTreeNode pNode)对指定节点进行右旋static void RIGHT_ROTATION(PRBTree pTree, PRBTreeNode pNode)在红黑树插入动作后进行红黑性质恢复static void FIX_UP_RB_AFTER_INSERT(PRBTree pTree, PRBTreeNode pNode)红黑树的节点插入void RBTREE_INSERT(PRBTree pTree, PRBTreeNode pNode)在红黑树删除动作后进行红黑性质恢复static void FIX_UP_RB_AFTER_DELETE(PRBTree pTree, PRBTreeNode pNode)红黑树的节点删除PRBTreeNode RBTREE_DELETE(PRBTree pTree, PRBTreeNode pDel)查找第K小元素,输出键值与颜色void K_min_elem(PRBTree pTree, int k)3.4 主算法设计int main() RBTree bsTree; InitRBTree(&bsTree); int _key; printf(请先创建一个红黑书，依次输入元素的整型数值，以#结束!n); printf(请输入第1个数值:); scanf(%d,&_key); bsTree.root-key=_key; PRBTreeNode p_Node; RBTREE_INSERT(&bsTree,bsTree.root); for(int i=2;_key!=#;i+) printf(请输入第%d个数值：,i); scanf(%d,&_key); p_Node-key=_key; RBTREE_INSERT(&bsTree,p_Node); printf(插入元素-1 查找元素-2n); printf(删除元素-3 查找第K小元素-4n); printf(退出操作-0 n); printf(请选择您对红黑平衡二叉树的操作：); int j; scanf(%d,&j); char Judge=Y; while(Judge=Y) switch(j) case 1: PRBTreeNode p_Node;printf(请输入要插入元素的数值：);scanf(%d,&p_Node-key);RBTREE_INSERT(&bsTree,p_Node);break; case 2:printf(请输入要查找元素的数值：); int val_key; scanf(%d,&val_key); PRBTreeNode pnode;pnode=RBTREE_SEARCH(bsTree.root,val_key);printf(元素为值：%d,元素颜色为：%s ,左孩子:%d,左孩子:%d n,pnode-key,pnode-color=BLACK?BLACK:RED,pnode-left-key,pnode-right-key); break;case 3: PRBTreeNode p_Del;printf(请输入要删除元素的数值：);scanf(%d,&p_Del-key);RBTREE_DELETE(&bsTree, p_Del); break;case 4:int K;printf(请输入K值：);scanf(%d,&K); K_min_elem(&bsTree,K); break;case 0: return 0;default:break; printf(操作完成！ 请选择 继续-Y 退出-N :); scanf(%C,&Judge); return 0;3.5 用户界面设计144 方案实现154.1 开发环境与工具15开发环境Window7 开发工具：microsoft visual C+4.2 程序设计关键技术16本程序的设计关键在与红黑树的构建及红黑树性质的恢复与维护：当我们在对红黑树进行插入和删除等操作时，对树做了修改，那么可能会违背红黑树的性质。为了保持红黑树的性质，我们可以通过对树进行旋转，即修改树种某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质。左旋：当在某个结点pivot上，做左旋操作时，我们假设它的右孩子y不是NILT，pivot可以为树内任意右孩子而不是NILT的结点。左旋以pivot到y之间的链为“支轴”进行，它使y成为该孩子树新的根，而y的左孩子b则成为pivot的右孩子。右旋与之类似。插入操作：情况1：插入的是根结点原树是空树，此情况只会违反性质2。对策：直接把此结点涂为黑色。情况2：插入的结点的父结点是黑色。此不会违反性质2和性质4，红黑树没有被破坏。对策：什么也不做。情况3：当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色。此时父结点的父结点一定存在，否则插入前就已不是红黑树。与此同时，又分为父结点是祖父结点的左子还是右子，对于对称性，我们只要解开一个方向就可以了。在此，我们只考虑父结点为祖父左子的情况。同时，还可以分为当前结点是其父结点的左子还是右子，但是处理方式是一样的。我们将此归为同一类。对策：将当前节点的父节点和叔叔节点涂黑，祖父结点涂红，把当前结点指向祖父节点，从新的当前节点重新开始算法。情况4：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子。对策：当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。情况5：当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左子。对策：父节点变为黑色，祖父节点变为红色，在祖父节点为支点右旋删除：情况1：当前节点是红色。解法，直接把当前节点染成黑色，结束。情况2：当前节点是黑色且是根节点。解法：什么都不做，结束情况3：当前节点是黑色，且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。解法：把父节点染成红色，把兄弟结点染成黑色，之后重新进入算法。然后，针对父节点做一次左旋。此变换后原红黑树性质5不变，而把问题转化为兄弟节点为黑色的情况。情况4：当前节点是黑色，且兄弟是黑色，且兄弟节点的两个子节点全为黑色。解法：把当前节点和兄弟节点中抽取一重黑色追加到父节点上，把父节点当成新的当前节点，重新进入算法。情况5：当前节点颜色是黑色，兄弟节点是黑色，兄弟的左子是红色，右子是黑色。解法：把兄弟结点染红，兄弟左子节点染黑，之后再在兄弟节点为支点解右旋，之后重新进入算法。情况6：当前节点颜色是黑色，它的兄弟节点是黑色，但是兄弟节点的右子是红色，兄弟节点左子的颜色任意。解法：把兄弟节点染成当前节点父节点的颜色，把当前节点父节点染成黑色，兄弟节点右子染成黑色，之后以当前节点的父节点为支点进行左旋，此时算法结束，红黑树所有性质调整正确。4.3 个人设计实现（按组员分工）4.3.1 肖瑶设计实现：/ 在红黑树插入动作后进行红黑性质恢复static void FIX_UP_RB_AFTER_INSERT(PRBTree pTree, PRBTreeNode pNode) while(RED = pNode-parent-color) if (pNode-parent = pNode-parent-parent-left) PRBTreeNode pUncleNode = pNode-parent-parent-right; if (RED = pUncleNode-color) pNode-parent-color = BLACK; pUncleNode-color = BLACK; pNode = pUncleNode-parent; pNode-color = RED; else if (pNode = pNode-parent-right) pNode = pNode-parent; LEFT_ROTATION(pTree, pNode); pNode-parent-color = BLACK; PRBTreeNode TempP = pNode-parent-parent;TempP-color = RED; RIGHT_ROTATION(pTree, TempP); else PRBTreeNode pUncleNode = pNode-parent-parent-left; if (RED = pUncleNode-color) pNode-parent-color = BLACK; pUncleNode-color = BLACK; pNode = pUncleNode-parent; pNode-color = RED; else if (pNode = pNode-parent-left) pNode = pNode-parent; RIGHT_ROTATION(pTree, pNode); pNode-parent-color = BLACK; PRBTreeNode TempP = pNode-parent-parent; TempP-color = RED; LEFT_ROTATION(pTree, TempP); pTree-root-color = BLACK;/ 红黑树的节点插入void RBTREE_INSERT(PRBTree pTree, PRBTreeNode pNode) PRBTreeNode pNodePosition = pTree-root; PRBTreeNode pParent = PNIL; while (PNIL != pNodePosition) pParent = pNodePosition; pNodePosition = pNode-key pNodePosition-key ? pNodePosition-right :pNodePosition-left; pNode-parent = pParent; if (PNIL = pParent) pTree-root = pNode; else if (pNode-key pParent-key) pParent-right = pNode; else pParent-left = pNode; FIX_UP_RB_AFTER_INSERT(pTree, pNode);/ 在红黑树删除动作后进行红黑性质恢复static void FIX_UP_RB_AFTER_DELETE(PRBTree pTree, PRBTreeNode pNode)while (pNode-color = BLACK) & (pNode != pTree-root) if (pNode = pNode-parent-left) PRBTreeNode pBrother = pNode-parent-right; if (RED = pBrother-color) pBrother-color = BLACK; pNode-parent-color = RED; LEFT_ROTATION(pTree, pNode-parent); pBrother = pNode-parent-right; if (BLACK = pBrother-right-color) & (BLACK = pBrother-left-color) pBrother-color = RED; pNode = pNode-parent; else if (BLACK = pBrother-right-color) pBrother-color = RED; pBrother-left-color = BLACK;RIGHT_ROTATION(pTree, pBrother); pBrother = pNode-parent-right; pBrother-right-color = BLACK; pBrother-color = pNode-parent-color; pNode-parent-color = BLACK; LEFT_ROTATION(pTree, pNode-parent); pNode = pTree-root; else PRBTreeNode pBrother = pNode-parent-left; if (RED = pBrother-color) pBrother-color = BLACK; pNode-parent-color = RED; RIGHT_ROTATION(pTree, pNode-parent); pBrother = pNode-parent-left; if (BLACK = pBrother-left-color) & (BLACK = pBrother-right-color) pBrother-color = RED; pNode = pNode-parent; else if (BLACK = pBrother-left-color) pBrother-color = RED; pBrother-right-color = BLACK; LEFT_ROTATION(pTree, pBrother); pBrother = pNode-parent-left; pBrother-left-color = BLACK; pBrother-color = pNode-parent-color; pNode-parent-color = BLACK; RIGHT_ROTATION(pTree, pNode-parent); pNode = pTree-root; pNode-color = BLACK;/ 红黑树的节点删除PRBTreeNode RBTREE_DELETE(PRBTree pTree, PRBTreeNode pDel) PRBTreeNode pRelDel; if (PNIL = pDel-left) | (PNIL = pDel-right) pRelDel = pDel; else / pRelDel = RBTREE_SUCCESSOR(pDel); PRBTreeNode pChildOfDel; pChildOfDel = (pRelDel-left!= PNIL ? pRelDel-left : pRelDel-right); / pChildOfDel-parent = pRelDel-parent; if (PNIL = pRelDel-parent) pTree-root = pChildOfDel; else if (pRelDel = pRelDel-parent-left) pRelDel-parent-left = pChildOfDel; else pRelDel-parent-right = pChildOfDel; if (pRelDel != pDel) pDel-key = pRelDel-key; if (pRelDel-color = BLACK) FIX_UP_RB_AFTER_DELETE(pTree, pChildOfDel); return pRelDel; 4.3.2 陈果设计实现：/ 查找指定键值的节点 PRBTreeNode RBTREE_SEARCH(PRBTreeNode pRoot, int val_key) while (PNIL != pRoot) & (val_key != pRoot-key) pRoot = (val_key key ? pRoot-left : pRoot-right); return pRoot;/ 查找最大键值节点 PRBTreeNode RBTREE_MAX(PRBTreeNode pRoot) while (PNIL != pRoot-right) pRoot = pRoot-right; return pRoot;/ 查找最小键值节点PRBTreeNode RBTREE_MIN(PRBTreeNode pRoot) while (PNIL != pRoot-left) pRoot = pRoot-left; return pRoot;/ 查找指定节点的后继节点PRBTreeNode RBTREE_SUCCESSOR(PRBTreeNode pRoot) if (PNIL != pRoot-right) return RBTREE_MIN(pRoot-right); PRBTreeNode pParent = pRoot-parent; while(PNIL != pParent) & (pRoot = pParent-right) pRoot = pParent; pParent = pRoot-parent; return pParent;/ 查找指定节点的前趋节点PRBTreeNode RBTREE_PREDECESSOR(PRBTreeNode pRoot)if (PNIL != pRoot-left) return RBTREE_MAX(pRoot-left); PRBTreeNode pParent = pRoot-parent;while(PNIL != pParent) & (pRoot = pRoot-left) pRoot = pParent; pParent = pRoot-parent; return pParent;/ 打印出红黑树每个节点的各项值。void RBTREE_STRUCTURE(PRBTreeNode pRoot)#define GetKey(p) (p=PNIL?-1:p-key) if (PNIL != pRoot) printf(KeyValue = %d, color = %s, Left = %d, Right = %d, Parent = %dn, pRoot-key, pRoot-color=BLACK?BLACK:RED, GetKey(pRoot-left), GetKey(pRoot-right), GetKey(pRoot-parent); RBTREE_STRUCTURE(pRoot-left); RBTREE_STRUCTURE(pRoot-right); /查找第K小元素,输出键值与颜色void K_min_elem(PRBTree pTree, int k) int i;PRBTreeNode pNode=RBTREE_MIN(pTree-root);for(i=2;ikey,pNode-color=BLACK?BLACK:RED); 4.3.3 张帅设计实现：/ 定义节点颜色 enum COLOR BLACK = 0, RED;/ 红黑树节点typedef struct tagRBTreeNode int key; struct tagRBTreeNode *left; struct tagRBTreeNode *right; struct tagRBTreeNode *parent; unsigned char color;RBTreeNode, *PRBTreeNode;/ 红黑树，包含一个指向根节点的指针 typedef struct tagRBTree PRBTreeNode root;RBTree, *PRBTree;/ 红黑树的NIL节点static RBTreeNode NIL = 0, 0, 0, 0, BLACK;#define PNIL (&NIL) / NIL节点地址 / 生成一个红黑树节点，缺省的节点颜色是红黑。 PRBTreeNode CreateRBTreeNode(int keyVal) PRBTreeNode p = (PRBTreeNode)malloc(sizeof(RBTreeNode); p-color = RED; p-left = PNIL; p-right = PNIL; p-parent = PNIL; p-key = keyVal; return p;/ 释放一个节点的内存 void DeleteRBTreeNode(PRBTreeNode pDel) if (PNIL != pDel) free(pDel); void InitRBTree(PRBTree pTree) / 初始化一棵红黑树 pTree-root = PNIL;/ 中序遍历二叉树，并输出键值与颜色void INORDER_RBTREE_WALK(PRBTreeNode pRoot) if (PNIL != pRoot) INORDER_RBTREE_WALK(pRoot-left); printf(元素为值：%d,元素颜色为：%s n,pRoot-key,pRoot-color=BLACK?BLACK:RED); INORDER_RBTREE_WALK(pRoot-right); / 对指定节点进行左旋static void LEFT_ROTATION(PRBTree pTree, PRBTreeNode pNode) PRBTreeNode pRight = pNode-right; pRight-parent = pNode-parent; if(pNode-parent-left = pNode) pRight-parent-left = pRight; else pRight-parent-right = pRight; if (PNIL = pRight-parent) pTree-root = pRight; if (PNIL != pRight-left) pRight-left-parent = pNode; pNode-right = pRight-left; pNode-parent = pRight; pRight-left = pNode;/ 对指定节点进行右旋static void RIGHT_ROTATION(PRBTree pTree, PRBTreeNode pNode) PRBTreeNode pLeft = pNode-left; pLeft-parent = pNode-parent; if(pNode-parent-left = pNode) pLeft-parent-left = pLeft; else pLeft-parent-right = pLeft; if (PNIL = pLeft-parent) pTree-root = pLeft; if (PNIL != pLeft-right) pLeft-right-parent = pNode; pNode-left = pLeft-right; pNode-parent = pLeft; pLeft-right = pNode;int main() RBTree bsTree; InitRBTree(&bsTree); int _key; printf(请先创建一个红黑书，依次输入元素的整型数值，以#结束!n); printf(请输入第1个数值:); scanf(%d,&_key); bsTree.root-key=_key; PRBTreeNode p_Node; RBTREE_INSERT(&bsTree,bsTree.root); for(int i=2;_key!=#;i+) printf(请输入第%d个数值：,i); scanf(%d,&_key); p_Node-key=_key; RBTREE_INSERT(&bsTree,p_Node); printf(插入元素-1 查找元素-2n); printf(删除元素-3 查找第K小元素-4n); printf(退出操作-0 n); printf(请选择您对红黑平衡二叉树的操作：); int j; scanf(%d,&j); char Judge=Y; while(Judge=Y) switch(j) case 1: PRBTreeNode p_Node;printf(请输入要插入元素的数值：);