内容上主要是复习了B树和红黑树,其他的因为太简单所以就只是过了一下,没记录下来
不包括全部内容 基础部分包括大O记号和小o记号的意义,P问题和NP问题和NP hard问题 B树和B+树 AVL平衡树和红黑树 KMP
资料:
资料来源:
M阶B树的特征:
区别:
B+树的查询优势:
参考资料2:简书-30张图了解红黑树 参考资料3:清华大学邓俊辉-红黑树演示 参考资料4:使用2-4树看待红黑树
AVL树:平衡二叉树,每个节点平衡因子的绝对值不超过1,即左右子树高度差不超过1。 最大的作用是使得二叉查找树更平衡,本质上是特殊的二叉查找树。 红黑树的性质:
为了满足性质,有三种变化:
所有插入的点默认为红色。(PS:叶子节点为黑色)为什么这么规定:因为红黑树中所有的点都是黑色,也是满足要求的,这样可能会造成问题。
重要例子:
根据邓俊辉老师的思路来,之前那个人很多没有讲 3+4重构,AVL保持平衡的方式,因为涉及到3个结点和4个子树,被称为3+4重构。
红黑树是一种persistent data structure,操作不会就地更新,而是会生成一个新的数据结构。 定义:
红黑树的提升变换:红黑树本质上是2-4树,即4路平衡树。进行提升变化后可以变为原来的4阶B树。 提升变化操作:将黑节点与其红孩子(可以迭代)视为B树的超级节点即可得到红黑树。4阶B树拆分,超级结点如果超过1个,则红黑相间且黑色占多数,则可以拆分成红黑树。
双红缺陷:有两个红结点相邻,表现在B树上是有两个红结点在B树中相邻。调整上可以使用局部3+4重构,重新染色。
调整完成后,g作为新的调整基准点与上层进行调整。如果为根节点,则直接转为黑色并进行颜色变换处理。
双红修正算法复杂度:
因此会更加关心重构操作,因为这对于一个持久化结构而言更加重要。
按照BST的常规算法,删除操作会将检索到的数据点移除,并用某一个后代来替代。但红黑树的性质不一定会继续加以维持。有可能违反3、4的性质。 情况0:被删除结点有一个红孩子。因为黑结点与其红孩子之间存在一条虚边,将红孩子上移并染色本质上相等于删除这条虚边,这样外部节点的黑距离是不变的,性质3也不会受到影响。
问题: 双黑缺陷,此时外部节点的黑高度是不同的。从B 树角度,所属结点发生了下溢。需要考察两个结点,一个是原树中的父亲,一个是原树中的兄弟。
从第二幅图可以看出,双黑操作对应的是下溢,此时可以用B树操作进行处理。(PS,我个人觉得从2-4树的角度,第二幅图的结点颜色应该为黑色,不然很不对劲),对应的是3+4重构。
s为黑,且两个孩子均为黑。根据父结点为红或黑分为两种子情况。
问题没有解决:黑高度的异常依然存在。但无形中r已经有了黑色的兄弟s’,由于p已经转为红色,之后只可能为BB-1或BB-2R。于是再经过一轮修复,红黑树的性质必然可以恢复。
插入后需要进行的操作:检索插入位置并执行插入,插入后如果改变红黑树性质则进行平衡。 注意,插入的结点一定为红色。 如果插入的结点的父节点为黑色,直接插入 如果插入结点的父节点为红色,则如上文的双红问题,以叔叔结点是否存在或颜色为判断标准. 设父结点为P,叔叔结点为S,祖父结点为PP