About 1 min

红黑树的红黑规则

红黑树的节点：两个属性，值和颜色。三个指针，左右孩子和父。

特殊的叶子节点：左右孩子是nil的，nil算是叶子节点。

  1. 节点的颜色，红或黑。
  2. 根节点是红。
  3. nil叶子节点是黑色。
  4. 不连红：红色节点的孩子必须是黑色。
  5. 黑相等：任意节点，从该节点到其后代叶子节点的每条路径上的黑色节点数量相等。

红黑树添加节点

父黑叔黑爷红

父红叔红：都要，且爷递归

父红叔黑：触发下面的复杂旋转

左右看父，且父递归。左左/右右看爷反，父黑爷红

父为左，就父左旋；父为右，就父右旋。

左左则爷右旋；右右则爷左旋。

1. 根 ---------------------> 根变黑色
2. 非根
    ---> 父黑 ---> 无
    ---> 父红(因为默认子是红，不能父子都红)
        --> 叔红: 父黑叔黑爷红、爷当前递归
        --> 叔黑：
            --> 父为左
                --> 子为左：父黑爷红（叔已黑），爷右旋
                --> 子为右：父左旋，父当前递归
            --> 父为右
                --> 子为左：父右旋，父当前递归
                --> 子为右：父黑爷红（叔已黑），爷左旋

【排序算法】

什么叫做排序算法的稳定性

相同元素被排序后，保持原有数组中的相对顺序不变。

二分查找的复杂度

O(log n)