网站制作网站开发公司,wordpress 后台分页按钮,免费地方域名注册,百度深圳总部问题引入
二叉查找树在频繁的动态更新过程中#xff0c;可能会出现树的高度远大于 log2n 的情况#xff0c;从而导致各个操作的效率下降。极端情况下#xff0c;二叉树会退化为链表#xff0c;时间复杂度会退化到 O(n)。要解决这个复杂度退化的问题#xff0c;需要设计一…问题引入
二叉查找树在频繁的动态更新过程中可能会出现树的高度远大于 log2n 的情况从而导致各个操作的效率下降。极端情况下二叉树会退化为链表时间复杂度会退化到 O(n)。要解决这个复杂度退化的问题需要设计一种平衡二叉查找树。在工程中很多用到平衡二叉查找树的地方都会用红黑树。为什么工程中都喜欢用红黑树而不是其他平衡二叉查找树呢
什么是“平衡二叉查找树”
平衡二叉树的严格定义是这样的二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树但是非完全二叉树也有可能是平衡二叉树。 平衡二叉查找树不仅满足上面平衡二叉树的定义还满足二叉查找树的特点。最先被发明的平衡二叉查找树是AVL 树它严格符合我刚讲到的平衡二叉查找树的定义即任何节点的左右子树高度相差不超过 1是一种高度平衡的二叉查找树。
很多平衡二叉查找树其实并没有严格符合上面的定义树中任意一个节点的左右子树的高度相差不能大于 1比如红黑树它从根节点到各个叶子节点的最长路径有可能会比最短路径大一倍。
学习数据结构和算法是为了应用到实际的开发中的没必要去死抠定义。对于平衡二叉查找树这个概念要从这个数据结构的由来去理解“平衡”的意思。发明平衡二叉查找树这类数据结构的初衷是解决普通二叉查找树在频繁的插入、删除等动态更新的情况下出现时间复杂度退化的问题。所以平衡二叉查找树中“平衡”的意思其实就是让整棵树左右看起来比较“对称”、比较“平衡”不要出现左子树很高、右子树很矮的情况。整棵树的高度相对来说低一些相应的插入、删除、查找等操作的效率高一些。
如何定义一棵“红黑树”
红黑树的英文是“Red-Black Tree”简称 R-B Tree。它是一种不严格的平衡二叉查找树。红黑树中的节点一类被标记为黑色一类被标记为红色。除此之外一棵红黑树还需要满足这样几个要求
根节点是黑色的每个叶子节点都是黑色的空节点NIL也就是说叶子节点不存储数据任何相邻的节点都不能同时为红色也就是说红色节点是被黑色节点隔开的每个节点从该节点到达其可达叶子节点的所有路径都包含相同数目的黑色节点
这里的第二点要求“叶子节点都是黑色的空节点”稍微有些奇怪它主要是为了简化红黑树的代码实现而设置的下一节我们讲红黑树的实现的时候会讲到。这节我们暂时不考虑这一点所以在画图和讲解的时候我将黑色的、空的叶子节点都省略掉了。
为什么说红黑树是“近似平衡”的
平衡二叉查找树的初衷是为了解决二叉查找树因为动态更新导致的性能退化问题。所以“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化得太严重。
解答开篇
AVL 树是一种高度平衡的二叉树所以查找的效率非常高但是有利就有弊AVL 树为了维持这种高度的平衡就要付出更多的代价。每次插入、删除都要做调整就比较复杂、耗时。所以对于有频繁的插入、删除操作的数据集合使用 AVL 树的代价就有点高了。
红黑树只是做到了近似平衡并不是严格的平衡所以在维护平衡的成本上要比 AVL 树要低。所以红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说要面对各种异常情况为了支撑这种工业级的应用我们更倾向于这种性能稳定的平衡二叉查找树。
关于红黑树究竟需要掌握哪些东西
观点学习数据结构和算法要学习它的由来、特性、适用的场景以及它能解决的问题。对于红黑树也不例外。重点掌握下面几个关键点
红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中复杂度退化的问题而产生的。红黑树的高度近似 log2n所以它是近似平衡插入、删除、查找操作的时间复杂度都是 O(logn)。因为红黑树是一种性能非常稳定的二叉查找树在工程中但凡是用到动态插入、删除、查找数据的场景都可以它实现起来比较复杂如果自己写代码实现难度会有些高这个时候其实更倾向用跳表来替代它
