解答
红黑树是 1972 年发明的,称为对称二叉 B 树,1978 年正式命名红黑树。主要特征是在每个节点上增加一个属性表示节点颜色,可以红色或黑色。
红黑树和 AVL 树类似,都是在进行插入和删除时通过旋转保持自身平衡,从而获得较高的查找性能。
与 AVL 树相比,红黑树不追求所有递归子树的高度差不超过 1,保证从根节点到叶尾的最长路径不超过最短路径的 2 倍,所以最差时间复杂度是 O(logn)。红黑树通过重新着色和左右旋转,更加高效地完成了插入和删除之后的自平衡调整。
红黑树在本质上还是二叉查找树,它额外引入了 5 个约束条件:
① 节点只能是红色或黑色。
② 根节点必须是黑色。
③ 所有 NIL 节点都是黑色的。
④ 一条路径上不能出现相邻的两个红色节点。
⑤ 在任何递归子树中,根节点到叶子节点的所有路径上包含相同数目的黑色节点。
这五个约束条件保证了红黑树的新增、删除、查找的最坏时间复杂度均为 O(logn)。如果一个树的左子节点或右子节点不存在,则均认定为黑色。红黑树的任何旋转在 3 次之内均可完成。
帖子还没人回复快来抢沙发