数据结构与算法.ppt

数据结构与算法——B树相关MySQLDBA彭立勋羔爆屁威平枷顾留醋回窿淬背沛锅绞恕珊伐逸艘侵焰菏央阀瑶背评陈掐蛙数据结构与算法数据结构与算法树的基本概念查找树的基本操作二叉搜索树平衡二叉树平衡树算法(AVL/Treep/Splay)红黑树线段树B树原型B+树将要介绍什么?煮卸斜苔誊憎涝医诈铀凸肉炙恬窒斥嘻躯栅舌超匠超息码撂臣鱼含郝吗炊数据结构与算法数据结构与算法树的基本概念树是n(n>=0)个结点的有限集。在任意一棵非空树中:(1)有且仅有一个特定的称为根的结点;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...Tm,其中每一个集合本身又是一棵树,:从图来定义,树是一个无环的连通无向图。糯妒拄爵露沮匀穷梳堪槽韧掺隧位阜矮属致沧烙膀栈像氖剃满恩揉咖分幢数据结构与算法数据结构与算法查找树的基本操作(1)SEARCH(S,k):返回有限集S中一个关键字为k的元素的指针x。即key[x]=k。INSERT(S,x):将由x指向的元素添加到S。DELETE(S,x):将由x指向的元素从S中删除。MINIMUM(S):返回全序集S中具有最小关键字的元素指针。MAXIMUM(S):返回全序集S中具有最大关键字的元素指针。艾琼毋医呻鸵儒抨答豢粕惜宙唤座狂里异它稠瞧多港俭促至混蓉揭尧勒架数据结构与算法数据结构与算法查找树的基本操作(2)ESSOR(S,x)(后继):返回全序集S中比x大的下一个元素的指针。PREDECESSOR(S,x)(前驱):返回全序集S中比x小的上一个元素的指针。吏搓隅超瓮捅华依寥纺饱期构炉揣坤逞壕难茁娘庆采挤恃渠岿锹夹期圾班数据结构与算法数据结构与算法二叉查找树定义:任取一颗子树,根节点都比左节点大(小),比右结点小(大)。递归定义层宠言痒离页麻烹沾泌们虱睁住帜持仰兔秸垃诉亲财栽骤狮疗愤柄养蓬证数据结构与算法数据结构与算法二叉查找树搜索二叉查找树(复杂度O(LogN))TREE-SEARCH(x,k)1ifx=NILork=key[x]2thenreturnx3ifk<key[x]4thenreturnTREE-SEARCH(left[x],k)5elsereturnTREE-SEARCH(right[x],k)探居安屡新灶效灿笆渤獭凳台寂屯球淘议泵砰蓟花旅妖蛹摘舞笺而轩咬士数据结构与算法数据结构与算法二叉查找树搜索的例子夕春方能曰由胎致估纳磐锄拱仟谱痈生既褐县辖肺音赚痔逃贫暇职堡糖怖数据结构与算法数据结构与算法二叉查找树获取最大/最小关键字元素(复杂度O(LogN))TREE-MINIMUM(x)/*TREE-MAXIMUM(x)*/1whileleft[x]≠NIL/*whileright[x]≠NIL*/2dox←left[x]/*dox←right[x]*/3returnx寇虚驮赤碰筛悔忱吠旦勇似服漏溺优柜扯车咳荆宗且傲充叶稽拢制晴场鹅数据结构与算法数据结构与算法二叉查找树获取前驱/后继(复杂度O(LogN))TREE-ESSOR(x)1ifright[x]≠NIL2thenreturnTREE-MINIMUM(right[x])3y←p[x]4whiley≠NILandx=right[y]5dox←y6y←p[y]7returny惫吧酿国炽宛兢修肢办舆锤咖烩邵铰硬瓤呢逊迈抵冠述蛆宵奥悦堕彼圃纪数据结构与算法数据结构与算法