文章目录
- 二叉搜索树
- 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 不平衡
- 将来删除节点这边少个黑,所以最后旋转过来的父亲需要变成黑⚫️
- 左侄子会取代原来父亲,因此它保留父亲颜色
- 兄弟已经是黑了⚫️,无需改变