主要记录了ads课上学到的内容，每周上完课后进行整理

AVL树

AVL树是高度平衡的树，AVL树解决了二叉搜索树在严格偏序插入的情况下退化为链表的情况。

AVL树的定义如下：

1. 空的树为AVL树（空的树高度为-1，只有跟结点的树高度为0）
2. 非空树若满足左右子树均为AVL树，并且左右子树的高度差的绝对值不超过1，那么就是AVL树

旋转

旋转是实现改变左右子树高度的方法，旋转分为左旋和右旋

左旋是将右子树的根节点提高，右旋是将左子树的根节点提高

1
2
3
4
5

    A							    B
   / \		  右旋			 /  \
  B	z		------>			 x    A
 / \			<------				 / \
x   y			  左旋			   y  z

旋转是一个常数时间内的操作，只需要进行固定的几个点移动

平衡因子

一个节点平衡因子的定义为左右子树的高度差，一个树是AVL树和一个树的平衡因子只为0，-1，1为充要条件

当对AVL树进行插入时，插入的路径上的所有节点的平衡因子都要发生改变

在AVL树中插入一个节点导致原AVL树不再高度平衡时，我们根据插入节点的位置不同进行不同的旋转操作来保持AVL树的高度平衡

当插入一个节点导致AVL树高度不平衡，那么一定是插入的这个节点，导致了根节点的左右子树高度差大于二，我们需要调整这个高度变大的子树（不妨设为右子树），由于右子树原来也是一个AVL树，我们可以同样的缩小下去，直到找到最后一个平衡因子出现问题的节点，对以该节点为根的子树进行高度调整。

在插入节点后的维护时，因为我们要更新插入路径上的每一个节点的平衡因子，我们要做的就是，从插入的节点进行回溯，对每一个不平衡的节点根据情况进行旋转，具体情况如下

1. 如果插入的节点为不平衡节点的右子树的右子树（RR rotation）,那么对该子树进行单左旋
2. 如果插入的节点为不平衡节点的左子树的左子树（LL rotation）,那么对该子树进行单右旋
3. 如果插入的节点为不平衡节点的右子树的左子树（RL rotation）,那么对该不平衡节点的右子树先进行左旋，再对该不平衡节点为根的树进行左旋
4. 如果插入的节点为不平衡节点的左子树的右子树（LR rotation）,那么先对该不平衡节点的左子树进行左旋，再对该不平衡节点为根的树进行右旋

对于删除操作，从删除节点开始到根节点的路径也需要进行回溯，重新计算平衡因子，同时进行高度调整（旋转）

根据AVL树的高度，求最少的节点数量

假设树的高度给定，我们要求最少的节点数目。假设树的高度为$h$,根据高度平衡的定义，不妨设左子树的高度为$h-1$,因为我们要求的是最少的节点数量，所以右子树的高度为$h-2$，我们有如下的数量关系

树的节点等于左子树的节点，加上右子树的节点加1（根节点）。

这里直接给出结论

$F_{h+3}$表示第$h+3$个斐波那契数

Splay tree

splay tree（伸展树）是将每一个查询的节点调整到根节点，这样的作用是考虑到最近查询的数据再次查询时就会很快。

splay tree与AVL树的区别在于，splay tree不需要严格保证节点的高度平衡

splay tree通过伸展操作将目标节点调整到根节点的高度

我们设目标节点为X，该节点的父节点为P，P的父节点为G，按以下的方式进行伸展操作

1. 如果P为根节点，那么直接对这个树进行旋转，将X提升到根节点
2. 如果P不是根节点，那么按G,P,X这三个节点的分布情况进行操作
   • 如果为zig-zag（锯齿）分布，那么将X进行两次的旋转，使得G，P变成X的子节点
   • 如果为zig-zig（直线）分布，那么先对P进行一次旋转，再对X进行一次旋转，使得P成为X的子节点，G成为P的子节点

splay tree的删除操作流程如下

1. 找到删除的节点
2. 取出删除节点的左右子树
3. 找到左子树的最大节点作为根节点，该根节点的右子树直接连接原来的右子树（也可以找右子树的最小节点作为根节点）

摊还分析

红黑树

插入

所有插入的节点的颜色都设置为红色，只需要对红黑树的性质四（所有红色节点的孩子节点都是黑色）进行维护。

• 如果插入的节点是根节点，那么直接设置为黑色

• 如果红色插入的节点的父节点是黑色，那么可以直接插入，如果父节点是红色，那么观察叔叔节点

  • 如果叔叔节点是红色

    叔叔和父亲继承爷爷的黑色，都变成黑色节点，爷爷变成红色节点，然后以爷爷为插入节点，再继续进行插入的维护（如果爷爷节点的父节点是黑色，那么结束，为红色，继续观察爷爷节点的叔叔节点）

  • 如果叔叔节点是黑色

    判断插入节点的位置类型（LL,RR,LR,RL）

    • LL(或RR):先进行右旋，然后将插入节点的父节点变为黑色，祖父节点变为红色
    • LR(或RL):先调整到（LL或RR），这个时候，原本的插入节点与父节点旋转后交换了父子关系，转到第一种情况

删除

红黑树的删除首先是要将删除的节点替换为删除叶子节点或只有一个孩子的节点（右子树中最小的节点，同时这个节点有一个右孩子，或左子树的最大节点，同时这个节点有一个左节点）。对于有一个孩子的节点，这个节点的孩子节点一定是红节点，如果是黑色节点，那么就不满足红黑树的第五条性质 （从一个节点到所有叶子结点的路径上的黑色节点的数量都相同），所以可以直接将该节点与叶子节点的值替换，然后删除叶子节点。

所以只剩下删除叶子节点的问题，如果叶子节点是红色，那么可以直接删除，如果叶子节点是黑色，删除后就会破坏第五条性质，我们的问题就是维护这一性质不被破坏，我们将被删除的节点设定为二重黑色节点（简称双黑节点），双黑节点来源于，先保留这个节点本身的黑色，同时加上哨兵节点的黑色，我们的目标就是将双黑节点调整为单黑节点。

调整双黑节点首先看它的兄弟节点

• 兄弟为黑色

  • 兄弟至少有一个红色孩子

    • LL(或RR): 兄弟的孩子节点的颜色染成兄弟的颜色，兄弟的颜色变成父亲的颜色，父亲的颜色染成黑色，然后将s进行右旋调整的根节点的位置（以兄的的孩子为节点的LL rotation），然后将双黑节点变成单黑节点（RR型对称，方法一样）
    • LR(或RL):直接将兄弟节点孩子的颜色变为父亲节点的颜色，然后进行（LR rotation），先进行左旋，形成远侄子的情况，然后进行右旋，将侄子节点变为根节点，消除双黑节点（RL型方法相同，操作对称）

  • 兄弟的孩子都是黑色

    兄弟节点变成红色，双黑上移（两边子树都少了一个黑色，父节点多一个黑色，维护性质5，如果父节点是红色，那么直接将其变为单黑节点即可，如果父节点是黑色，那么将其变为双黑节点，然后对父节点进行双黑节点的维护（即进行兄弟节点的检查，如果是根节点，那么就直接变为单黑）

• 兄弟为红色

  兄弟节点交换颜色，然后朝双黑节点进行旋转，然后再对双黑节点进行维护