文章目录

  • 二叉搜索树
  • 2. avl树
  • 3. 红黑树

b树和b+树比较适合与磁盘打交道的,磁盘操作耗时,这些树 矮,红黑树、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 不平衡
    • 将来删除节点这边少个黑,所以最后旋转过来的父亲需要变成黑⚫️
    • 左侄子会取代原来父亲,因此它保留父亲颜色
    • 兄弟已经是黑了⚫️,无需改变