Skip to main content

8-几种奇怪恶心的树

平衡二叉树

左右子树高度之差的绝对值不超过1的二叉排序树称为平衡二叉树。

插入​

找到合适的位置插入，然后判断类型进行处理：

  1. LL：右旋
  2. RR：左旋
  3. LR：先左后右
  4. RL：先右后左

删除​

删除一个节点后，会导致一棵子树失衡，假设删除w，则要回溯找到第一个不平衡节点z，y为z子树中高度最高的孩子节点，x是y中高度最高的孩子节点，根据x和y、z的位置进行处理，若x、y是z的：

  1. LL：右旋
  2. RR：左旋
  3. LR：先左后右
  4. RL：先右后左

删除和插入操作类似，不同之处在于删除的调整，可能会导致另外的不平衡，需要反复多次进行调整。

红黑树

概念​

什么是红黑树，红黑树是一种特殊的二叉排序树，考试内容不会很深，简单清楚性质概念和插入操作即可，删除操作很难，考察概率不大。

主要性质：

  1. 每个结点或黑或红
  2. 根节点必黑
  3. 叶节点必黑，这里的叶节点是外部结点
  4. 不存在两个相邻的红节点
  5. 任意一个节点，该节点到任意一个叶节点的简单路径上，经过的黑节点数目是一样的

顺口溜：

info
  • 左根右（排序）
  • 根叶黑
  • 不红红
  • 黑路同

两个结论：

  • 从根出发到叶节点的路径不大于最短路径的一半
  • 有n个内部红节点的红黑树高度h≤2∗log2(n+1)h \le 2*log_{2}{(n+1)}
  • 插入的节点初始化为红

插入操作​

  1. 第一步先确定要插入的位置
  2. 若为根节点，直接染黑
  3. 如果不破坏红黑树特征，正常
  4. 如果破坏了“不红红”的条件，找到父亲的兄弟结点，也就是叔结点，按照叔结点的两种情况去调整:(1)红叔叔（2）黑叔叔

（1）红叔叔 叔、父、爷结点染色（颜色反转），同时爷结点变成新节点（变黑则无所谓，变红则要再调整）。 （2）黑叔叔 找父节点和爷结点，判断当前节点对于爷结点的位置进行调整：

  1. LL：右旋，父节点换爷结点，同时父和爷染色
  2. RR：左旋，父节点换爷结点，同时父和爷染色
  3. LR：先左后右，当前节点先左后右，儿结点换爷结点，同时染色
  4. RL：先右后左，当前节点先右后左，儿结点换爷结点，同时染色

B树

概念​

info
  1. 树中每个结点至多有m个子树，即一个节点中至多m-1个关键字
  2. 根节点至少两棵子树
  3. 初根节点外的所有非叶节点，至少[m/2]（向上取整）棵子树，即至少有[m/2]（向上取整）-1个关键字
  4. 所有叶节点在最后一层（NULL节点，空指针）

image.png image.png

B树高（磁盘存取次数）​

最矮​

image.png

最高​

image.png

查找​

  1. 在B树中找节点
  2. 在节点中中找关键字

与节点中的关键字进行比对，其中节点的左指针指向的节点集合小于该节点，右指针指向的节点集合大于节点，依据这种特性，一层层进行查找，如果到最后NULL节点，则说明找不到了。

插入​

明确一点，一个节点内的关键字个数[（m/2）向上取整-1，m-1]

  1. 定位，找到应该插入的位置
  2. 插入，如果关键字个数插入后在正确范围内，则直接插入，否则进行处理
  3. 多的情况处理如下：

image.png 如下处理： image.png

删除​

明确一点，一个节点内的关键字个数[（m/2）向上取整-1，m-1]，所以删除后节点的关键字个数不能小于（m/2）向上取整-1。

  1. 直接删除，如果删除满足关键字的最低要求，则直接删除
  2. 如果在非终端节点，则用直接前驱或者直接后继来代替

image.png

  1. 如果在兄弟够借，即目前关键字删除前为**（m/2）向上取整-1**，且其左（右）兄弟的关键字数目大于**（m/2）向上取整，**则从兄弟中拿一个节点，放到父节点中，然后从父节点中拿一下下来填充给不满足要求的节点，称为父子换位法

image.png 这里的92处已经不满足，但是左兄弟仍然充裕，则进行父子换位法： image.png

  1. 兄弟不够借。当兄弟不够借的时候，当前节点+兄弟结点的个数为m-2，此时需要父节点落下一个节点，与兄弟合并，则合并后的节点关键字数目为m-1，同时父节点关键字数目-1。如果父节点不满足要求，则进行兄弟够借和兄弟不够借两种试探，进行填补跟合并。如果操作使得根节点-1变为0，则直接删除根节点，换成新的根节点。(切记不可进行前驱后继填补)

image.png 此时需要父节点落下70，进行合并： image.png 73处不满足，同时左兄弟不够借，则82落下，进行合并： image.png 删除根节点，合并得新根节点： image.png

B+树（常用于关系型数据库的存储）

概念​

  1. m阶B+树每个结点最多m棵子树（也就是最多m个孩子节点）
  2. 非叶、根节点至少有两棵子树，其他每个分支节点至少有（m/2）向上取整棵子树
  3. 节点的子树个树和关键字个数一样
  4. 叶节点包含所有关键字，也就是全部关键字都会存储在叶子节点，节点内按大小排序
  5. 所有分支节点，中仅仅包含它所指向的子节点中的最大值，及其子节点的指针
  6. 叶节点之间会有指针穿在一起（支持顺序查找）

image.png 如上：3，9，15中存储的分别是三个子节点中的最大值，最后绿色的叶节点之间有指针连在一起。

查找​

从根出发，找到合适的位置（处于哪个子节点），过程中会在非叶节点中遇到关键字，但这并不是查找成功，要一直查到叶节点中才算成功，这是区别于B树的一个地方，B树是能够在非终端节点中就找到结果的。 如下是一个查找成功的例子，查找9，从根出发，直到叶节点。 image.png

如下是查找失败的例子：从根出发，进入15的子节点，然后进入9的子节点，对比了6->8，发现8已经大于7，则查找失败了。 image.png 总之无论成功与否，最终都一定要走到最下面的一层节点。

B和B+的类比​

image.png