二叉搜索树、AVL、红黑树

1. 二叉搜索树

找一个节点的前驱和后继：
前驱：如果节点有左子树，找左子树的最大值，如果没有左子树，找最近一个自右而来的节点
后继：如果节点有右子树，找右子树的最小值，如果没有右子树，找最近一个自左而来的节点

2. avl树

左右子树高度差不超过1
新增和删除节点会导致树的失衡，要进行下面操作
LL
LR
RR
RL

3. 红黑树

红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少

红黑树特性

1. 所有节点都有两种颜色：红🔴、黑??
2. 所有 null 视为黑色??
3. 红色🔴节点不能相邻
4. 根节点是黑色??
5. 从根到任意一个叶子节点，路径中的黑色??节点数一样

插入情况

插入节点均视为红色🔴

case 1：插入节点为根节点，将根节点变黑??

case 2：插入节点的父亲若为黑色??，树的红黑性质不变，无需调整

插入节点的父亲为红色🔴，触发红红相邻

case 3：叔叔为红色🔴

• 父亲变为黑色??，为了保证黑色平衡，连带的叔叔也变为黑色??
• 祖父如果是黑色不变，会造成这颗子树黑色过多，因此祖父节点变为红色🔴
• 祖父如果变成红色，可能会接着触发红红相邻，因此对将祖父进行递归调整

case 4：叔叔为黑色??

1. 父亲为左孩子，插入节点也是左孩子，此时即 LL 不平衡
   • 让父亲变黑??，为了保证这颗子树黑色不变，将祖父变成红🔴，但叔叔子树少了一个黑色
   • 祖父右旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
2. 父亲为左孩子，插入节点是右孩子，此时即 LR 不平衡
   • 父亲左旋，变成 LL 情况，按 1. 来后续处理
3. 父亲为右孩子，插入节点也是右孩子，此时即 RR 不平衡
   • 让父亲变黑??，为了保证这颗子树黑色不变，将祖父变成红🔴，但叔叔子树少了一个黑色
   • 祖父左旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
4. 父亲为右孩子，插入节点是左孩子，此时即 RL 不平衡
   • 父亲右旋，变成 RR 情况，按 3. 来后续处理

删除情况

case0：如果删除节点有两个孩子

• 交换删除节点和后继节点的 key，value，递归删除后继节点，直到该节点没有孩子或只剩一个孩子

如果删除节点没有孩子或只剩一个孩子

case 1：删的是根节点

• 删完了，直接将 root = null
• 用剩余节点替换了根节点的 key，value，根节点孩子 = null，颜色保持黑色??不变

删黑色会失衡，删红色不会失衡，但删黑色有一种简单情况

case 2：删的是黑??，剩下的是红🔴，剩下这个红节点变黑??

删除节点和剩下节点都是黑??，触发双黑，双黑意思是，少了一个黑

case 3：被调整节点的兄弟为红🔴，此时两个侄子定为黑 ??

• 删除节点是左孩子，父亲左旋
• 删除节点是右孩子，父亲右旋
• 父亲和兄弟要变色，保证旋转后颜色平衡
• 旋转的目的是让黑侄子变为删除节点的黑兄弟，对删除节点再次递归，进入 case 4 或 case 5

case 4：被调整节点的兄弟为黑??，两个侄子都为黑 ??

• 将兄弟变红🔴，目的是将删除节点和兄弟那边的黑色高度同时减少 1
• 如果父亲是红🔴，则需将父亲变为黑，避免红红，此时路径黑节点数目不变
• 如果父亲是黑??，说明这条路径还是少黑，再次让父节点触发双黑

case 5：被调整节点的兄弟为黑??，至少一个红🔴侄子

• 如果兄弟是左孩子，左侄子是红🔴，LL 不平衡
  • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑??，平衡起见，左侄子也是黑??
  • 原来兄弟要成为父亲，需要保留父亲颜色
• 如果兄弟是左孩子，右侄子是红🔴，LR 不平衡
  • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑??
  • 右侄子会取代原来父亲，因此它保留父亲颜色
  • 兄弟已经是黑了??，无需改变
• 如果兄弟是右孩子，右侄子是红🔴，RR 不平衡
  • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑??，平衡起见，右侄子也是黑??
  • 原来兄弟要成为父亲，需要保留父亲颜色
• 如果兄弟是右孩子，左侄子是红🔴，RL 不平衡
  • 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑??
  • 左侄子会取代原来父亲，因此它保留父亲颜色
  • 兄弟已经是黑了??，无需改变