查找算演进

  • 暴力（遍历）->二叉->二叉查找->自平衡二叉查找（红黑）

    红黑树

  • 红黑就是一种二叉查找数

  • 红黑树四个特点
    • 节点不是红就是黑
    • 不可能有连在一起的红色节点
    • 根节点root总是黑色
    • 每个红色节点的两个字节的都是黑色。叶子节点都是黑色（NaN节点）；出度为0满足了性质就可近似的平衡了，不一定要红黑，可为其他 。
  • 插入
    • 默认插入颜色：红色
  • 动作
    • 左旋：
      • 当前父节点是红色，叔叔节点是黑色；且当前是右子树的时候。以父节点左旋。
      • 1、旋转点下去2、右子节点上去3、右子节点的左子树移动到旋转点的右子节点位置。
    • 右旋：
      • 当前父节点是红色，叔叔是黑色的时候，且当前的节点是左子树。右旋：1、父节点变黑色2、祖父节（爷爷节点）点变红色3、以祖父节点旋转。
    • 变色：红遍黑黑边红。
      • 插入红色，父节点红色，叔叔节点（父节点左右）红色。