#红黑树概念与性质
时间复杂度: 插入O(log2n), 删除(O(log2n)), 查询(O(log2n)).
平衡二叉树(AVL): 平衡二叉树的插入与删除很容易破坏平衡特性，需要频繁调整，时间开销较大，适用于查询为主。
红黑树RBT: 插入与删除很多时候不会破坏红黑树的特性，即便需要调整，一般都可以在常数级时间内完成，适用于频繁插入与删除的场景。

##特性

  1. 红黑树是二叉排序树，满足二叉排序数的特点，左子树结点值≤根结点值≤右子树结点值。
  2. 与普通BST相比：
    • 每个结点或是红色的或是黑色的
    • 根结点是黑色的
    • 叶结点(也叫做外部结点，NULL节点，失败结点)均是黑色的
    • 不存在两个相邻的红色结点(即红结点的父亲结点与孩子结点均为黑色)
    • 对每个结点，从当前节点出发到任一叶节点的简单路径上，所含黑结点的数目相同。
      1
      2
      3
      4
      5
      6
      7
      struct RBNode{
        int key;
        RBNode *parent;
        RBNode *lchild;
        RBnode *rchild;
        int color;
      };
      背诵口诀: 左根右，根叶黑，不红红，黑路同
  3. 结点的黑高bh——从某节点出发不包含该节点到任一空叶结点的路径上黑色结点的个数。
  4. 性质：
    1. 从根节点到叶节点的最长路径不大于最短路径的2倍
    2. 有n个内部结点的红黑树高度为h<2log2(n+1)

#红黑树的查找，插入与删除

红黑树的查找

红黑树的查找与BST(二叉排序树),AVL(平衡二叉树)相同，从跟出发，左小右大，若查找到一个空叶结点，则查找失败。
##红黑树的插入

  • 先查找，确定插入位置(原理同二叉排序树)，插入新节点
  • 新结点时根——染为黑色
  • 新结点非跟——染为红色
    • 若插入新结点后仍然满足红黑树定义，则插入结束
    • 若插入新结点后不满足红黑树定义，则需要调整，使其重新满足红黑树定义(如何调整？答：看新叔叔的脸色(hahahaha!))
      • 黑叔：旋转＋染色(旋转与平衡二叉树相同)
        • LL型：右单旋，父换爷+染色(以插入结点的父节点为基准旋转)
        • RR型：左单旋，父换爷+染色(同上)
        • LR型：左、右双旋，儿换爷＋染色(先以插入结点为基准左旋在以旋转后的当前结点位置右旋)
        • RL型：右、左双旋，儿换爷+染色(上述左右相反即可)
      • 红叔：染色＋变新
        • 叔父爷染色，爷变为新结点(变为新结点即从该插入部分第二句话开始考虑该结点即可。)

根节点黑高为h的红黑树，内部结点数(关键字数量)至少有${r^h} - 1$个(总共有h层黑节点的满树形态)。

红黑树的删除

  1. 红黑树的删除结点的处理方式与二叉排序树的删除方式相同。
  2. 删除结点之后，可能破坏红黑树的特性，此时需要调整使其再次满足红黑树的情况，调整方式与插入部分的调整方式相同。

此文内容总结自王道考研数据结构课程，仅作个人笔记记录使用。