移动微网站开发,平面设计主要做什么工作,新手网络设计师人生规划,二维码网站建设源码二叉搜索树
二叉查找树#xff0c;也称为二叉搜索树、有序二叉树或排序二叉树#xff0c;是指一棵空树或者具有下列性质的二叉树#xff1a;
若任意节点的左子树不空#xff0c;则左子树上所有节点的值均小于它的根节点的值#xff1b;若任意节点的右子树不空#xff0…二叉搜索树
二叉查找树也称为二叉搜索树、有序二叉树或排序二叉树是指一棵空树或者具有下列性质的二叉树
若任意节点的左子树不空则左子树上所有节点的值均小于它的根节点的值若任意节点的右子树不空则右子树上所有节点的值均大于它的根节点的值任意节点的左、右子树也分别为二叉搜索树 如果二叉查找树是平衡的则查找、插入的时间复杂度为O(logn)。如果二叉查找树完全不平衡则时间复杂度为O(n)。 中序遍历二叉搜索树可以获得关键字的递增序列 二叉搜索树的查找算法
在二叉查找树b中查找x的过程为
若b是空树则搜索失败否则若x等于b的根节点的值则查找成功否则若x小于b的根节点的值则搜索左子树否则查找右子树。
二叉搜索树的节点插入算法
向一个二叉搜索树b中插入一个节点s的算法过程为
若b是空树则将s所指节点作为根节点插入否则若s-data等于b的根节点的值则返回否则若s-data小于b的根节点的值则把s所指节点插入到左子树中否则把s所指节点插入到右子树中。新插入节点总是叶子节点
二叉搜索树的节点删除算法
若待删除节点*p为叶子节点则直接删除即可若待删除节点*p只有左子树PL或右子树PR则当*p是左子树右子树时直接令PL或PR成为其父节点*f的左子树右子树若待删除节点*p的左子树或右子树均不为空 其一是令*p的左子树为*f的左/右依*p是*f的左子树还是右子树而定子树*s为*p左子树的最右下的结点而*p的右子树为*s的右子树其二是令*p的直接前驱或直接后继替代*p然后再从二叉查找树中删去它的直接前驱或直接后继。
AVL树 AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基和叶夫根尼·兰迪斯他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。 AVL树是一种自平衡二叉搜索树在AVL树中任一节点对应的两棵子树的最大高度差为1查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)增加和删除元素的操作则可能需要借由一次或多次树旋转以实现树的重新平衡。
平衡因子节点的平衡因子是它的左子树的高度减去它的右子树的高度有时相反。
旋转操作
右旋 左旋
需要平衡的四种情况
B-树
参考文章 B-树就是B树中间的横线并不是减号 为什么数据库索引使用B-树而不是二叉搜索树 考虑磁盘IO的问题数据库索引是存储在磁盘上的当数据量比较大的时候索引的大小可能有几个G甚至更多当我们利用索引查询的时候只能逐一加载每一个磁盘页这里的磁盘页对应索引树的节点最坏情况下磁盘IO次数等于索引树的高度所以需要把原本“瘦高”的树结构变得“矮胖”这就是B-树的特征之一。 B树是一种多路平衡查找树每个节点最多可以包含k个孩子k为B树的阶k的选择取决于磁盘页大小 一个m阶的B树具有如下几个特征
若根节点不是叶子节点则至少有两个子节点每个中间节点都包含 k-1 个元素和 k 个孩子其中 ⌈m/2⌉ k m每个叶子节点都包含 k-1个元素其中⌈m/2⌉ k m所有的叶子节点都位于同一层每个节点中的元素从小到大排列节点当中k-1个元素刚好是k个孩子包含的元素的值域分划。
B-树主要应用于文件系统以及部分数据库索引比如著名的非关系型数据库MongoDB大部分关系型数据库比如Mysql则使用B树作为索引。
B树的插入操作
参考博客 插入操作是指插入一条记录即key, value的键值对。如果B树中已存在需要插入的键值对则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。
1根据要插入的key的值找到叶子结点并插入。
2判断当前结点key的个数是否小于等于m-1若满足则结束否则进行第3步。
3以结点中间的key为中心分裂成左右两部分然后将这个中间的key插入到父结点中这个key的左子树指向分裂后的左半部分这个key的右子支指向分裂后的右半部分然后将当前结点指向父结点继续进行第3步。 当阶数m为偶数时需要分裂时就不存在排序恰好在中间的key那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。
以5阶B树为例介绍B树的插入操作 在5阶B树中结点最多有4个key最少有2个key。
在空树中插入39 此时根结点就一个key此时根结点也是叶子结点继续插入22、97、41 根结点此时有4个key继续插入53 插入后超过了最大允许的关键字个数4所以以key值为41为中心进行分裂结果如下图所示分裂后当前结点指针指向父结点满足B树条件插入操作结束。当阶数m为偶数时需要分裂时就不存在排序恰好在中间的key那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。 依次插入13、21、40 同样会造成分裂结果如下图所示。 依次插入30、27、 33 36、35、34 24、29 插入 30、27、 33 插入 36、35、34 插入24、29 插入26 当前结点需要以27为中心分裂并向父结点进位27然后当前结点指向父结点结果如下图所示。 进位后导致当前结点即根结点也需要分裂分裂的结果如下图所示。 分裂后当前结点指向新的根此时无需调整。最后再依次插入key为 17、28、31、32 的记录
B树的删除操作
删除操作是指根据key删除记录如果B树中的记录中不存对应key的记录则删除失败。
如果当前需要删除的key位于非叶子结点上则用后继key这里的后继key均指后继记录的意思覆盖要删除的key然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步该结点key个数大于等于Math.ceil(m/2)-1结束删除操作否则执行第3步。如果兄弟结点key个数大于Math.ceil(m/2)-1则父结点中的key下移到该结点兄弟结点中的一个key上移删除操作结束。 否则将父结点中的key下移与当前结点及它的兄弟结点中的key合并形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针指向这个新结点。然后当前结点的指针指向父结点重复上第2步。 有些结点它可能即有左兄弟又有右兄弟那么我们任意选择一个兄弟结点进行操作即可。
以5阶B树为例介绍B树的删除操作 5阶B树中结点最多有4个key,最少有2个key
原始状态 在上面的B树中删除21删除后结点中的关键字个数仍然大于等2所以删除结束 在上述情况下接着删除27。从上图可知27位于非叶子结点中所以用27的后继替换它。从图中可以看出27的后继为28我们用28替换27然后在28原27的右孩子结点中删除28。删除后的结果如下图所示。 删除后发现当前叶子结点的记录的个数小于2而它的兄弟结点中有3个记录当前结点还有一个右兄弟选择右兄弟就会出现合并结点的情况不论选哪一个都行只是最后B树的形态会不一样而已我们可以从兄弟结点中借取一个key。所以父结点中的28下移兄弟结点中的26上移,删除结束。结果如下图所示。 在上述情况下接着删除32结果如下图。 当删除后当前结点中只有一个key而兄弟结点中也仅有2个key。所以只能让父结点中的30下移和这个两个孩子结点中的key合并成为一个新的结点当前结点的指针指向父结点。结果如下图所示。 当前结点key的个数满足条件故删除结束。上述情况下我们接着删除key为40的记录删除后结果如下图所示。 同理当前结点的记录数小于2兄弟结点中没有多余key所以父结点中的key下移和兄弟这里我们选择左兄弟选择右兄弟也可以结点合并合并后的指向当前结点的指针就指向了父结点。 同理对于当前结点而言只能继续合并了最后结果如下所示。 合并后结点当前结点满足条件删除结束。
B树
参考文章 B树是B-树的一种变体有着比B-树更高的查询性能 一个m阶的B树具有如下几个特征
有k个子树的中间节点包含有k个元素B树中是k-1个元素每个元素不保存数据只用来索引所有数据都保存在叶子节点。所有的叶子结点中包含了全部元素的信息及指向含这些元素记录的指针且叶子结点本身依关键字的大小自小而大顺序链接。所有的中间节点元素都同时存在于子节点在子节点元素中是最大或最小的元素 在B-树中无论是中间节点还是叶子节点都有卫星数据牵引元素所指向的数据记录而在B树中只有叶子节点带有卫星数据其余中间节点仅仅是索引没有任何数据关联。
B树的优点 单行查询 在单元素查询的时候B树会自顶向下逐层查找节点最终找到匹配的叶子节点。步骤与B-树类似但是B树的中间节点没有卫星数据所以同样大小的磁盘页可以容纳更多的节点元素在数据量相同的情况下B树比B-树更加“矮胖”查询IO的次数也更少。其次B树的查询必须最终查找到叶子节点而B-树只要找到匹配元素即可无论匹配元素处于中间节点还是叶子节点因此B-树的查找性能不稳定最好情况是根节点最坏情况是叶子节点而B树的每次查找都是稳定的。 范围查询 B-树的范围查询只能依靠繁琐的中序遍历B树的范围查询只需要在链表上做遍历即可。
总结
单一节点存储更多的元素使得查询的IO次数更少。所有查询都要查找到叶子节点查询性能稳定。所有叶子节点形成有序链表便于范围查询。
红黑树
