一、红黑树RBT概念

1、【红黑树RBT】引入的原因

• 它就是对【平衡二叉树AVL】的优化
  • 【平衡二叉树AVL】的【插入、删除】为了保持平衡性，处理得非常麻烦
  • 而【红黑树RBT】不需要【平衡性】！！！相对【插入、删除】更方便

2、【平衡二叉树性能】VS【红黑树性能】

• 1）在【增、删、查】方面的【时间复杂度】

  • 记住【时间复杂度】BST、AVL、RBT全都一样
  • 但是注意【时间复杂度】不等于【效率】，效率还包括中间【具体操作的复杂性】

• 2）在【调整树形态】方面的【效率】

• 3）【主要常用功能】不同

  • 由上面对【调整树形态】方面对比，可以知道【红黑树】更牛逼克拉斯！！！
  • 但是因为【保持平衡性】，平衡二叉树的树高通常比红黑树更低！！！所以：
    • 【平衡二叉树】：【查找】牛逼！！！！！！
    • 【红黑树】：【插入、删除】牛逼！！！！！

二、红黑树的【定义】

对各个定义的解释：

• 1、只有红节点和黑节点。【根节点】和【叶子节点】必须是【黑色】
  • 注意：叶子节点是指【空节点】
• 2、不允许【连续两个红节点】
• 3、任一点的【子孙的路径到叶子节点的路上】，【黑色节点数一样多】
  • 以上所有定义结论可以总结为【左根右、根叶黑、不红红、黑路同】

；

；

• 【黑高nh】

  • 上面我们知道有个定义结论：【黑路同：任一点其后代路径到叶节点，黑色点数一样】
  • 那么【任一点这个路径的黑色点数目（不包括根节点）】就是【该点的黑高nh】
  • 而【树的黑高】=【根节点的黑高】

；

• 练习红黑树定义规则

三、红黑树的【性质】

• 1、性质一：【最长路径 = 最短路径2倍】

• 2、性质二：【红黑树高h：2log2(n+1)】

  • 注意：【n是内部节点，不包括空叶节点】
  • 记忆方法1：由【时间复杂度：O(log2n)】联想【树高：2log2(n+1)】，时间复杂度+1再×2倍
  • 记忆方法2：就记住【树高为h的红黑树，h/2高的子树一定是满二叉树】！！！！
  • 具体分析原因如下图，简单理解就是：
    • “最短路径”全是黑点、“最长路径”一半黑点一半红点
    • 而“最长路径” 就是 “树高h”；“最短路径”又是 “最长路径的1/2”，也就是 “h/2”
    • 那么【树高h/2子树】包含了【最长短路全部】和【最长路径一半】，必是满二叉树
    • 根据二叉树【节点数n 与 高度h/2】的关系计算，可得出【整个树高h】

• 3、性质三：高度h红黑树节点数【最少2^k - 1】、【最多2^2k - 1】

  • 【最少情况】：全是黑色点嘛，高度是h
  • 【最多情况】：在最少情况基础上，往中间穿插红色点，各个路径上一半黑点一半红点，高度放大2倍==>2h
• 其他性质：
  • 前面的性质基本都包含了下面性质

四、红黑树【操作】

1、红黑树【查找】

没什么说的，跟BST和AVL一模一样，小左大右

2、红黑树【插入】

规则：

【例子】

3、红黑树【删除】

不学了，反正大概率不考，就记住这一点就行，谁爱学谁学去吧

五、【例题】