网站维护服务,简述网站的制作步骤,如何看网站做没做推广,辽宁网站建站系统哪家好二叉树
一棵二叉树是结点的一个有限集合#xff0c;该集合或者为空#xff0c;或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 二叉树的特点#xff1a;
每个结点最多有两棵子树#xff0c;即二叉树不存在度大于2的结点。二叉树的子树有左右之分#xf…二叉树
一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 二叉树的特点
每个结点最多有两棵子树即二叉树不存在度大于2的结点。二叉树的子树有左右之分其子树的次序不能颠倒。
满二叉树
满二叉树二叉树的所有叶子节点都在最后一层且总数n2^(n-1)。 完全二叉树
完全二叉树数据从上到下从左到右依次进行平铺。
有序二叉树
有序二叉树左子树上的值小于根节点的值右子树上的值大于根节点的值。
有序二叉树的遍历
深度优先遍历
1、先序/前序遍历根节点----》左子树-----》右子树
2、中序遍历左子树----》根节点-----》右子树
3、后序遍历左子树----》右子树-----》根节点
有序二叉树不稳定O(logn) - O(n)
有序二叉树不稳定是因为没有任何限制以至于在某些特殊的情况下会形成链表。
平衡二叉树
平衡二叉树是在有序二叉树的基础之上而来的就是为了解决有序二叉树不稳定的问题。要求一个节点的左右子树高度差的绝对值不能超过1可以等于1。
如果插入的数据之后使得一个节点的左右子树高度差的绝对值超过了1就要通过LL、RR、LR、RL四种旋转策略来保证平衡二叉树。
四种旋转策略
LL旋转策略 实例 RR旋转策略 实例 LR旋转策略 实例 RL旋转策略 实例 在实行旋转策略是选择距离造成不平衡节点最近的不平衡节点作为要操作节点。 平衡二叉树特别稳定但每次进行调整都会耗费计算机性能。 我们想既要时间复杂度在O(logn)又要十分稳定还要不耗费计算机性能这时推出了红黑树。
红黑树基于2-3-4树
2-3-4树是从下向上构建的。节点内升序每个节点最多有3个值当插入第4个值时需要在这四个之中选中间值进行升元。
实例 然后通过2-3-4树转换 形成红黑树
转换规则如下图 将刚刚的2-3-4树转换为红黑树 红黑树的特点
1、红黑树中每一个节点不是红色节点就是黑色节点。
2、红黑树当中根节点一定是黑色的。———在转化的过程中2-3-4节点都是以黑色节点开头的
3、每一个叶子节点都是黑色的。
4、从根节点到任意一个叶子节点的路径上所走过的黑色节点的数量相同
5、如果一个节点是红色的那么他的子节点一定是黑色
4、5条特点会导致最长的路径绝对不会超过最短路径的2倍。例如最长路径为黑红黑红黑红最短路径为黑黑黑。
为什么红黑树是O(logn)
2-3-4树是多叉树如果数据相等它的时间复杂度小于传统二叉树2-3-4树的时间复杂度
红黑树最复杂的时候也就是变为2倍变为2logn。这是依旧可以看成是logn。
B树
多叉树以B树为最基本点。2-3-4树来源于B树。
B树特点
1、B树的数据存储是 key-value类型的。
2、B树有几个叉并不确定要看具体实现。
3、M阶B树 3.1、每个节点上最多有 M-1 个值并且以升序排列。3阶B树每个节点最多有两个值。.....2-3-4树属于4阶B树
红黑树和B树如果都在内存中内存向cpu提供数据的时间相等由于红黑树对比次数相对较少所以红黑树是内存最优二叉树。
为什么要有B树
红黑树和B树如果都在磁盘中--------》数据寻址浪费时间--------》磁头移动的物理时间平均盘面旋转半圈
B树多用于磁盘原因是分出多个叉降低树的高度降低寻址次数和时间。
B树优胜于寻址但是数据进行对比还是要在内存中。
B树
在B树基础上改造出现的B树但和传统B树又不太一样。B树是mysql数据库专用底层数据结构。
B树的特点
1、非叶子节点仅具有索引功能也就是说非叶子节点只能存储key值不能存储value值。
2、B树的所有叶子节点会构成一个有序的链表这样就可以根据key值遍历数据。
之所以有这两个特点就是为数据库的功能服务
B树的构建 插入 3 4 磁盘向cpu推送数据每次需要推送一页4kb的数据如两个文件 2kb3kb只能先推送2kb再推送3kb。
B树的优点
1、非叶子节点不包含数据只能放索引这样每次就可以向内存当中传输更多的key值在内存当中进行数据比对在磁盘当中进行数据查询。
2、叶子节点是链接在一起的这样有利于区间查询。
