北京网站建设建设公司邢台123贴吧最新消息

北京网站建设建设公司,邢台123贴吧最新消息,在线制作网站地图,在线代码生成器一.二叉排序树二叉排序树的定义是任意一个父节点的值#xff0c;大于其左子树节点的值#xff0c;小于其右子树节点的值。以下是两个例子#xff1a;#xff08;1#xff09;数组#xff1a;5,3,1,4,8,9,7它的二叉排序树是这样的#xff1a;它的时间复杂度是O(logn)。大于其左子树节点的值小于其右子树节点的值。以下是两个例子1数组5,3,1,4,8,9,7它的二叉排序树是这样的它的时间复杂度是O(logn)。2数组1,2,3它的二叉排序树是这样的它的时间复杂度是O(n)。由此可见两种情况下的二叉排序树的时间复杂度不同因此二叉排序树是不稳定的。当树的结构完全平衡时如红黑树节点数 n 与高度 h 的关系为h logn。此时核心操作的时间复杂度为O(log n)这是二叉排序树的最优性能。当节点按升序或降序插入时二叉排序树会退化为一条单链每个节点只有左子树或只有右子树。此时树的高度h n核心操作的时间复杂度退化为O(n)。为了解决这种不平衡的现象引入了一种更先进的树名为平衡二叉树。二.平衡二叉树平衡二叉树在排序二叉树的基础上要求左右子树高度差的绝对值不能超过 1小于等于 1。如果这个树不平衡了我们应该怎么调节于是引入了4种平衡化调整策略。1LL型这是调节前的树这是调节后的树技巧让不平衡节点朝着造成不平衡的节点走两步盯着不平衡主链让中间节点成为新的父节点其余节点按照顺序进行插入。2RR型这是调节前的树这是调节后的树整体方法和LL型类似。3LR型这是调节前的树这是调节后的树技巧还是先让不平衡节点朝着造成不平衡的节点走两步然后盯着不平衡主链采用两步旋转法第一步后二整体旋转把造成不平衡的点和它的父节点调换顺序并变成LL/RR型第二步采用LL/RR旋转4RL型这是调节前的树后二整体旋转之后的树这是调节后的树整体和LR型类似。其实平衡二叉树也是有缺点的它过分追求时间复杂度的完美导致旋转过程会消耗大量的计算机资源。于是引入了一个性能更好的树名为红黑树。三.红黑树在介绍红黑树之前要先了解一下2-3-4树4阶B树因为2-3-4树与红黑树是等价的数据结构它们之间可以相互转换。12-3-4树的特点与插入操作2-3-4树每种节点的结构特性每个节点的关键字都是有序排列的且左子树的所有关键字小于根节点关键字右子树的所有关键字大于根节点关键字。所有叶子节点都在同一层保证了树的高度平衡。插入操作首先从根节点开始查找插入位置找到合适的叶子节点后插入新关键字。如果插入后该节点的关键字数量超过 3 个即成为 4 - 节点则需要进行分裂操作。将 4 - 节点中间的关键字提升到父节点左右两边的关键字分别形成两个新节点。如果父节点也因此变得满了成为 4 - 节点则需要递归地对父节点进行分裂操作。22-3-4树到红黑树的转换首先我们先了解一下2-3-4树与红黑树各种节点的对应样式下图是一个2-3-4树然后找到各节点对应的红黑树样式2节点对应一个黑节点3节点对应父节点是黑节点下面接一个红结点4节点对应父节点是黑节点下面左右节点都是红结点。调整好之后如下图所示每个最下方的节点下面都有一个黑色的叶子结点图中没有画出来3红黑树的特点1.红黑树的节点颜色不是红色就是黑色的。2.根节点一定是黑色的。3.叶子节点也是黑色的上面那张图每个最下方的节点下面都有一个黑色的叶子结点图中没有画出来。4.如果一个节点是红色的那么他的子节点一定是黑色的。5.从根节点出发到任意的一个叶子节点所走过的路径上黑色节点的数目是相同的。从特点中还可以得出一个结论红黑树当中最长的链条不会超过最短链条的 2 倍。