set四个集合操作&&红黑树初识

set四个集合操作&&红黑树初识

了解红黑树：首先说说二叉查找树。二叉查找树的重要性质：任何节点的键值一定大于其左子树中每一个节点的键值，并小于其右子树中每一个节点的键值。在极端情况下，当所有节点位于一条链上时，二叉查找树的操作时间为O(N)。沿树的左边向下走，能够找到最小值。沿着树的右边走能够找到最大值。

和二叉搜索树一样，红黑树（一种特殊的二叉查找树）可以支持search，minimum，maximun,insert,delete等操作，同时保证了在最坏情况下集合操作的时间复杂度是O(lgn).

从某个结点出发（不含这个结点）到达一个叶节点的任意一条简单路径上的黑色结点的个数称为该节点的黑高。写为bh(x)

每个结点有5个属性：color,key,left,right,p。红黑树有以下性质： 1.每个节点红或黑色的。 2.根结点是黑色的。 3.每个叶子结点是黑色的。 4.一个结点是红色的那么两个子结点是黑色的。 5.从任意结点到其后代叶子结点的简单路径上，均包含相同数目的黑色结点一颗有n个内部结点的红黑树高度至多是2lg(n+1)  //以任意结点x为根的子树至少包含2^[(bhx)-1]-1个内部结点.

插入删除结点后可能违背或破坏红黑树原有的性质，为了维持原有的特性需要重新着色，左旋，右旋。红黑树的具体代码操作较为复杂，是数据结构里的高级产品，具体的旋转，插入和删除请参考《算法导论》。带有哨兵的T.nil的红黑树：

与红黑树相关的C++关联容器map和set：两者内部自建一颗红黑树，具有排序功能，不涉及内存的copy和move仅仅是指针的移动，所以效率较高。缺点是比较占用内存空间。

四个set_operator集合操作 四个set_集合操作set_union,set_intersection,set_difference,set_symmetric_difference除set_union外比较的集合对象要是严格升序的。并且 The return value of set_() is an iterator to the end of the operator range.当然也可以使用类似于：set_union(ap.begin(),ap.end(),bp.begin(),bp.end(),inserter(cp,cp.begin()));的语句在cp的指定位置cp.begin()的前插入。 set_symmetric_difference：对称差集：是指并集和交集的差集。 输入数据： 4 56 78 90 102 4 56 90 100 150

#include #include#include#includeusing namespace std;vector ap,bp,cp;void show(){ vector::iterator ix=cp.begin(); for(;ix!=cp.end();ix++){ cout<<*ix<<" "; } cout<>n; while(n--){ int a; cin>>a; ap.push_back(a); } cin>>n; while(n--){ int b; cin>>b; bp.push_back(b); } set_intersection(ap.begin(),ap.end(),bp.begin(),bp.end(),inserter(cp,cp.begin())); //ix接收到交集的最后一个元素的iterator cout<<"set_intersection:";show(); cp.clear(); set_union(ap.begin(),ap.end(),bp.begin(),bp.end(),inserter(cp,cp.begin())); //cp.begin()); cout<<"set_union:";show(); cp.clear(); set_difference(ap.begin(),ap.end(),bp.begin(),bp.end(),inserter(cp,cp.begin())); cout<<"set_differece:"; show(); cp.clear(); set_symmetric_difference(ap.begin(),ap.end(),bp.begin(),bp.end(),inserter(cp,cp.begin())); cout<<"set_symmetric_difference:"; show(); return 0;}

输出：

set_intersection:56 90 set_union:56 78 90 100 102 150 set_differece:78 102 set_symmetric_difference:78 100 102 150

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。