数据结构与算法复习

2022-06-17 12:25:25 浏览数 (1)

原文地址

内容上主要是复习了B树和红黑树，其他的因为太简单所以就只是过了一下，没记录下来

数据结构与算法复习

不包括全部内容 基础部分包括大O记号和小o记号的意义，P问题和NP问题和NP hard问题 B树和B 树 AVL平衡树和红黑树 KMP

资料：

  • B站-内功心法，红黑树、平衡树、B树和B 树
  • 清华大学邓俊辉-数据结构与算法，我计划把这篇与它的计算几何做两个观后笔记。

B树和B 树

资料来源：

  • MIT6.046
  • 博客

M阶B树的特征：

  1. 非叶子结点最多只有M个分支
  2. 除根节点以外的非叶子结点分支数为上取整(M/2)到M。
  3. 关键字个数=分支数-1
  4. 所有叶子结点位于同一层

区别：

  1. B树的关键字集合分布在整棵树中，而B 树的实际数据只在叶子节点中。因此B树的搜索有可能在非叶子结点结束。
  2. 因为B 树的所有数据都在叶子节点中，所以B 树的叶子节点会依据关键字的大小自小而大的顺序链接，可以进行顺序遍历。非叶子结点可以看作是索引，结点中仅含有子树中的最大或最小关键字。同一个数字会在不同结点中重复出现。

B 树的查询优势：

  1. B 树的中间结点不保存数据，所以磁盘也能够容纳更多结点元素
  2. B 树的查询必须查找到叶子节点，B树不必，因此B 树查找更加稳定，但并不慢
  3. 对于范围查找来说，B 树只需要遍历叶子节点链表（因为是顺序链接的），而B树需要重复进行中序遍历。

红黑树

参考资料2：简书-30张图了解红黑树 参考资料3：清华大学邓俊辉-红黑树演示 参考资料4：使用2-4树看待红黑树

AVL树：平衡二叉树，每个节点平衡因子的绝对值不超过1，即左右子树高度差不超过1。 最大的作用是使得二叉查找树更平衡，本质上是特殊的二叉查找树。 红黑树的性质：

  1. 每个结点不是红色就是黑色
  2. 不可能有连在一起的红色节点。
  3. 根节点一定是黑色root
  4. 每个红色节点的两个子节点都是黑色。叶子节点都是黑色。

为了满足性质，有三种变化：

  1. 红变黑，黑变红，保证根节点是黑色
  2. 左旋
  3. 右旋

所有插入的点默认为红色。（PS：叶子节点为黑色）为什么这么规定：因为红黑树中所有的点都是黑色，也是满足要求的，这样可能会造成问题。

  1. 变颜色的情况：当前结点的父亲是红色，且它的祖父结点的另一个子节点也是红色（叔叔结点）。
    • 把父结点设为黑色
    • 把叔叔也设为黑色
    • 把祖父结点，也就是父节点的父节点设为红色
    • 把指针定义到祖父结点设为当前要操作的分析的点变换的规则
  2. 左旋：当前父结点是红色，叔叔结点是黑色，且当前结点是右子树。左旋以父节点为左旋。
  3. 右旋：当前父结点是红色，叔叔结点是黑色，且当前的结点是左子树。右旋
    • 把父节点变为黑色
    • 把祖父节点变为红色
    • 以租父节点旋转

重要例子：

红黑树

根据邓俊辉老师的思路来，之前那个人很多没有讲 3 4重构，AVL保持平衡的方式，因为涉及到3个结点和4个子树，被称为3 4重构。

基础定义

红黑树是一种persistent data structure，操作不会就地更新，而是会生成一个新的数据结构。 定义：

  1. 树根必定为黑色
  2. 外部节点均为黑色
  3. 其余节点：如果为红色，只能有黑色的孩子
  4. 外部节点到根：途中黑节点数目相等。

提升变换

红黑树的提升变换：红黑树本质上是2-4树，即4路平衡树。进行提升变化后可以变为原来的4阶B树。 提升变化操作：将黑节点与其红孩子（可以迭代）视为B树的超级节点即可得到红黑树。4阶B树拆分，超级结点如果超过1个，则红黑相间且黑色占多数，则可以拆分成红黑树。

双红缺陷与修正

双红缺陷：有两个红结点相邻，表现在B树上是有两个红结点在B树中相邻。调整上可以使用局部3 4重构，重新染色。

  • 已知本结点与父结点为红色
  • RR-1：叔叔结点u->color=B，此时重新染色即可。
  • RR-2：叔叔结点u->color=R，此时合并为有4个关键码的超级结点，有3个红色。此时有5个分支，在4阶B树中是非法的，会发生上溢。B树中修复上溢，需要在问题结点中找到居中的关键码并进行分裂。

调整完成后，g作为新的调整基准点与上层进行调整。如果为根节点，则直接转为黑色并进行颜色变换处理。

双红修正算法复杂度：

因此会更加关心重构操作，因为这对于一个持久化结构而言更加重要。

删除

按照BST的常规算法，删除操作会将检索到的数据点移除，并用某一个后代来替代。但红黑树的性质不一定会继续加以维持。有可能违反3、4的性质。 情况0：被删除结点有一个红孩子。因为黑结点与其红孩子之间存在一条虚边，将红孩子上移并染色本质上相等于删除这条虚边，这样外部节点的黑距离是不变的，性质3也不会受到影响。

问题： 双黑缺陷，此时外部节点的黑高度是不同的。从B 树角度，所属结点发生了下溢。需要考察两个结点，一个是原树中的父亲，一个是原树中的兄弟。

  • BB-1：下只是可能下的一种情况，其余情况与其对称或相似，不失一般性。下有三个结点，四棵子树，对此情况进行一次3 4重构

从第二幅图可以看出，双黑操作对应的是下溢，此时可以用B树操作进行处理。（PS，我个人觉得从2-4树的角度，第二幅图的结点颜色应该为黑色，不然很不对劲），对应的是3 4重构。

s为黑，且两个孩子均为黑。根据父结点为红或黑分为两种子情况。

  • BB-2R：此时s所在的超级结点不够数量借出，因此直接合并。上层结点失去了一个关键码p，但不会继续发生下溢。因为p是红色的，因此超级结点中至少有一个黑色的父亲。
  • BB-2B：下层下溢会引发上层下溢，从而向上延伸
  • BB-3：兄弟结点S为红色，其余孩子均为黑。 将BB-3转换为之前的情况

问题没有解决：黑高度的异常依然存在。但无形中r已经有了黑色的兄弟s’，由于p已经转为红色，之后只可能为BB-1或BB-2R。于是再经过一轮修复，红黑树的性质必然可以恢复。

红黑树具体实现

红黑树的插入

插入后需要进行的操作：检索插入位置并执行插入，插入后如果改变红黑树性质则进行平衡。 注意，插入的结点一定为红色。 如果插入的结点的父节点为黑色，直接插入 如果插入结点的父节点为红色，则如上文的双红问题，以叔叔结点是否存在或颜色为判断标准. 设父结点为P，叔叔结点为S，祖父结点为PP

红黑树的删除

ps 重构

0 人点赞