[What]数据结构与算法 -> 红黑树

课程:王争 –> <数据结构与算法之美>

前导知识: 红黑树的演变

认识传说中的红黑树。

概念

普通的二叉查找树在理想情况下,时间复杂度是O(logn),但当其频繁更新后有可能退化为一个链表,其时间复杂度就是O(n)。

平衡二叉树 为避免低效的查找效率,规定:二叉树中任意一个节点的左右 子树 的高度相差不能大于一。

  • 也就是说任意一个节点的左右子树高度可以小于或等于一,对于前面的满二叉树和完全二叉树都满足此要求,除此之外还有很多其它树也满足。
  • 因为二叉查找树的高度决定了时间复杂度,所以当树左右的高度平衡时,整体上树的高度就会低一些,对应的时间复杂度就小一些。
balance_binary_tree.jpg

红黑树并未严格符合平衡二叉树的定义,其节点由红色和黑色组成,满足以下要求:

  • 根节点是黑色的
  • 每个叶子节点都是黑色的空节点(NIL, 不存储实际数据)
  • 任何相邻的节点都不能同时为红色,红色节点被黑色节点隔开
    • 相邻的意思是指通过连线连接起来的节点
  • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点
rb-tree.jpg* 实现逻辑

红黑树的插入和删除和二叉查找树没有本质的不同,关键在于插入和删除后很可能会破坏原有的黑色平衡:

  • 相邻的节点都不能同时为红色
  • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点

为了保证黑色平衡,其本质操作便是 左旋(rotate left),右旋(rotate right),翻转(flip)

rb_op.jpg

这些操作查看文章开头提到的那篇文章更好理解。

Last Updated 2019-04-15 一 20:41.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)