滨州哪里有做网站的,选服务好的佛山网站建设,博客网站登录入口,网站主题和风格数组和链表是常用的数据结构#xff0c;数组虽然查找快#xff08;有序数组可以通过二分法查找#xff09;#xff0c;但是插入和删除是比较慢的#xff1b;而链表#xff0c;插入和删除很快#xff08;只需要改变一些引用值#xff09;#xff0c;但是查找就很慢数组虽然查找快有序数组可以通过二分法查找但是插入和删除是比较慢的而链表插入和删除很快只需要改变一些引用值但是查找就很慢需要从头开始遍历 那么有没有一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点呢那就是接下来要介绍的——树。
1、二叉查找树
特性
1、左子树上所有节点的值均小于它的根节点的值2、右子树上所有节点的值均大于它的根节点的值3、左、右子树也分别为二叉排序树。 但是一个不好会形成链表结构比如一个有序数组形成的二叉树2、平衡二叉查找树
特性
1、在二叉树的基础上要求两个子树的高度差不能超过12、每次增删都会通过一次或多次旋转来平衡二叉树
调整平衡的基本思想
当在二叉排序树中插入一个节点时首先检查是否因插入而破坏了平衡若破坏则找出其中的最小不平衡二叉树在保持二叉排序树特性的情况下调整最小不平衡子树中节点之间的关系以达到新的平衡。 所谓最小不平衡子树指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
先插入指定节点记录下当前节点的信息LHEH或者RH。
若左子树高LH查看其左子树根节点的信息若是LH则一次右旋若是RH则一次左旋一次右旋若右子树高RH查看右子树根节点的信息若是RH则一次左旋若是LH则一次右旋一次左旋调整改变的节点信息
虽然平衡树解决了二叉查找树退化为近似链表的缺点能够把查找时间控制在 O(logn)不过却不是最佳的因为平衡树要求每个节点的左子树和右子树的高度差至多等于1这个要求实在是太严了导致每次进行插入/删除节点的时候几乎都会破坏平衡树的第二个规则进而我们都需要通过左旋和右旋来进行调整使之再次成为一颗符合要求的平衡树且随着树的高度的增加动态插入和删除的代价也越来越大为了解决优化插入和删除性能红黑树出现了。
显然如果在那种插入、删除很频繁的场景中平衡树需要频繁着进行调整这会使平衡树的性能大打折扣为了解决这个问题于是有了红黑树红黑树具有如下特点
3、红黑树
特性
1、根节点是黑色2、每个节点或者是黑色或者是红色3、每个叶子节点是黑色。 [注意这里叶子节点是指为空的叶子节点4、如果一个节点是红色的则它的子节点必须是黑色的也就是说一个红节点的父节点只能是黑色5、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点也就是说确保没有一条路径会比其他路径长出俩倍
红黑树Red Black Tree 是一种自平衡二叉查找树 红黑树和AVL树类似都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡从而获得较高的查找性能。 二叉平衡树的严格平衡策略以牺牲建立查找结构(插入删除操作)的代价换来了稳定的O(logN) 的查找时间复杂度 它虽然是复杂的但它的最坏情况运行时间也是非常良好的并且在实践中是高效的 它可以在O(log n)时间内做查找插入和删除这里的n 是树中元素的数目。
红黑树的操作代价 查找代价由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)可以说明红黑树虽然不像平衡二叉查找树一样是严格平衡的但平衡性能还是要比二叉查找树要好。其查找代价基本维持在O(logN)左右但在最差情况下(最长路径是最短路径的2倍少1)比平衡二叉查找树要略逊色一点。 插入代价RBT插入结点时需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转这一点和平衡二叉查找树的插入操作一样。虽然变色操作需要O(logN)但是变色操作十分简单代价很小。 删除代价红黑树的删除操作代价要比平衡二叉查找树要好的多删除一个结点最多只需要3次旋转操作。
RBT 效率总结 : 查找效率最好情况下时间复杂度为O(logN)但在最坏情况下比平衡二叉查找树要差一些但也远远好于二叉查找树。 插入和删除操作改变树的平衡性的概率要远远小于AVLRBT不是高度平衡的。因此需要的旋转操作的可能性要小而且一旦需要旋转插入一个结点最多只需要旋转2次删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)但是实际上这种操作由于简单所需要的代价很小。
红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是平衡二叉查找树所不具备的。
调整平衡的基本思想
变色为了重新符合红黑树的规则尝试把红色节点变为黑色或者把黑色节点变为红色。左旋转逆时针旋转红黑树的两个节点使得父节点被自己的右孩子取代而自己成为自己的左孩子。说起来很怪异大家看下图右旋转顺时针旋转红黑树的两个节点使得父节点被自己的左孩子取代而自己成为自己的右孩子。大家看下图场景HashMap TreeSet TreeMap
4、 B树
设计缘由
数据库索引是存储在磁盘上的当数据量比较大的时候索引的大小可能有十几个G甚至更多。当我们利用索引查询的时候能把整个索引全部加载到内存吗显然不可能能做的只有逐一加载每一个磁盘页这里的磁盘页对应着索引树的节点。
如果我们利用二叉查找树作为索引结构那么最坏每个节点数据在不同磁盘页上的情况下磁盘IO次数等于索引树的高度。 所以为了减少磁盘IO次数我们就需要把原本“瘦高”的树结构变得“矮胖”节点数变少了。这就是B树的特征之一
B树是一种多路平衡查找树它的每一个节点最多包含m个孩子m被称为B树的阶m的大小取决于磁盘页的大小。——一个节点最多包含一个磁盘页的数据
也就是说当B树变得矮胖以后每个节点可以包含多个数据数据量大小由磁盘页的大小决定同样的数据B树比二叉树/红黑树节点少。所以B树在查询时磁盘IO次数变少了从而可以提升查找性能。 特征
一个m阶的B树具有如下几个特征
1.根结点至少有两个子女。2.每个中间节点都包含k-1个元素和k个孩子其中 m/2 k m3.每一个叶子节点都包含k-1个元素其中 m/2 k m4.所有的叶子结点都位于同一层。5.每个节点中的元素从小到大排列节点当中k-1个元素正好是k个孩子包含的元素的值域分划
场景
B树主要应用于文件系统以及部分数据库索引比如著名的非关系型数据MongoDB。 而大部分关系型数据库比如mysql则使用B树作为索引
5、 B树
B树是B树的一种变体但是又有所不同
特征
一个m阶的B树具有如下几个特征 1.有k个子树的中间节点包含有k个元素B树中是k-1个元素每个元素不保存数据只用来索引所有数据都保存在叶子节点。 2.所有的叶子结点中包含了全部元素的信息及指向含这些元素记录的指针且叶子结点本身依关键字的大小自小而大顺序链接。 3.所有的中间节点元素都同时存在于子节点在子节点元素中是最大或最小元素。 这里特别要注意有两点 其一每个父节点的元素都出现在子节点中是子节点的最大或最小元素因此所有叶子节点包含了全量元素信息 其二每个叶子节点都带有指向下一个节点的指针形成了一个有序链表 其三只有叶子节点带有卫星数据其余中间节点仅仅是索引没有任何数据关联如下图所谓卫星数据指的是索引元素所指向的数据记录比如数据库中的某一行在B树种无论中间节点还是叶子节点都带有卫星数据。 设计优势
B树的好处主要体现在查询性能上由于B树的中间节点没有卫星数据所以同样大小的磁盘页可以容纳更多的节点元素这就意味着一次性加载到内存中的节点元素更多从而使得查询时IO次数也更少。(举个简单的例子一个磁盘页可以加载B树的100个节点元素但是可以加载B树的1000个节点元素那么对于查找999这个数来说B数需要10次IOB数只需要1次IO)
B树相对B树的优点 IO一次读数据是从磁盘上读的磁盘容量是固定的取数据量大小是固定的非叶子节点不存储数据节点小磁盘IO次数就少。 B树查询性能稳定因为B树的查询必须最终查找到叶子节点 而B树只要找到匹配元素即可无论匹配元素处于中间节点还是叶子节点。所以B树的查询性能并不稳定最好情况是只查根节点最坏情况是查到叶子节点 B树的所有Data域在叶子节点一般来说都会进行一个优化就是将所有的叶子节点用指针串联起来可以认为是链表遍历叶子节点就能获取全部数据这样就能进行区间访问了。 B树做范围查询只能繁琐的遍历但是B树只需要查到查找到范围下限以后遍历叶子节点有序链表就可以了。
综合起来B树比B树的优势有三个1、IO次数更少2、查询性能更佳3、范围查询简便
场景Mysql索引
6、红黑树 VS B树
红黑树的深度比B树大当数据量小时可以把数据完全放到内存中红黑树的时间复杂度比B树低不用每次都查到叶子节点如linux中进程的调度用的是红黑树Java中HashMap、TreeMap、TreeSet都在内存中操作也都是用红黑树实现
但是当数据量大时不能一次性把数据放到内存时红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁进而导致效率低下而B树因其读磁盘次数少具有更快的速度。
