示意图来源于《王道考研数据结构》

AVL树

以最小不平衡树-首棵平衡因子差绝对值大于1的树作为研究对象

LL旋转

左孩子的左子树有新插入，导致的不平衡

旋转方式：左孩子向根的方向旋转

RR旋转

右孩子的右子树有新插入，导致的不平衡

旋转方式：右孩子向根的方向旋转

LR旋转

左孩子的右子树有新插入，导致的不平衡

旋转方式：右子树的根向左孩子的方向旋转，再向根的方向旋转

RL旋转

右孩子的左子树有新插入，导致的不平衡

旋转方式：左子树的根向右孩子的方向旋转，再向根的方向旋转

B树

基本结构


本质为一棵m-叉搜索树，每个结点中关键字个数n的要求：$\lceil n/2 \rceil -1 \leq n \leq m-1$

查找

同BST

插入

先查找定位，再插入，若插入后关键字个数大于m-1，则结点分裂为两个新节点，取中位数作为父节点的新关键字

删除

  • 待删除关键字k不在终端结点时，直接删除k，并用其前驱或后继代替k

  • 待删除关键字k在终端节点时：

    1. 删除后仍然够：直接删除
    2. 删除后不够：
      1. 兄弟够借：通过父子换位达到新的平衡
      2. 兄弟不够借：