二叉搜索树、AVL、红黑树、B树
文章目录
- 二叉搜索树
- 2. avl树
- 3. 红黑树
b树和b+树比较适合与磁盘打交道的，磁盘操作耗时，这些树 矮，红黑树、avL树高，比较适合与内存打交道。
找一个节点的前驱和后继：
前驱：如果节点有左子树，找左子树的最大值，如果没有左子树，找最近一个自右而来的节点
后继：如果节点有右子树，找右子树的最小值，如果没有右子树，找最近一个自左而来的节点
2. avl树
左右子树高度差不超过1
新增和删除节点会导致树的失衡，要进行下面操作
LL
LR
RR
RL
3. 红黑树
红黑树也是一种自平衡的二叉搜索树，较之 AVL，插入和删除时旋转次数更少
红黑树特性
- 所有节点都有两种颜色：红🔴、黑⚫️
- 所有 null 视为黑色⚫️
- 红色🔴节点不能相邻
- 根节点是黑色⚫️
- 从根到任意一个叶子节点，路径中的黑色⚫️节点数一样
插入情况
插入节点均视为红色🔴
case 1：插入节点为根节点，将根节点变黑⚫️
case 2：插入节点的父亲若为黑色⚫️，树的红黑性质不变，无需调整
插入节点的父亲为红色🔴，触发红红相邻
case 3：叔叔为红色🔴
- 父亲变为黑色⚫️，为了保证黑色平衡，连带的叔叔也变为黑色⚫️
- 祖父如果是黑色不变，会造成这颗子树黑色过多，因此祖父节点变为红色🔴
- 祖父如果变成红色，可能会接着触发红红相邻，因此对将祖父进行递归调整
case 4：叔叔为黑色⚫️
- 父亲为左孩子，插入节点也是左孩子，此时即 LL 不平衡
- 让父亲变黑⚫️，为了保证这颗子树黑色不变，将祖父变成红🔴，但叔叔子树少了一个黑色
- 祖父右旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
- 父亲为左孩子，插入节点是右孩子，此时即 LR 不平衡
- 父亲左旋，变成 LL 情况，按 1. 来后续处理
- 父亲为右孩子，插入节点也是右孩子，此时即 RR 不平衡
- 让父亲变黑⚫️，为了保证这颗子树黑色不变，将祖父变成红🔴，但叔叔子树少了一个黑色
- 祖父左旋，补齐一个黑色给叔叔，父亲旋转上去取代祖父，由于它是黑色，不会再次触发红红相邻
- 父亲为右孩子，插入节点是左孩子，此时即 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 不平衡
- 将来删除节点这边少个黑，所以最后旋转过来的父亲需要变成黑⚫️
- 左侄子会取代原来父亲，因此它保留父亲颜色
- 兄弟已经是黑了⚫️，无需改变