南大软院ds期末试卷d.s期终复习1

1、 D.S.复习提纲 第第1章：章： 数据，数据结构，基本类型，抽象数据类型，数据，数据结构，基本类型，抽象数据类型，Java语言的面向对象语言的面向对象编程、递归的概念与实现编程、递归的概念与实现 。 主要能用递归思想写出算法主要能用递归思想写出算法 例子：例子： ppt-递归例递归例1 求求n! 递归例递归例2 求求a0+a1+a2+an-1 作业作业- 例例3 求数组中的最大值求数组中的最大值 例例4 求数组元素的平均值求数组元素的平均值 例例3,例例4如果用链表来实现呢？如果用链表来实现呢？ 复习例题复习例题-例例5 统计二叉树中的叶结点个数统计二叉树中的叶结点个数 例例6 交换每个结点

2、的左子女和右子女交换每个结点的左子女和右子女 例例1. 1. 求求n!n!factorial function f(n)=n! 1 n1 (recursive component) /递归部分递归部分 f(n)f(5)=5*f(4)=5*4f( 3)=5*4*3f(2)=5*4*3*2f(1)=120 static long factorial (int n) if ( n 0) return Rsum(a,n-1)+an-1; return 0; 例例3. 3. 求数组中的最大值求数组中的最大值public static int findMax(int a, int n)/n表示表示n个元素

3、，它们在数组个元素，它们在数组a中中 if(n= =1) return a 0; else int temp=findMax(a,n-1); return tempa n-1?temp:a n-1; int max(int a,int n) if(n = = 1) return a0;int m = max(a,n-1);if( m an-1 )return m;else return an-1;例3. 求数组中的最大值如果用链表来实现表：如果用链表来实现表： 求链表中的最大值求链表中的最大值 int GetMaxInt( ListNode f ) if( f.link = = NULL )

4、return f .data ; else int i = GetMaxInt( f.link ); if ( i f .data ) return i ; else return f .data ; 或或 else return ( f . data) ( GetMaxInt( f . link ) ) ? f . data : GetMaxInt( f . link );例例4 . 4 . 求数组元素的平均值求数组元素的平均值float average( int a,int n) if(n = = 1) return a0;else return (average(a,n-1)*(n-1)

5、+an-1)/n; 如果用链表：如果用链表： float Average( ListNode f, int n ) if( f.link = = NULL ) return f.data; else return ( Average ( f.link, n-1 ) * ( n-1 ) + f.data ) / n;例5. 统计叶子结点个数int leafNum ( BinTreeNode * root ) if ( root = = NULL ) return 0 ; if ( root-leafchild = = NULL & root-rightchild = = NULL ) retur

6、n 1; else return leafNum( root- leftchild ) + leafNum ( root- rightchild ) ; 例6. 交换左右子数void Swapchild ( BinTreeNode * p ) if ( p = = NULL ) return ; BinTreeNode * temp = p - left ; p -left = p - right ; p - right = temp; Swapchild ( p -left ); Swapchild (p -right );第第2 2章章 算法分析算法分析 复杂性上界和平均复杂度的渐近分析;

7、 最佳、最差和平均情况下的复杂度差异; 大O、和 符号 1）分析某个语句的执行次数（频度）2）分析某个程序段执行的时间复杂度（用大O表示，要求写出推导过程） ppt:-对排序算法与查找算法的分析 例1-for (int i = 1; i = n; i+) for (int j = 1; j=n; j+) cij = 0.0; for ( int k = 1; k = n; k+) cij = cij+aik*bkj; 次数为: n*n*n第第2 2章章 算法分析算法分析例例2. x = 0; y = 0; for (int i = 1; i = n; i+) for (int j = 1; j

8、 = i; j+) for (int k = 1; k 0) if(x100) x -= 10; y-; else x+; 1100次次 第3章 表、栈和队列 表、栈和队列的（基本概念，顺序存储结构，链式存储结构，应用），表、栈和队列的（基本概念，顺序存储结构，链式存储结构，应用）， 特殊矩阵的压缩存储特殊矩阵的压缩存储 表：表： 逻辑逻辑-（e1, e2, .en) e1, e2, .en) 物理物理-数组实现数组实现 链表实现链表实现-单链表单链表 循环链表循环链表 双向链表双向链表 cursor cursor 表头结点表头结点用链表实现用链表实现 操作操作-查找、插入、删除等查找、插入、

9、删除等 ppt-多项式相加多项式相加 约瑟夫问题约瑟夫问题 双链表的插入、删除双链表的插入、删除 例题例题-逆转链表等题逆转链表等题第3章 表 例例1. 逆转链表（假设不带表头结点）逆转链表（假设不带表头结点） public void inverse( ListNode f ) if ( f = = NULL ) return; ListNode p = f . link ; pr = NULL; while ( p ! = NULL ) f . link = pr ; pr = f ; f = p ; p = p . link ; f . link = pr ; 第第3 3章章例例2. 设有

10、如下结构的循环链表和可利用空间表设有如下结构的循环链表和可利用空间表 data link L a0 a1 . an-1 Avail 请在常数时间内实现将请在常数时间内实现将L链表中的所有结点归还到可利用空间表链表中的所有结点归还到可利用空间表 ListNode p = L.link; L.link = Avail; Avail = p; 栈、队列 定义定义-栈的定义，栈的定义， 队列的定义队列的定义 机内实现机内实现-数组数组 （循环队列）（循环队列） 单链表单链表 应用应用 栈栈-对表达式求值。中缀对表达式求值。中缀-后缀后缀-对后缀表达式求值对后缀表达式求值 递归函数的实现。递归函数的实现

11、。 PPT：第：第4章中用非递归实现中序章中用非递归实现中序,后序遍历后序遍历(在第在第4章中讲章中讲) 队列队列-循环队列的补充题：已知队尾元素的位置与元素的个数，循环队列的补充题：已知队尾元素的位置与元素的个数， 求队头元素的位置。求队头元素的位置。 中缀到后缀：中缀到后缀： (a+b)*(c-d)/2*e)- ab+cd-2/e* 用了什么栈？用了什么栈？ 对后缀表达式求值： 用了什么栈 例2. 队列-循环队列的补充题 已知队尾元素的位置与元素的个数， 求队头元素的位置。 先用实例来分析，然后归结到一般情况。 .frontrear情况一情况一: front=rear-length+1.r

12、earfront情况二情况二: front=rear-length+1+m合并合并: front=(rear-length+1+m)%mfront特殊矩阵的压缩存储特殊矩阵的压缩存储 Arrays and Matrix1D-Array1D-Array1. One-dimensional array 1D-array is a limited sequence composed of n (n0) elements which are of the same data type. For example: Location of the element Loc(ai)=Loc(a0)+i 35

13、27 49 18 60 54 77 83 41 02a 0 1 2 3 4 5 6 7 8 9Size-1i2D-Array2D-Array Two-dimensional arrays are composed of n rows and m columns.a00 a01 a02a0 m-1 a10 a11 a12a1 m-1a20 a21 a22a2 m-1.an-10 an-11an-12.an-1 m-1 Anm=2D-Array2D-ArrayThere are three ways to implement a 2D array 1) mapping the 2D-array t

14、o a 1D-arraya00 a01a0 m-1a10a11 .an-1 m-1a00 a01 a02a0 m-1 a10 a11 a12a1 m-1a20 a21 a22a2 m-1.an-10 an-11an-12.an-1 m-1 Row major order2D-Array2D-Array Location mapping: a) row-major order Loc(aij)=Loc(a00)+i*m+j*l b) column-major order Loc(aij)=Loc(a00)+j*n+i*l2D-Array2D-Array An 3D-Array: int am1m

15、2m3 Location mapping Loc(aijk)=Loc(a000)+i*m2*m3+j*m3+kMatrix Matrix 1.definition: a m*n Matrix is a table with m rows and n columns. m and n are the dimensions of the matrix. For example: a 5*4 matrix7 2 0 90 1 0 56 4 2 08 2 7 31 4 9 612345 1 2 3 4MatrixMatrix 2.Matrix can be implemented with a two

16、 dimensional array : int xmn or Array2Dxmn use x(i,j) to index the matrix element, 1=i=m , 1=j1;Lower triangular. M(i,j)=0 for ij;Symmetric.M(i,j)=M(j,i);Special MatrixSpecial MatrixFor example: 2 0 0 0 2 1 0 0 2 0 0 0 0 1 0 0 3 1 3 0 5 1 0 0 0 0 4 0 0 5 2 7 0 3 1 0 0 0 0 6 0 0 9 0 4 2 7 0(a)Diagona

17、l (b) Tridiagonal Lower Triangular 2 1 3 0 2 4 6 0 0 1 3 8 4 1 9 5 0 0 1 6 6 9 4 7 0 0 0 0 0 5 7 0(d)Upper Triangular (e)SymmetricSpecial MatrixSpecial Matrix1)Lower Triangular a11a21 a22a31 a32 a33an1 an2 annLocation mapping in row-major order: Loc(a(i,j)=Loc(a(1,1)+(1+2+3+i-1)+(j-1)*l =Loc(a(1,1)+

18、(i*(i-1)/2+j-1)*lSpecial MatrixSpecial Matrix2)Upper Triangular a11 a12 a1n a22a2n . annK=1i-1Location mapping in row-major order: Loc(a(i,j)=Loc(a(1,1)+(n-k+1)+j-i*lSpecial MatrixSpecial Matrix3) Tridiagonal a11 a12 a21 a22 a23 a32 a33 a34 an,n-1 an,nLocation mapping in row-major order: Loc(a(i,j)=

19、Loc(a(1,1)+(i-1)*3-1+(j-i+1)*lSparse MatricesSparse Matrices1.Definition: An m*n matrix is said to be sparse if “many” of its elements are zero. number of zero elementsnumber of non-zero elementsSparse MatricesSparse Matrices An example of sparse matrix:0 0 0 2 0 0 0 6 0 0 7 00 0 0 9 0 0 0 4 5 0 0 0

20、Sparse MatricesSparse Matrices 2.Array representation The nonzero entries of an sparse matrix may be mapped into a 1D array in row major order. The structure of each element is: row col value Sparse MatricesSparse Matrices For example : 1 4 2 2 2 6 2 5 7 3 4 9 4 2 4 4 3 5row col valuea:MaxTerms-1012

21、0 0 0 2 0 0 0 6 0 0 7 00 0 0 9 0 0 0 4 5 0 0 0 Sparse Matrices3. Linked Representation 例子：例子： 四行四行 0 0 11 0 0 12 0 0 0 0 0 -4 0 0 0 0 0 0 0 0 五五 列列F 4 5 3TTTTTheadnodeH0 H1 H2 H3 H4 TTTTH0H1H2H3F 0 211F 1 012F 2 1-4习题：习题： 设有一个设有一个n*n的对称矩阵的对称矩阵A，如下图，如下图(a)所示。为了节约存储，可以只所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对

22、角线或对角线以下的元存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组存放于一个一维数组B中，如图中，如图(b)和图和图(c)所示。并称之为对称矩阵所示。并称之为对称矩阵A的压缩存储方式。试问：的压缩存储方式。试问： 1）存放对称矩阵）存放对称矩阵A上三角部分或下三角部分的一维数组上三角部分或下三角部分的一维数组B有多少元有多少元素？素？ 2）若在一维数组）若在一维数组B中从中从0号位置开始存放，则如图号位置开始存放，则如图(a)所示的对称矩所示的对称矩

23、阵中的任一元素阵中的任一元素aij在只存上三角部分的情形下在只存上三角部分的情形下(图图(b)应存于一维数应存于一维数组的什么下标位置？给出计算公式。组的什么下标位置？给出计算公式。 3）若在一维数组）若在一维数组B中从中从0号位置开始存放，则如图号位置开始存放，则如图(a)所示的对称矩所示的对称矩阵中的任一元素阵中的任一元素aij在只存下三角部分的情况下在只存下三角部分的情况下*(图图(c)应存于一维应存于一维数组的什么下标位置？给出计算公式。数组的什么下标位置？给出计算公式。 a11 a12 a1n a11 a12 a1n a11 a21 a22 a2n a22 a2n a21 a22 .

24、 . an1 an1 ann ann an1 an2 ann (a) (b) (c)答案：答案： 1) 1+2+3+n = *(1+n)*n 2) loc(Ai,j ) = loc(B0) + ( n+n-1+.+n-i+2 + j-i ) t = *(2*n-i+2)*(i-1) + j-i ij 3) loc(Ai,j = loc(B0) + (1+2+3+.+i-1+j-1) t = *i*(i-1) + j-1 i=j t = *j*(j-1) + i-1 ij 第4章 树 1.二叉树的定义、性质二叉树的定义、性质 2.满二叉树与完全二叉树的概念满二叉树与完全二叉树的概念 3.二叉树的

25、机内存储：二叉树的机内存储： 数组表示（完全二叉树）、左数组表示（完全二叉树）、左-右拉链表示、右拉链表示、cursor 递归递归 4.先序、中序、后序遍历先序、中序、后序遍历 非递归非递归 层次遍历层次遍历-用到队列用到队列例例1. 第第4章中用非递归实现中序章中用非递归实现中序,后序遍历后序遍历Inorder, Postorder non-recursive algorithm Inorder non-recursive algorithm ABCDEFIHGroottemplate void InOrder(BinaryNode* t) if(t) InOrder(tLeft); vis

26、it(t); InOrder(tRight); Inorder non-recursive algorithmInorder non-recursive algorithm void Inorder(BinaryNode * t) StackBinaryNode* s(10); BinaryNode * p = t; for ( ; ; ) 1) while(p!=NULL) s.push(p); p = p-Left; 2) if (!s.IsEmpty( ) p = s.pop( ); cout element; p = p-Right; else return; 5. 利用先序、中序可唯

27、一构造一棵树利用先序、中序可唯一构造一棵树 先序：先序：ABDCEGFHI 中序：中序：DBAEGCHFI 利用中序、后序可唯一构造一棵树利用中序、后序可唯一构造一棵树 手工画出一棵树手工画出一棵树 利用算法生成一棵树利用算法生成一棵树Create BinaryTree recursive algorithm preorder:ABDCEGFHI inorder: DBAEGCHFI ABCDEFIHGCreate BinaryTree recursive algorithm 1void CreateBT(String pres, ins ; BinaryNode * & t) int inp

28、os; String prestemp, instemp ; if (pres.length( )= =0) t=NULL; else t=new BinaryNode; t-element=pres.ch0; inpos=0; while (ins.chinpos!=t-element) inpos+; prestemp=pres(1,inpos); instemp=ins(0,inpos-1); CreateBT(prestemp, instemp, t-left); prestemp=pres(inpos+1, pres.length( )-1); instemp=ins(inpos+1

29、, pres.length( )-1); CreateBT(prestemp, instemp, t-right); Create BinaryTree recursive algorithm 1Create BinaryTree recursive algorithm 1 public: BinaryTree( string pre, string In ) createBT( pre, In, root ) ; main( ) BinaryTree t1( “ABHFDECKG”, “ HBDFAEKCG” ) ; . *6. 利用广义表表示来构造一棵树利用广义表表示来构造一棵树 7. 应

30、用应用 树的机内表示：树的机内表示： 广义表表示、双亲表示、左子女广义表表示、双亲表示、左子女-右兄弟表示右兄弟表示 1) Take a tree as a binary treeabcdefghijfirstchild data nextsiblingabcdefghij树的存储方式：三种树的存储方式：三种广义表表示：广义表表示：a(b(f,g),c,d(h,i,j),e)双亲表示法双亲表示法左子女左子女右兄弟表示法右兄弟表示法 class TreeNode: T data; TreeNode *firstchild, *nextsibling; class Tree: TreeNode *

31、 root, *current; 树树-二叉树的转换二叉树的转换 Forest Binary tree Forest Binary tree A F H B C D G I J E K 每棵树转为二叉树 A F H B G I C K J D E 把每棵二叉树根用右链相连 A B F C G H D I E R J Binary tree Forest Binary tree Forest A B F C G H D I E R J树与森林的遍历树与森林的遍历 树的遍历：深度优先遍历，广度优先遍历树的遍历：深度优先遍历，广度优先遍历深度优先遍历深度优先遍历 先序次序遍历（先序）先序次序遍历（先

32、序） 访问树的根访问树的根 按先序遍历根的第一棵子树，第二棵子树，按先序遍历根的第一棵子树，第二棵子树， 等。等。 后序次序遍历（后序）后序次序遍历（后序） 按后序遍历根的第一棵子树，第二棵子树，按后序遍历根的第一棵子树，第二棵子树，等等 访问树的根。访问树的根。 A 先根：先根：ABEFCGKLDHIJM与与 B C D 对应的二叉树的先序一致对应的二叉树的先序一致 E F G H I J 后根：后根：EFBKLGCHIMJDA与与 对应的二叉树的中序一致对应的二叉树的中序一致 K L M 广度优先遍历广度优先遍历 A B C D E F G H I J K L M 分层访问：分层访问：AB

33、CDEFGHIJKLM 森林的遍历 深度优先遍历 * 先根次序遍历 访问F的第一棵树的根 按先根遍历第一棵树的子树森林 按先根遍历其它树组成的森林 * 中根次序遍历中根次序遍历 按中根遍历第一棵树的子树森林按中根遍历第一棵树的子树森林 访问访问F的第一棵树的根的第一棵树的根 按中根遍历其它树组成的森林按中根遍历其它树组成的森林 * 后根次序遍历 按后根遍历第一棵树的子树森林 按后根遍历其它树组成的森林 访问F的第一棵树的根二叉树的先序二叉树的先序 二叉树的中序二叉树的后序二叉树的后序 A K B C D I H E F G J 先根：ABEFCGDKIHJ 中根：EFBGCDAIJHK 后根：

34、FEGDCBJHIKA A B K E C I F G D H J 广度优先遍历（层次遍历）补充：补充： 线索树线索树 Thread Tree Thread Tree1.Purpose:2. Thread Tree Representation left Thread Tree and right Thread Tree3.Thread Tree class 1.Purpose: Example： A B C D E F G H J Thread Tree A B C D E F G H J Inorder: DBAEGCHFJThread Treeroot2. 机内如何存储机内如何存储 一个

35、结点增加两个标记域：一个结点增加两个标记域： leftchild leftthread data rightthread rightchild 0 leftchild 指向左子女指向左子女 leftThread = = 1 leftchild 指向前驱（某线性序列）指向前驱（某线性序列） 0 rightchild 指向右子女指向右子女 rightThread = = 1 rightchild 指向后继指向后继 Thread TreeThread Tree left threadTree right threadTree 8. 哈夫曼树 哈夫曼树的构造 哈夫曼编码 扩充的二叉、三叉、.、t叉树

36、15, 3, 14, 2, 6, 9, 16, 17 构造扩充的三叉树。9. 等价类问题 PPT第8章第第4.14.1章：二叉搜索树章：二叉搜索树 1.二叉搜索树的概念二叉搜索树的概念 2.带索引的二叉搜索树的概念带索引的二叉搜索树的概念 3. AVL树树-平衡的二叉搜索树平衡的二叉搜索树 4. B-树树 1.二叉搜索树的概念二叉搜索树的概念 二叉搜索树二叉搜索树 Example:45125390781006124373 left element right二叉搜索树二叉搜索树主要操作：主要操作： 查找、插入、删除查找、插入、删除15122410811181617202923213230353

37、3 2. 2.带索引的二叉搜索树的概念带索引的二叉搜索树的概念An indexed binary search tree is derived from an ordinary binary search tree by adding the field leftSize to each tree node.Value in Leftsize field=number of the elements in the nodes left subtree +1leftSize left element right Example: 4 20 2 15 1 25 1 18 1 12 1 30 例子：

38、例子： 写一递归函数实现在带索引的二叉搜索树（写一递归函数实现在带索引的二叉搜索树（IndexBST)中查找第中查找第k个小个小的元素。的元素。public Comparable findK( BinaryNode root, int k)if( root=null) return null;/空空 if( kroot. leftSize) /在右子树在右子树findK( root. right, k-root. leftSize);/注意减去注意减去 else return root.element;3.AVL树树-平衡的二叉搜索树平衡的二叉搜索树 Definition of an AVL

39、tree: (1) is a binary search tree (2) Every node satisfies |hL-hR|=1 where hL and hR are the heights of TL(left subtree) and TR(right subtree),respectively. 例子例子1345681011121518202224+10-10-1AVL TreeAVL TreeHeight of an tree: the longest path from the root to each leaf nodeBalance factor bf(x) of a

40、node x : height of right subtree of x height of left subtree of x Left data Right balance(height) Each node: AVL Tree The height of an AVL tree with n elements is O(log2 n), so an n-element AVL search tree can be searched in O(log2 n) time. AVL Tree 插入插入 左外侧，左外侧， 右外侧右外侧-一次旋转一次旋转 左内侧，右内侧左内侧，右内侧-二次旋转二

41、次旋转 AVL树的插入树的插入: 1. 首先要正确地插入首先要正确地插入 2. 找到有可能发生的最小不平衡子树找到有可能发生的最小不平衡子树 3. 判别插入在不平衡子树的外侧还是内侧判别插入在不平衡子树的外侧还是内侧 4. 根据根据3的判别结果的判别结果,再进行单旋还是双旋再进行单旋还是双旋 从空的从空的AVL树建树的算法。一个例子树建树的算法。一个例子 ： 7个关键码发生四种转动个关键码发生四种转动 A， Z， C， W， D， X， YAAZAZCW右双旋转右双旋转AAZZCC右内右内ADZCW左外左外右单旋转右单旋转ACDZW左单旋转左单旋转右外AACCDDZZXXWWY左双旋转左双旋转

42、左内AACYCDDZZXXWW AVL树的删除： 方法 ： 与二叉搜索树的删除方法一样。 假设被删除结点为W, 它的中序后继为X, 则用X代替W,并 删除X. 所不同的是:删除X后,以X为根的子树高度减1,这一高度 变化可能影响到从X到根结点上每个结点的平衡因子,因此要进 行一系列调整。WX AVL树的算法分析树的算法分析 具有具有n个结点的平衡二叉树（个结点的平衡二叉树（AVL），进行一次插入或删除），进行一次插入或删除的时间最坏情况的时间最坏情况O（log2 n) 证明：实际上要考虑证明：实际上要考虑n个结点的平衡二叉树的最大高度个结点的平衡二叉树的最大高度 (3/2) log2 (n +

43、 1 ) 设设T h 为一棵高度为为一棵高度为h，且结点个数最少的平衡二叉树。，且结点个数最少的平衡二叉树。h-2h-1h假设右子树高度为假设右子树高度为h-1因结点个数最少因结点个数最少,左子树高度左子树高度只能是只能是h-2这两棵左子树这两棵左子树,右子树高度分别右子树高度分别为为h-2, h-1,也一定是结点数最少的也一定是结点数最少的:n = 7h = 3T 3h = 1T 1n = 2h =2T 2n = 4 h = 4T 4n = 12h = 0T 0n = 1 以上五棵平衡二叉树，又称为以上五棵平衡二叉树，又称为Fibonacci树。树。 也可以这样说一棵高度为也可以这样说一棵高

44、度为h的树，其右子树高度为的树，其右子树高度为h-1的的Fibonacci树，左子树是高度为树，左子树是高度为h-2的的Fibonacci树，即树，即T h - 2T h - 1假设假设N h表示一棵高度为表示一棵高度为h的的Fibonacci树的结点个数，则树的结点个数，则 N h =N h - 1 + N h - 2 + 1 N 0 = 1 , N 1 = 2 , N 2 = 4 , N 3 = 7 , N4 = 12 , . . .N 0 + 1 =2 , N 1 + 1 = 3 , N2 + 1 = 5 , N 3 + 1 = 8 , N4 + 1 = 13 , . . . N h +

45、 1满足费波那契数的定义，并且满足费波那契数的定义，并且N h+ 1= F h + 3 f 0 f 1 f 2 f 3 f 4 f 5 f 6 . . . 0 1 1 2 3 5 8 . . .费波那契数费波那契数F i 满足下列公式满足下列公式 F i = ( ) - ( ) 15 1- 5 2iii | | =2Level 2 =2m/2Level 3 =2m/22Level h = 2m/2h-1B-treesB-trees n+1= 2m/2h-1 , (n+1)/2= m/2h-1 , h-1=log m/2 (n+1)/2, logm(n+1)=h=1+logm/2 (n+1)/2

46、In the case that each node has m children Example: n=2*106, m=199 then h=1+log100(102)3=4 search one from 200 branchesB-treesB-trees2) Inserting into a B-Tree always happen at one level above the external nodesB-treesB-trees Case 1:number of children in the nodem, insert into the node as ordered 10

47、802 4 6 20 30 40 50 60 70 82 84 86 88A B-Tree of order 7Insert 3B-treesB-trees 10 802 3 4 6 20 30 40 50 60 70 82 84 86 88B-treesB-treesCase 2.Insert into a node with m children (also called a full node), like insert 25 into the B-Tree in the last example, the full node is split into two nodes. A new

48、 pointer will be added to the parent of the full node .Because km/2 is inserted into parent node, it may cause new split. If the root is split,the height of the tree will increased by 1. B-treesB-trees Example: Insert 4430 802050 6090102535 40557082 8595A B-Tree of order 3B-treesB-trees 802060901025

49、 44557082 859535403050Algorithm analyses: If the insert operation causes s node to split, the number of disk access is h (to read in the nodes on the search path) +2s (to write out the two split parts of each node that is split) +1 (to write the new node).B-treesB-trees3)deletion from a B-Tree Two c

50、ases: The element to be deleted is in a node whose children are external nodes(i.e.the element is in a leaf) The element is to be deleted from a nonleaf.B-treesB-treesa) the element to be deleted is in a leaf Case1: delete it directly if it is in a node which has more than m/2 children Case2: if it

51、is in a node which has m/2children, after deletion ,the number of children(m/2-1) is not suitable for a B-Tree borrow an element from the its nearest sibling if can, and do some adjusting.B-treesB-trees Example: delete 379 283 353 401307 313 331 347367 379 389283 347 401307 313 331353 367 389A B-TRE

52、E of order 7B-treesB-trees If nearest left or right sibling both only has m/2 children, then merge themAfter deletion ,merge the node and its sibling with the element between them in the parent into a single nodeMaybe cause new merge in parent nodesThe height of the tree will deceased by one if root

53、 is merged.B-treesB-trees Example:a B-Tree of order 7 ,delete 431283 353 401367 379 389419 431 439B-treesB-treesb)delete a key in a node in the above levelDelete itReplace it with the smallest key in the right subtree or the largest key in the left subtreeBecause delete a key in the leaf node , do t

54、he adjust mentioned in a)B-treesB-trees Example:Delete 80, then replace it with 82 or 70, delete 82 or 70 at last30 802050 6085102535 4055708290A B-TREE of order 3B-treeB-tree例子：例子：1. 分别分别 delete 50 ,40 in the following 3阶阶B-树树.503060 802040557095B-treeB-tree2. 分别画出插入分别画出插入65, 15, 40, 30后的后的3阶阶B-树。树

55、。 554580 90 25 355060 708595第5章：散列 1.散列函数的选择 2.解决冲突的方法 开地址法：线性探查法 平方探查法 二次散列 链地址法 Hash Function1。散列函数的选择。散列函数的选择 2. solve a collision2. solve a collision1. Open Addressing 1) linear Probing If hash(key)=d and the bucket is already occupied then we will examine successive buckets d+1, d+2,m-1, 0, 1,

56、2, d-1, in the arraysolve a collisionsolve a collision example keys : Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly hash( key ) = ord( x ) ord(A) x为取为取key第一个字母在字母表中的位置。例如：第一个字母在字母表中的位置。例如： hash(Attlee) = 0 H( Burke ) = 1 , H( Ekers ) = 4 , H( Broad ) = 1, H( Blum ) = 1, H( Attlee ) = 0 , H

57、( Hecht ) = 7 , H(Alton ) = 0 , H( Ederly ) = 4, 设散列表长设散列表长 m = 26 ( 025 ) 分析比较次数：分析比较次数： 搜索成功的平均搜索长度搜索成功的平均搜索长度 1/8( 1 + 1 + 2 + 3 + 1 + 1 + 6 + 3 ) = 18/8 * 搜索不成功的平均搜索长度搜索不成功的平均搜索长度 1/26( 9+8+7+6+5+4+3+2+ 1+1+1+.+1) = (9+8+7+6+5+4+3+2+ 18) = 62/26solve a collisionsolve a collision 2) Quadratic pro

58、bing If hash(k)=d and the bucket is already occupied then we will examine successive buckets d+1, d+22, d+33, in the array example : ( 89,18, 49, 58, 69 ) hash( k ) = k % 10; 0 1 2 3 4 5 6 7 8 9 49 58 69 18 89 2 3 3 1 1 ASVsucc=(1+1+2+3+3)/5solve a collisionsolve a collision 3) Double Hashing If has

59、h1(k)=d and the bucket is already occupied then we will counting hash2(k) =c, examine successive buckets d+c, d+2c, d+3c, in the array example: hash1(k) = k % 10; hash2(k) = R (k % R ); 其中 R 1 & parebleTo( array hole / 2 ) 0; hole /= 2 ) array hole = array hole / 2 ; array hole = x; Heaps public Com

60、parable deleteMin( ) if( isEmpty( ) ) return null; Comparable minItem = findMin( ); array 1 = array currentSize- ; percolateDown( 1 ); return minItem; Heaps private void percolateDown( int hole ) int child; Comparable tmp = array hole ; for( ; hole *2 = currentSize; hole = child ) child = hole * 2;