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

AVL树

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

AVL树的定义如下：

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

旋转

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

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

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

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

平衡因子

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

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

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

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

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

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

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

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

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

$n_h = n_{h-1}+n_{h-2}+1$

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

这里直接给出结论

$n_h = F_{h+3}-1,h\geq-1$

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

$F_{i}=\frac{1}{\sqrt{5}}(\frac{1+\sqrt{5}}{2})^{i}$

Splay tree

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

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

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

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

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

splay tree的删除操作流程如下

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

摊还分析

红黑树

插入

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

如果插入的节点是根节点，那么直接设置为黑色
如果红色插入的节点的父节点是黑色，那么可以直接插入，如果父节点是红色，那么观察叔叔节点
- 如果叔叔节点是红色
  
  叔叔和父亲继承爷爷的黑色，都变成黑色节点，爷爷变成红色节点，然后以爷爷为插入节点，再继续进行插入的维护（如果爷爷节点的父节点是黑色，那么结束，为红色，继续观察爷爷节点的叔叔节点）
- 如果叔叔节点是黑色
  
  判断插入节点的位置类型（LL,RR,LR,RL）
  - LL(或RR):先进行右旋，然后将插入节点的父节点变为黑色，祖父节点变为红色
  - LR(或RL):先调整到（LL或RR），这个时候，原本的插入节点与父节点旋转后交换了父子关系，转到第一种情况

删除

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

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

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

兄弟为黑色
- 兄弟至少有一个红色孩子
  - LL(或RR): 兄弟的孩子节点的颜色染成兄弟的颜色，兄弟的颜色变成父亲的颜色，父亲的颜色染成黑色，然后将s进行右旋调整的根节点的位置（以兄的的孩子为节点的LL rotation），然后将双黑节点变成单黑节点（RR型对称，方法一样）
  - LR(或RL):直接将兄弟节点孩子的颜色变为父亲节点的颜色，然后进行（LR rotation），先进行左旋，形成远侄子的情况，然后进行右旋，将侄子节点变为根节点，消除双黑节点（RL型方法相同，操作对称）
- 兄弟的孩子都是黑色
  
  兄弟节点变成红色，双黑上移（两边子树都少了一个黑色，父节点多一个黑色，维护性质5，如果父节点是红色，那么直接将其变为单黑节点即可，如果父节点是黑色，那么将其变为双黑节点，然后对父节点进行双黑节点的维护（即进行兄弟节点的检查，如果是根节点，那么就直接变为单黑）
兄弟为红色

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

左偏树（Leftist Heaps）

所有数据结构都有结构性和顺序性：

堆的结构性是每一个堆都是完全二叉树（除了最底层，其余每一层的节点数都是满的）
堆的顺序性（以最小堆为例），每一个节点的值都小于它的子节点

向堆中插入元素：

插入元素到堆尾，然后对堆尾元素进行上浮直到该节点大于父节点（对最小堆而言）

堆的查询和删除操作都是针对堆顶元素进行，删除堆顶元素时，将堆尾元素移到堆顶，然后对该元素进行下沉操作，（以最小堆为例），将该元素与子结点中最小的元素进行交换，如果子节点的元素都大于该节点元素或没有孩子节点，那么下沉结束。

合并（merge）两个堆：

将两个堆的元素打散合并后新建一个堆，时间是线性的

左偏树

顺序性和堆一样，结构性上比较特殊，不是完全二叉树也不是平衡二叉树

对于孩子数少于两个的节点称为外部节点，其余为内部节点。

NPL:从任意一个节点到外部节点的节点的最短距离。空节点的NPL为-1。

性质：对每一个节点计算NPL（null path length）,左儿子的NPL不能小于右儿子的NPL。

每一个节点的NPL的计算方法：

$NPL = min\{left(NPL),right(NPL)\}+1$

由上述性质可知，每一个节点的右路径一定是该节点到外部节点的最短路径，每一个左偏树的子树都是左偏树。

定理：如果一个左偏树右路径上有$r$个节点，那么这棵左偏树节点数至少为$2^r-1$

左偏树保证了右路径的最大长度有上界为$log(N+1)$向下取整，我们可以将需要进行的操作都在右路径上进行，保证了效率。插入操作是合并操作的一种特殊请况

左倾堆的合并（递归）

对于两个堆，将堆顶元素比较大的堆递归地插入到堆顶元素较小的堆。

例如，我们要合并两个堆$H_1$,$H_2$，先比较这两个堆的堆顶元素，将堆顶元素小的那棵树的堆顶元素和其左子树保留，递归地将堆顶元素较小的堆的右子树和另一个堆进行合并，将合并得到的新子树作为右子树，同时计算两颗子树的NPL，如果不满足左偏堆的要求，那么就交换左右子树，这样递归执行，直到一棵树为空时跳出递归。每一层递归都保证了堆的顺序性，由于没一个节点的左子树都是没有经过改动的左倾堆，每一个节点的右子树经过了合并，所以需要对右子树进行计算NPL和左子树比较，根据递归的原则，我们假定右子树已经保证了是一棵左倾树。

迭代

将两颗左偏树按照右路径上的节点分割为根节点加左子树，然后沿着大小顺序在右路径上进行合并，再对右路径上的所有节点进行自底向上的NPL计算，如果该节点左子树的NPL小于右子树的NPL，就交换左右子树。

删除

删除堆顶元素，然后合并两棵子树

斜堆（Skew Heaps）

在合并两个斜堆的时候，一定交换左右子树（除了右路径的最大元素）。不需要维护NPL。

斜堆的合并，只有right path上最大的节点才不需要交换左右孩子，其余的都需要交换

斜堆合并操作的均摊分析

定义重节点为，一个节点的右子树节点数多与左子树节点数，反之为轻节点

定义势能函数为堆中重节点的数量，在斜堆的合并过程中，我们对右路径上的节点不断进行递归合并，最坏情况为两条右路径上的节点都经过合并,我们定义一个堆的右路径上的节点数为$H_i = h_i+l_i(i=1,2)$,$h_i$为右路径上的重节点数量，$l_i$为右路径上的轻节点数量，$T_{worst} = l_1+l_2+h_1+h_2$,进行合并操作前$\Phi(D_i) = h_1+h_2+h$(h为合并过程中不会改变轻重性质的节点数量)，合并操作后$\Phi(D_{i+1})\leq l_1+l_2+h$,合并操作后最坏的情况为轻节点全部变成重节点，原来的重节点可以证明肯定全部变成轻节点了，所以总的时间开销为$T\leq T_{worst}+\Phi(D_{i+1})-\Phi(D_i)=2(l_1+l_2)$,$l_i\leq l=log(N)$。所以证明均摊时间为$O(log(N))$

斐波那契堆

斐波那契堆是一种可合并堆，可用于合并优先队列，比二项堆由更好的摊还分析性能，合并操作的时间复杂度是$O(1)$

和二项堆一样，斐波那契堆是一组堆最小有序树组成的，并且是一种可合并堆

和二项堆不同的是，斐波那契堆中的树不一定是二项树，而且二项堆中的树都是有序排列的，但是斐波那契堆中的树都是有根而无序的

节点定义

斐波那契堆的节点包含信息比较多，要保存节点的度，节点的左右兄弟，节点的第一个孩子，结点的父节点，节点是否被删除第一个孩子（marked）。

类定义

类内要保存当前堆的最小节点，堆中结点的总数，堆的最大度

插入操作

插入节点很简单，直接将该节点插入到根表的min节点之前就可以了，同时比较该节点是否比min节点小，如果小的话就对min进行更新。根表是一个双向循环链表，其中min被视为表头，由于双向循环链表的任意一个节点都可以被视作表头，所以min的更新只需要修改指针指向的节点位置就可以了。

合并操作

合并操作是将一个堆的根表插入到另一个堆的根表当中，就是将两个双向链表拼接成一个双向链表

取出最小节点

取出最小节点首先要将最小节点的子树都直接串联在根表中，其次要合并所有度相等的树，直到没有度相等的树。

取出最小节点后，先找到新的最小节点，然后将原来的最小结点的子树都添加到斐波那契堆中之后，移除原来的最小节点，同时新建一个cons堆，将原来斐波那契堆中的堆一个个添加到该堆中，在添加的过程中我们会进行比较，如果加入的堆和cons堆中的堆度相等，那么就将这两个堆进行合并，如果没有度相等的堆，那么就将这个堆正常插入到cons堆，将原来的斐波那契堆的所有堆都插入到cons堆后，合并cons堆当中度相等的堆，最后将cons堆得到的数据赋值给原来的斐波那契堆。

回溯

题目1

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

1 2	输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

我的解法

我自己想的backtracking的树是第i层是第i个位置的元素，然后第一层中，如果这个数字已经在之前排列过这个位置，那么就跳过这个数字不考虑，如果之前没有排列过，那么就将这个数字添加到已经被排列过的数字的vector中，然后进行递归。最后，如果输入的只有一个元素，直接将这个元素返回。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
    //记录已经遍历过的位置，比如第一个位置被遍历的元素就放在第一个vector里面，其余位置放在对应地vector里面
        vector<vector<int >> answer;
        if(nums.size() == 1){
            answer.push_back(nums);
            return answer;
        }
        vector<int> position_record;
        for(int i=0;i<nums.size();++i){
            vector<vector<int>> temp_answer;
            vector<int> temp = nums;
            auto it = find(position_record.begin(),position_record.end(),nums[i]);
            if(it != position_record.end()){
                continue;
            }else{
                position_record.push_back(nums[i]);
            }
            temp.erase(temp.begin()+i);
            temp_answer = permuteUnique(temp);
            for(auto& v:temp_answer){
                v.insert(v.begin(),nums[i]);
                answer.push_back(v);
            }
        }
        return answer;
    }
};

题目2

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

这道题没做出来，参考了官方题解

首先是先决条件判定，长度和应该为4的倍数并且最长的火柴应该小于等于边长，然后是进行回溯，这道题的回溯树不是很直观。我们以一个edges的vector来储存每一条边放的火柴长度，然后我们遍历所有的火柴（从大到小），假如我们把一根火柴放在一个edge中，如果放进这根火柴后，这一条边的长度大于正方形的边长，那么这种情况不成立，要进行回溯（将这根火柴取出来），如果不大于正方形的边长，那么这么放目前来看是可行的，那么接着判断剩下的火柴能不能成功放进去组成正方形（使用递归函数），如果可以，那么直接返回答案，不可以，那么这根火柴要进行回溯，最后的递归终点的判定条件是如果下标等于所有火柴的个数，那么证明所有火柴都放进正方形里了，直接返回true

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        sort(matchsticks.begin(),matchsticks.end());
        reverse(matchsticks.begin(),matchsticks.end());
        int sum = accumulate(matchsticks.begin(),matchsticks.end(),0);
        int edge = sum / 4;
        if(sum % 4 != 0 || matchsticks[0] > edge)
        return false;//如果最长的火柴棍都比边长长的话，肯定不能围成正方形（因为不能折断）
        //现在确保了，和为4的倍数，最长的棍子小于等于边长，选定边长为和除以4
        vector<int> edges(4);//表示目前拼了几条边
        int index = 0;
        bool ans = backtrack(matchsticks,edges,edge,0);
        return ans;
    }
    bool backtrack(vector<int> matchsticks,vector<int>& edges,int edge,int index){
        if(index == matchsticks.size())
            return true;//所有火柴都被取了
        for(int i = 0;i<edges.size();++i){
            edges[i] += matchsticks[index];
            if(edges[i] <= edge&&backtrack(matchsticks,edges,edge,index+1))
            return true;
            edges[i] -= matchsticks[index];
            if(edges[i] == 0)
            break;
        }
        return false;
    }
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

高级数据结构