数据结构-第三部分

单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三部分 集合,集合中的元素互相之间没有关系,集合的存储：借用其他容器,集合的操作：查找和排序,这一部分将介绍,排序算法,散列表,不相交集,1,第7章 集合与静态查找表,集合的基本概念,查找的基本概念,无序表的查找,有序表的查找,STL中的静态表,2,集合的基本概念,集合中的数据元素除了属于同一集合之外，没有任何逻辑关系。,在集合中，每个数据元素有一个区别于其他元素的唯一标识，通常称为键值或关键字值,集合的主要运算：,查找某一元素是否存在,将集合中的元素按照它的唯一标识排序,3,集合的存储,任何容器都能存储集合,常用的表示形式是借鉴于线性表或树,唯一一个仅适合于存储和处理集合的数据结构是散列表,4,第7章 集合与静态查找表,集合的基本概念,查找的基本概念,无序表的查找,有序表的查找,STL中的静态表,5,查找的基本概念,用于查找的集合称之为查找表,查找表的分类：,静态查找表,动态查找表,内部查找,外部查找,6,静态查找表的存储,静态查找表可以用顺序表存储。 如C+的标准模板库中的类模板vector，或第二章中定义的seqList，或直接存储在C+的原始数组中。,查找函数应该是一个函数模板。模板参数是数据元素的类型。,7,第7章 集合与静态查找表,集合的基本概念,查找的基本概念,无序表的查找,有序表的查找,STL中的静态表,8,无序表的查找,无序表：数组中的元素是无序的,无序表的查找：毫无选择只能做线性的顺序查找,template ,int seqSearch(vector &data, const Type &x), data0 = x;,for (int i = data.size() - 1; x != datai; -i);,return i;,9,第7章 集合与静态查找表,集合的基本概念,查找的基本概念,无序表的查找,有序表的查找,STL中的静态表,10,有序表的查找,顺序查找,二分查找,插值查找,分块查找,11,顺序查找,与无序表的顺序查找类似，只是当被查元素在表中不存在时，不需要查到表尾,template ,int seqSearch(vector &data, const Type &x), data0 = x;,for (int i = data.size() - 1; x datai; -i);,if ( i = 0 | x != datai) return 0; else return i;,12,有序表的查找,顺序查找,二分查找,插值查找,分块查找,13,二分查找,每次检查待查数据中排在最中间的那个元素,如中间元素等于要查找的元素，则查找完成,否则，确定要找的数据是在前一半还是在后一半，然后缩小范围，在前一半或后一半内继续查找。,14,查找 x=8,0,1,2,mid=4 但 key=9 10,向左,key,4,8,9,10,11,13,19,3,4,5,6,7,high=7,low=1,0,1,2,mid=2 找到,key,4,8,9,10,11,13,19,3,4,5,6,7,high=7,low=1,15,template ,int binarySearch(const vector &data,const Type &x), int low = 1, high = data.size() - 1, mid;,while (low = high ) /查找区间存在, mid = (low + high) / 2; /计算中间位置,if ( x = datamid ) return mid;,if ( x datamid) high = mid - 1;,else low = mid + 1;,return 0;,16,有序表的查找,顺序查找,二分查找,插值查找,分块查找,17,插值查找,适用于数据的分布比较均匀的情况,查找位置的估计,缺点：计算量大,18,插值查找适用情况,访问一个数据元素必须比一个典型的指令费时得多。例如，数组可能在磁盘里而不是在内存里，而且每次比较都需要访问一次磁盘。,这些数据必须不仅有序，而且分布相当均匀，这可以使每次估计都相当准确，可以将大量的数据排除出查找范围。这样，花费这些计算代价是值得的,19,有序表的查找,顺序查找,二分查找,插值查找,分块查找,20,分块查找,分块查找也称为索引顺序块的查找。,是处理大量数据查找的一种方法。,它把整个有序表分成若干块，块内的数据元素可以是有序存储，也可以是无序的，但块之间必须是有序的。,21,查找由两个阶段组成：查找索引和查找块,22,第7章 集合与静态查找表,集合的基本概念,查找的基本概念,无序表的查找,有序表的查找,STL中的静态表,23,STL中的静态表,对应于顺序查找和二分查找，C+的标准模板库中提供两个模板函数：find和binary_search。这两个函数模板都位于标准库algorithm中,find函数顺序查找一个序列,find有两个模板参数。第一个模板参数是对应于存储集合数据的容器的迭代器。第二个模板参数是集合元素的类型。,函数有三个形式参数。第一、二个形式参数是两个迭代器对象，指出查找的范围。第三个参数是需要查找的对象值。,find函数的返回值是一个迭代器对象，指出了被查找的元素在容器中的位置。,24,binary_search,binary_search函数用二分查找的方式查找一个有序序列。,它也有两个模板参数。第一个模板参数是对应于存储集合数据的容器的迭代器。第二个模板参数是集合元素的类型。,函数也有三个形式参数。第一、二个形式参数是两个迭代器对象，指出查找的范围。第三个参数是需要查找的对象值。,函数的返回值是bool类型的，指出了被查找的元素在容器中是否存在。如果存在，返回true，否则，返回false。,25,应用实例,#include ,#include ,#include ,using namespace std;,int main(), int a = 2,4,7,8,10,12,13,15,16,19,20;,vector v;,vector:iterator itr;,for (int i=0; i11; +i) v.push_back(ai);,if (binary_search(v.begin(), v.end(),13),cout 13 存在n;,else cout 13 不存在n;,itr = find(v.begin(), v.end(),13);,cout *itr left );,else if( t-data right );,else return true;,63,insert函数的实现,template ,void BinarySearchTree:insert( const Type & x ), insert( x, root ); ,template ,void BinarySearchTree:insert( const Type & x, BinaryNode *&t ), if( t = NULL ),t = new BinaryNode( x, NULL, NULL );,else if( x data ) insert( x, t-left );,else if( t-data right );,64,insert函数设计说明,私有的insert函数的第二个形式参数，它是一个指向结点的指针的非常量引用。,这个引用符号不能省略。正是这个引用，使得新插入的结点和它的父结点之间关联了起来。,65,remove函数的实现,template ,void BinarySearchTree:remove(,const Type & x ),remove( x, root );,66,template ,void BinarySearchTree:remove( const Type & x,BinaryNode * & t ), if( t = NULL ) return;,if( x data ) remove( x, t-left );,else if( t-data right );,else if( t-left != NULL & t-right != NULL ) ,BinaryNode *tmp = t-right;,while (tmp-left != NULL) tmp = tmp-left;,t-data = tmp-data;,remove( t-data, t-right );,else BinaryNode *oldNode = t;,t = ( t-left != NULL ) ? t-left : t-right;,delete oldNode;,67,remove函数设计说明,同样请注意私有的remove函数的参数，它的第二个参数也是指向结点的指针的引用。,与插入过程一样，这个引用也不能去掉。正是这个引用使得被删结点的父结点和被删结点的儿子连接起来。,68,二叉查找树类的使用,int main (), int a = 10, 8, 6, 21, 87, 56, 4, 0 , 11, 3, 22, 7, 5, 34, 1, 2, 9;,BinarySearchTree tree;,for (int i = 0; i 17; +i) tree.insert(ai);,cout endl find 2 is (tree.find(2)?true:false) endl;,tree.remove(2);,cout after delete 2, find 2 is (tree.find(2)?true:false) endl;,cout find 3 is (tree.find(3)?true:false) endl;,tree.remove(3);,cout after delete 3, find 3 is (tree.find(3)?true:false) endl;,cout find 21 is (tree.find(21)?true:false) endl;,tree.remove(21);,cout after delete 21, find 21 is (tree.find(21)?true:false), endl;,return 0;,69,10,21,87,9,11,8,7,6,0,4,3,1,2,56,22,34,70,第8章 动态查找表,二叉查找树,AVL树,红黑树,AA树,伸展树,B树和B+树,STL中的动态查找表,71,AVL树,AVL树的定义,AVL树的插入操作,AVL树的删除,AVL树类的实现,72,平衡二叉查找树,当树退化为链表时，树的优点荡然无存。要使查找树的性能尽可能好，就要使得树尽可能丰满。要构造一个丰满树很困难，一种替代的方案是平衡树。,D,G,E,D,A,B,C,F,E,G,B,A,C,F,73,二叉平衡树,二叉平衡树就是满足某种平衡条件的二叉查找树,平衡条件：,容易维护,保证树的高度是O(logN),74,平衡条件,最简单的想法是让左右子树有同样的高度。但它并不能保证树是矮胖的。,另一个想法是要求每个节点的左右子树都有同样的高度。这个条件能保证树是矮胖的，但这个条件太苛刻，只有满二叉树才满足这个条件。,将上述条件稍微放宽一些就是二叉平衡查找树。,75,平衡树的定义,平衡因子（平衡度）：结点的平衡度是结点的左子树的高度右子树的高度。,空树的高度定义为-1。,平衡二叉树：每个结点的平衡因子都为 1、1、0 的二叉树。或者说每个结点的左右子树的高度最多差1的二叉树。,可以证明平衡树的高度至多约为：1.44log(N+2) -1.328,76,是平衡树不是丰满树,不是平衡树,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,14,5,3,9,28,63,53,60,50,17,18,30,+1,+2,-1,-1,0,0,0,0,0,+1,-1,77,平衡二叉树的查找性能,定理：具有 N,个结点的平衡树，高度 h 满足：log,2,(N+1) = h height;,void LL( AvlNode * ,void LR( AvlNode * ,void RL( AvlNode * ,void RR( AvlNode * ,int max(int a, int b) return (ab)?a:b;,;,109,find函数的非递归实现,template ,bool AvlTree:find( const Type & x ) const,AvlNode *t = root;,while (t!=NULL & t-data != x),if (t-data x) t = t-left; else t = t-right;,if (t=NULL) return false; else return true;,110,LL,template ,void AvlTree:LL( AvlNode * & t ),AvlNode *t1 = t-left;,t-left = t1-right;,t1-right = t;,t-height = max( height( t-left ), height( t-right ) ) + 1;,t1-height = max( height( t1-left ), height(t) + 1;,t = t1;,A,B,+1,h-1,0,+2,+1,h,h-1,h-1,B,L,B,R,A,R,危机结点,111,RR,template ,void AvlTree:RR( AvlNode * & t ),AvlNode *t1 = t-right;,t-right = t1-left;,t1-left = t;,t-height = max( height( t-left ), height( t-right ) ) + 1;,t1-height = max( height( t1-right ), height(t) + 1;,t = t1;,A,B,-1,h-1,0,-2,-1,h-1,h-1,B,R,B,L,A,L,危机结点,112,LR,和RL,template ,void AvlTree:LR( AvlNode * & t ),RR( t-left );,LL( t );,template ,void AvlTree:RL( AvlNode * & t ),LL( t-right );,RR( t );,113,私有的insert函数的实现,template ,void AvlTree:insert( const Type & x, AvlNode * & t ), if( t = NULL ),t = new AvlNode( x, NULL, NULL );,else if( x data ) ,insert( x, t-left );,if( height( t-left ) - height( t-right ) = 2 ),if( x left-data ) LL( t ); else LR(t);,else if( t-data right );,if( height( t-right ) - height( t-left ) = 2 ),if( t-right-data height = max( height( t-left ) , height( t-right ) ) + 1;,114,私有的remove函数的实现,template ,bool AvlTree:remove( const Type & x, AvlNode * & t ), bool stop =false;,int subTree; / 1表示删除发生在左子树上，,/ 2表示删除发生在右子树上,if( t = NULL ) return true;,115,if( x data ) stop = remove( x, t-left ); subTree = 1;,else if( t-data right ); subTree = 2;,else if( t-left != NULL & t-right != NULL ) ,AvlNode *tmp = t-right;,while(tmp-left != NULL) tmp = tmp-left;,t-data = tmp-data;,stop = remove( t-data, t-right );,subTree = 2;,else AvlNode *oldNode = t;,t = ( t-left != NULL ) ? t-left : t-right;,delete oldNode;,return false;,if (stop) return true;,int bf;,116,switch(subTree) ,case 1: bf = height(t-left) - height(t-right) + 1;,/原来结点的平衡度,if (bf = 0) return true; /情况一,if (bf = 1) return false; /情况二,if (bf =-1) /情况三,int bfr = height(t-right-left) - height(t-right-right);,switch (bfr) ,case 0: RR(t); return true;,case -1: RR(t); return false;,default: RL(t); return false;,break;,117,case 2: bf = height(t-left) - height(t-right) -1;,if (bf = 0) return true; /情况一,if (bf = -1) return false; /情况二,if (bf = 1) /情况三,int bfl = height(t-right-left),- height(t-right-right);,switch (bfl) ,case 0: LL(t); return true;,case 1: LL(t); return false;,default: LR(t); return false;, ,118,第8章 动态查找表,二叉查找树,AVL树,红黑树,AA树,伸展树,B树和B+树,STL中的动态查找表,119,红黑树,红黑树的定义,红黑树的插入,红黑树的删除,红黑树类的实现,红黑树是平衡树的一种替换方案。它比平衡树效率高。红黑树在最坏情况下的操作时间是O(logN),120,红黑树的定义,每个节点都被标记为红色或是黑色的,根是黑色的,如果一个节点是红色的，那么它的儿子都是黑色的,每一条从某个节点到一个空链域的路径必须具有相同数量的黑色节点,14,12,5,3,9,28,26,15,60,50,20,25,30,23,121,红黑树,红黑树的定义,红黑树的插入,红黑树的删除,红黑树类的实现,红黑树是平衡树的一种替换方案。它比平衡树效率高。红黑树在最坏情况下的操作时间是O(logN),122,红黑树的插入,插入过程同普通的二叉查找树，只是插入后被插入的节点要被着色,着成黑色是不可能的，会违反定义4，必须着成红色,如果父节点是黑色的，插入结束。如果父节点是红色的，则违反定义3。必须调整节点的颜色,把新插入的节点称作X，P是它的父亲节点，S是它父亲的兄弟节点（空节点认为是黑色的），G是X祖父。,123,颜色调整总结,父结点P的兄弟结点S是黑色的,X是G的外侧结点：LLb，RRb,X是G的内侧结点：LRb，RLb,父结点P的兄弟结点S是红色的,124,LLb，RRb,B,D,E,C,A,G,S,B,X,P,D,E,C,A,P,G,X,S,LLb旋转,D,E,C,A,G,P,B,X,S,RRb旋转,D,E,C,A,P,X,B,S,G,调整后，树根为黑色。不需要继续调整,125,LRb，RLb,LRb旋转,B,D,E,C,A,G,S,B,P,D,E,C,A,X,G,S,X,P,B,D,E,C,A,G,S,B,P,D,E,C,A,X,G,S,RLb旋转,X,P,调整后，树根为黑色。不需要继续调整,126,14,12,5,3,9,28,26,15,60,50,20,25,30,23,1,在树中插入1，属LLb的情况,14,12,5,3,9,28,26,15,60,50,20,25,30,23,1,127,父结点P的兄弟结点S是红色的,D,E,C,A,G,S,B,X,P,D,E,C,A,G,S,B,X,P,通过重新着色，消除连续红节点,128,D,E,C,A,G,S,B,P,X,D,E,C,A,G,S,B,P,X,通过重新着色，连续的红结点就不存在了，而且路径上的黑结点数也没有变化 。,经过重新着色以后，根结点变成了红色。如果原来,X,的曾祖父就是红色的，那么又出现了连续红结点问题。于是，需要继续往上调整。最坏的情况下可能要调整到根。,129,14,12,3,5,9,28,26,15,60,50,20,25,30,23,1,55,24,插入24,14,12,3,5,9,28,26,15,60,50,20,25,30,23,1,55,24,重新着色,调整20、25的连续红节点，又是情况二。重新着色,14,12,3,5,9,28,26,15,60,50,20,25,30,23,1,55,24,130,红黑树,红黑树的定义,红黑树的插入,红黑树的删除,红黑树类的实现,红黑树是平衡树的一种替换方案。它比平衡树效率高。红黑树在最坏情况下的操作时间是O(logN),131,红黑树的删除,删除操作首先使用普通的二叉查找树的删除算法删除结点，然后进行旋转及颜色的调整。,在二叉查找树的删除中，最终可以归结到两种情况：删除叶结点和删除只有一个儿子的结点。只要解决了这两种情况下的着色问题，就解决了红黑树的删除,132,红黑树删除时的情况,删除的是红色叶结点 ：直接删除,删除只有一个儿子的结点 ：将儿子的颜色改为黑色,删除一个黑色的叶结点,133,删除一个黑色的叶结点,被调整的结点的兄弟是黑色的（如果兄弟是空结点，则认为是黑色结点）,被调整的结点的兄弟是红色的,删除这个结点将会使得这个位置变成了一个空结点。因此，这条路径上少了一个黑结点。我们将这个空结点称为被调整结点。,134,被调整的结点的兄弟是黑色的,L0和R0：兄弟结点有0个红孩子,L1L和R1R：兄弟有一个红孩子，且为它的外侧的孩子,L1R和R1L：兄弟有一个红孩子，且为它的内侧的孩子,L2和R2：兄弟有两个红孩子,135,L0和R0,p,s,z,p,s,z,父节点原来可以为任意颜色。如果父结点原来是红色的，现在变成了黑色，调整可以结束了。但如果父结点原来就是黑色的，现在经过父结点的所有路径都少了一个黑结点。于是继续调整。,136,L1L和R1R,p,sr,sl,s,z,p,sr,sl,s,z,新的根结点的颜色和老的根结点的颜色是相同的，因此也不会出现连续的红结点的问题。调整可以结束了,137,L1R和R1L,p,sr,sl,s,z,srl,srr,p,sr,sl,s,z,srl,srr,由于新的根结点的颜色和老的根结点的颜色是相同的，因此也不会出现连续的红结点的问题。调整可以结束了,138,L2和R2,p,sr,sl,s,z,srl,srr,p,sr,sl,s,z,srl,srr,L2的调整方法和L1R是一样的，R2的调整方法和R1L是一样的,139,删除一个黑色的叶结点,被调整的结点的兄弟是黑色的（如果兄弟是空结点，则认为是黑色结点）,被调整的结点的兄弟是红色的,删除这个结点将会使得这个位置变成了一个空结点。因此，这条路径上少了一个黑结点。我们将这个空结点称为被调整结点。,140,兄弟结点是红色的,如果被调整结点的兄弟结点是红色的，那么父结点一定是黑色的，兄弟结点的儿子也一定是黑色的。,旋转后，红黑树的特性得以保持，但被调整结点的兄弟结点变成了黑色。,第2种情况转换成了第1种情况，,p,s,z,sl,sr,p,s,z,sl,sr,141,14,12,3,5,9,28,26,15,60,50,20,25,30,23,1,55,24,在下列红黑树中删除26，违反了红黑树的性质，25的右路径少了一个黑结点，是属于第二种情况,14,12,3,5,9,28,15,60,50,20,25,30,23,1,55,24,142,旋转后，结果如下，被调整节点（25的右孩子）的兄弟变成了黑色而且有一个红孩子，属于L1R的情况。,14,12,3,5,9,28,15,60,50,20,25,30,23,1,55,24,14,12,3,5,9,28,15,60,50,20,25,30,23,1,55,24,调整后，这棵树恢复了平衡,继续调整,143,红黑树,红黑树的定义,红黑树的插入,红黑树的删除,红黑树类的实现,红黑树是平衡树的一种替换方案。它比平衡树简单。红黑树在最坏情况下的操作时间是O(logN),144,红黑树类的实现,红黑树的节点类需要一个保存颜色的数据成员,插入、删除时的调整需要用到父节点可祖父节点，所以用迭代的方式实现,145,红黑树类的定义,template ,class RedBlackTree,struct RedBlackNode, Type data;,RedBlackNode *left;,RedBlackNode *right;,int colour; / 0 - Red, 1 - Black,RedBl