红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别

发布时间:2023-03-17 18:30

1、红黑树与平衡二叉查找树的区别:
平衡二叉树(AVL):

  • 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1 (完全平衡),并且左右两个子树都是一棵平衡二叉树。
  • 时间复杂度最好情况和最坏情况都为O(lgn)
  • 为保证绝对平衡,所以插入、删除后需要多次旋转来保持平衡,因而非常耗时。

红黑树:

  • 红黑树放弃了追求完全平衡,追求大致平衡
  • 时间复杂度最好情况和最坏情况也为O(lgn)
  • 追求大致平衡所以,不需大量旋转操作

总结: AVL树适合用于插入与删除次数比较少,但查找多的情况;若插入删除次数较多,则红黑树适合。

参考资料:红黑树与平衡二叉树的区别?
红黑树和AVL树(平衡二叉树)区别

2、红黑树性质:
满足红黑性质的二叉搜索树
\"红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别_第1张图片\"
红黑树保证没有一条到叶节点的路径会比其他路径长出两倍,因此是近似平衡的,如图(a)所示。
为了便于代码,使用哨兵代表NULL,表示叶节点与根节点的父节点,如图(b)所示。
\"红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别_第2张图片\"
通常只显示内部节点:
\"红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别_第3张图片\"
3、旋转操作:用于维护红黑性质
左旋与右旋:旋转后节点拼接保证二叉查找树性质即可容易理解。
左旋(右旋):变为其右(左)孩子的左(右)孩子。
\"红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别_第4张图片\"
伪代码:
\"红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别_第5张图片\"
4、插入:
步骤:
a、按二叉搜索树方法插入到叶子节点;
b、着色为红色;
c、调用红黑性质调整函数,通过旋转与重新着色让树变成红黑树。
\"红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别_第6张图片\"
代码17行:红黑性质调整函数:
分三类情况:
**情况1:z的叔节点y为红色:**循环调整颜色使得满足性质4,直到父节点为黑色。
\"红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别_第7张图片\"
情况2:z的叔节点y为黑色且z为一个右孩子: 通过左旋变为 情况3
**情况3:z的叔节点y为黑色且z为一个左孩子:**通过右旋并重新着色完成红黑性质调整。
\"红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别_第8张图片\"
整体代码:
\"红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别_第9张图片\"
\"红黑树:旋转、插入、删除操作;与平衡二叉查找树的区别_第10张图片\"
5、删除
太复杂了,工作中用到再学习吧。面试中了解原理,会用,知道去哪里学习就可以了。

总结:

1、红黑树追求大致平衡,AVL树追求绝对平衡。
2、红黑树在二叉查找树基础上,通过左旋右旋,颜色调整来满足性质。
3、了解红黑树性质。

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号