数据结构与算法

1、数据结构与算法B树相关MySQL DBA 彭立勋树的基本概念查找树的基本操作二叉搜索树平衡二叉树平衡树算法(AVL/Treep/Splay)红黑树线段树B树原型B+树将要介绍什么？树的基本概念树是n(n=0)个结点的有限集。在任意一棵非空树中：(1)有且仅有一个特定的称为根的结点；(2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,.Tm,其中每一个集合本身又是一棵树,并且称为根的子树.补充：从图来定义，树是一个无环的连通无向图。查找树的基本操作（1）SEARCH(S,k)：返回有限集S中一个关键字为k的元素的指针x。即keyx=k。INSERT(S,x)：将由x指向的元素添

2、加到S。DELETE(S,x)：将由x指向的元素从S中删除。MINIMUM(S)：返回全序集S中具有最小关键字的元素指针。MAXIMUM(S)：返回全序集S中具有最大关键字的元素指针。查找树的基本操作（2）SUCCESSOR(S,x)（后继）：返回全序集S中比x大的下一个元素的指针。PREDECESSOR(S,x)（前驱）：返回全序集S中比x小的上一个元素的指针。二叉查找树定义：任取一颗子树，根节点都比左节点大（小），比右结点小（大）。递归定义二叉查找树搜索二叉查找树（复杂度O(LogN)）TREE-SEARCH (x, k)1 if x= NIL or k = keyx2 then retu

3、rn x3 if k keyx4 then return TREE-SEARCH(leftx, k)5 else return TREE-SEARCH(rightx, k)二叉查找树搜索的例子二叉查找树获取最大/最小关键字元素（复杂度O(LogN)）TREE-MINIMUM (x) /*TREE-MAXIMUM(x)*/1 while leftx NIL /* while rightx NIL*/2 do x leftx /* do x rightx*/3 return x二叉查找树获取前驱/后继（复杂度O(LogN)）TREE-SUCCESSOR(x)1 if rightx NIL2 the

4、n return TREE-MINIMUM (rightx)3 y px4 while y NIL and x = righty5 do x y6 y py7 return y二叉查找树插入元素（复杂度O(LogN)）TREE-INSERT(T, z)1 y NIL2 x rootT3 while x NIL4 do y x5 if keyz keyx6 then x leftx7 else x rightx8 pz y9 if y = NIL10 then rootT z Tree T was empty11 else if keyz O(N)平衡二叉树平衡二叉树本质上是一颗二叉查找树，但是

5、它是严格平衡的，即任一结点的左右子树高度差不超过1.平衡二叉树为什么要平衡随机生成的二叉查找树经过多次插入/删除操作之后平衡二叉树为什么要任一结点的左右子树高度差不超过1而不只是根节点平衡树算法(AVL)AVL树，严格平衡的二叉树旋转算法平衡树算法(AVL)单旋转（左旋/右旋）平衡树算法(AVL)双旋转（左右旋，右左旋）平衡树算法(其他)Splay：伸展树，也是利用旋转的方法，但是只做单旋转。Treep：为每个节点附加一个随机的优先级，规定优先级必须满足堆的性质的前提下对关键字执行基本二叉查找树的算法。红黑树红黑树是一种二叉查找树，但在每个节点上增加一个存储位表示结点的颜色，可以使RED/BLACK。通过对任何一条从根节点到叶子的路径上各个着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。线段树使用区间作为节点构成的查找树适用于区间统计计算和动态统计B树原型B树与红黑树的不同在于，B树的节点可以有许多子节点，所以B树的分支因子可能很大。B树原型分裂操作：当节点不能再增加元素时，节点会分裂成两个节点插入操作删除操作B+树在叶子节点上添加指向下一个节点的指针非叶子节点不保存实际关键字信息数据库