视频课程
小黑屋思过中,禁止观看!
评论并刷新后可见

您需要在视频最下面评论并刷新后,方可查看完整视频

视频课程
立即观看
付费视频

您支付费用,方可查看完整视频

¥{{user.role.value}}
课程视频
开始学习
会员专享

视频合集

红黑树详解

  • 课程笔记
  • 问答交流

红黑树的应用场景非常广泛,在数据结构与算法里占据很重要的位置,需要重点掌握。
为了助大家掌握好红黑树,这节课我会重点讲解以下5点:

1.平衡二叉树
2.什么是红黑树
3.红黑树的特征
4.红黑树的左旋和右旋
5.红黑树的应用场景

平衡二叉树(AVL树)

红黑树详解-mikechen
平衡二叉树全称平衡二叉搜索树,也叫AVL树,是一种自平衡的树。

AVL树也规定了左结点小于根节点,右结点大于根节点。并且还规定了左子树和右子树的高度差不得超过1,这样保证了它不会成为线性的链表。

什么是红黑树

红黑树(Red Black Tree) 是一种自平衡二叉查找树,典型的用途是实现关联数组。

它是在1972年发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 修改为如今的“红黑树”。

红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。

红黑树特征

红黑树详解-mikechen

  • 红黑树为平衡二叉树的一种
  • 节点是红色或黑色。
  • 根节点是黑色。
  • 每个叶子节点都是黑色的空节点(NIL节点)。
  • 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树的左旋和右旋

评论交流
    说说你的看法