数据结构

初识数据结构

算法的复杂度

栈与队列

排序与递归

哈希与矩阵

由一个或多个（n >= 0）节点组成的有限集合T，且仅有一个节点称为根（Root），当n > 1时，其余节点分为m（m >= 0）个互不相交的有限集合（T1、T2、T3。。。Tm）每个集合本身又是一棵树，常被称为根（Root）的子树。

定义

树的定义具有递归性质，即树中有树，最终成树。

特点

树的定义与特点

即根节点（没有前驱）

根

即终端节点（没有后继）

叶子

是指m棵互不相交的树的集合（例如没有根节点的子树其集合就被称为森林）

*森林

节点各子树（T1、T2、T3。。。Tm）从左至右有序，不能互换（左为第一）

*有序树

节点各子树可互换位置

*无序树

即上层的那个节点（直接前驱，parent）

双亲

即下层结点的子树（直接后继，child）

孩子

同一双亲下的同层节点（孩子之间互称兄弟，sibling）

兄弟

双亲位于同一层次的节点（非同一双亲，cousin）

堂兄弟

从根到该结点所经分支的所有节点

祖先

该节点下层子树中的任一节点

子孙

是指树的数据元素（个人理解：节点是常名，结点是变名，原因无他，数据元素是可变的，犹如const 和 let的声明，但都是同一个指引）

*结点

节点挂接的子树数（有几个直接后继就是几度，又可以看作有多少个孩子就有多少个度）

*节点的度

从跟到该节点的层数（根节点算第一层）

*节点的层次

度为0的节点（个人称其为断子绝孙的节点），如：叶子节点、没有度的根节点

*终端节点

除树根以外的节点（内部节点）

*分支节点

所有节点度中的最大值（Max{各节点的度}，拓展：数学表达式Max{}意为取括号里数列中最大的那个值）

*树的度

所有节点中最大的层数（Max{各节点的层次}）

*树的深度

外框

相关术语及名词解释

优点：寻找一个结点的双亲结点操作实现很方便

缺点：寻找一个结点的孩子结点很不方便

用指针表示出每个结点的双亲结点

双亲表示法

优点：寻找一个结点的孩子结点比较方便

缺点：寻找一个结点的双亲结点很不方便

用指针指出每个结点的孩子结点

孩子表示法

用指针既表示出每个结点的双亲结点，也表示出每个结点的孩子结点

双亲孩子表示法

表示出第一个结点的第一个孩子结点，也表示出每个结点的下一个兄弟结点

孩子兄弟表示法

树的存储结构

初识树

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成

概念

每个结点最多有两棵子树

二叉树的子树有左右之分，其次序不能颠倒

所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上

满二叉树

如果一棵具有N个结点的二叉树的结构与满二叉树的前N个节点 的结构相同，称为完全二叉树（特别说明：满二叉树是特殊的完全二叉树，而完全二叉树不一定是满二叉树）

完全二叉树

若规定根节点的层次为1，则一棵非空二叉树第n层上最多有2^（n-1）（n>=1）个结点，（^代表次方）

若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^ (n-1) (n>=0)，特别说明：这里的深度与上面的层次概念只不过是换一种的说法

如果i>1，则序号为i的结点的双亲结点的序号为i/2取整    如果i=1，则序号为i的结点为根节点，无双亲结点

如果2i<n，则序号为i的双亲结点的左孩子序号是2i右孩子序号是2i+1    如果2i>=n，则序号为i结点无右孩子结点

如果2i+1<=n，则序号为i结点的右孩子结点的序号为2i+1

如果2i+1>n，则序号为i结点无右孩子结点

具有n个结点的完全二叉树，如果按照从上至下从左到右的顺序对所有结点从1开始编号，则对于序号为i的结点有：

i满足2i <= n时，i必有左孩子且期序号为2i     i满足2i +1 >= n时，i必有右孩子且序号为2i+1

二叉树的性质

优点：存储完全二叉树，简单省空间，如上图

缺点：对一般二叉树尤其单支树，存储空间利用不理想，如上图

顺序存储（就是用一组连续的存储单元存放二叉树中的结点）

包含数据域和左右指针域的链表

链式存储（就是用链表来表示一棵二叉树，即用链来指示元素的逻辑关系）

二叉树的存储结构

依照顺序存储结构来创建（如上的存储结构所述）

依照链式存储结构来创建（如上的存储结构所述）

二叉树的创建

前序遍历（遵循先遍历双亲结点后再遍历左结点最后才遍历右结点的顺序，简称：中左右）打印的顺序为：12485367

中序遍历（遵循先遍历左结点后遍历双亲结点再最后才遍历右结点的顺序，简称：左中右）打印的顺序为：84251637

后序遍历（遵循先遍历左结点后遍历右结点再最后才后遍历双亲结点的顺序，简称：左右中）打印的顺序为：84526731

层序遍历（前面的都是深度优先而层级遍历则是广度优先）打印顺序为：12345678

二叉树的遍历

二叉树的基本操作

树之二叉树

按照二叉树的遍历将二叉树导成一个线性序列

线索化概念

递归遍历有可能导致栈溢出

非递归版本可能会降低程序的效率

想要找到某种遍历形式下某个节点的前驱还是后继比较难

树中有大量的空指针域造成浪费

普通二叉树可能存在的问题

定义：二叉树的结点加上线索后的的二叉树

线索二叉树

结点中指向前驱或者后继结点的指针

线索

作用区分是孩子结点还是前驱或者后继

线索标识位

当某结点的左指针为空时，令该指针指向按照某种方式遍历二叉树时得到该结点的前驱节点

当某结点的右指针为空时，令该指针指向按照某种方式遍历二叉树时得到该结点的后继结点

线索化过程

线索化二叉树

如图lchild和ltag分别代表左指针和左指针标识位、rchild和rtag分别代表右指针和右指针标识位、data代表当前结点数据，其中线索标识为则是ltag和rtag而线索则是遍历中那些没有左右孩子的指针即lchild和rchild，特别说明：一般地当ltag=0 时使得lchild指向左孩子；当ltag=1 时使得lchild指向直接前驱；当rtag=0 时使得rchild指向右孩子；当rtag=1 时使得rchild指向直接后继；

如图，先序遍历遵循中左右、中序遍历遵循左中右、后序遍历遵循左右中

如果左子树不为空，则左子树上所有节点的值都小于根结点的值

它的右子树不为空，则右子树上所有节点的值都大于根结点的值

它的左右子树也分别为二叉搜索树（或称：二叉查找树）

性质

根结点key==要查找的key，返回查找key对应的结点

根结点key>查找key，在其左子树查找

根结点key<查找key，在其右子树查找

否则返回null

若根结点不为空

例如查找32，第一次递归判定到了41 > 32所以对41的左子树进行查找，第二次递归判定到了32 > 20，再对20的右子树进行查找，第三次递归判定到了32 > 29再对29的右子树进行查找，第四次递归直接命中32，递归结束返回当前结点，如果查找不到的话就返回null

搜索

首先检测这个节点是不是已经存在，要是存在不插入（如果树的根节点为空则创建其为树的根节点），否则将元素插入到找到的位置

插入

插入的过程用到了搜索的原理（具体可用递归和非递归方法）

首先判断是否在树中，没有直接返回

直接删除该结点（如图需要删除的是key值为27的叶结点过程）

要删除的节点没有孩子节点

删除该结点并使被删除结点的双亲结点指向被删除结点的左孩子结点

要删除的节点只有左孩子

删除该结点并使被删除结点的双亲结点指向被删除结点的右孩子结点

要删除的节点只有右孩子

【H】结点是一个叶子结点的情况（如图需要删除的是key值为20的结点的过程）

【H】结点是一个非叶子结点的情况（如图依旧是需要删除的是key值为20的结点的过程）

加深理解图

需要找到这个节点的右子树上的最小结点【记为H】（因为它没有左子节点），把【H】替换到我们计划删除的节点上；然后，再删除这个最小的节点【H】（因为它没有左子节点，所以可以转化成之前的两种情况之一）。特别说明：找到某个节点的右子树上的最小结点就意味着这个最小结点是没有左子树的了，因为如果它还有左子树那就说明它还未是最小值故而还需要往左子树继续查找最小结点。

*要删除的节点有左、右孩子结点

有的情况

因为删除的节点只有一个子节点所以只需要更新父节点中的指向待删除结点的链接即可，让它指向待删除结点的子节点即可，所以无论是只有左孩子还是只有右孩子的情况处理逻辑都是一致的。(如图需要删除的是key值为50的结点的过程)

删除

最坏情况依旧是O(N)。二叉查找树在一定条件下可能会退化成链表，如图所示，这就是一个弯曲的链表。

对于二叉查找树来说，不管是插入、删除还是查找操作，时间复杂度都和树的高度成正比，也就是O(H)，因为每次操作都对应了一条从根节点向下的一条路径。而对于树的高度，却很可能因树的形状的不同而不同。

二叉搜索树性能分析

操作

二叉搜索树

上面说到二叉搜索树虽然可以提高我们查找数据的效率，但如果插入二叉搜索树的数据是有序或接近有序的，此时二叉搜索树会退化为单支树，在单支树当中查找数据相当于在单链表当中查找数据，效率是很低下的，因此两位俄罗斯的数学家（名字简称：G.M.Adelson-Velskii和E.M.Landis）在1962年发明了解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。故而AVL树又被称为平衡二叉树（Balanced Binary Tree）。

AVL树概念

它的左右子树都是AVL树

左子树和右子树高度之差（简称平衡因子）的绝对值不超过1（即整数值只有-1、0、1这三位兄弟）

如果一棵树是高度平衡的，它就是AVL树。如果它有n个节点，其高度可保持在0(lgn)，平均搜索复杂度O(lgn)，特别说明：这里所说的二叉搜索树的高度是平衡的是指：树中每个结点左右子树高度之差的绝对值不超过1，因为只有满二叉树才能做到每个结点左右子树高度之差均为0（而lgn是以10为底n的对数）

AVL树性质

AVL树的概念与性质

如图所示平衡因子的标记（如值为3对应的这棵子树来讨论，它的左子树高度为2右子树高度为1，按照右树高度-左树高度的规则故而它的平衡因子为1-2=-1。又如值为7对应的这棵子树来讨论，它的左子树高度为1右子树高度为2，按照右树高度-左树高度的规则故而它的平衡因子为2-1=-1，其他的标记由来雷同，而叶子结点的平衡因子一律为0）特别说明：此标记的计算公式不等同于如下讲述的内容，这里只是为了方便说明平衡因子的由来及定义

待插入结点的key值比当前结点小就插入到该结点的左子树

待插入结点的key值比当前结点大就插入到该结点的右子树

待插入结点的key值与当前结点的key值相等就插入失败

回顾一下二叉搜索树的插入规则

按照二叉搜索树的插入方法，找到待插入位置（如果是空树，插入后即为根结点）

找到待插入位置后，将待插入结点插入到树中

与二叉搜索树插入结点不同的是：AVL树插入结点后需要更新树中结点的平衡因子，因为插入新结点后可能会影响树中某些结点的平衡因子

由于一个结点的平衡因子是否需要更新，是取决于该结点的左右子树的高度是否发生了变化，因此插入一个结点后，该结点的祖先结点的平衡因子可能需要更新

新增结点在parent的右边，parent的平衡因子+ +（即自增1）

新增结点在parent的左边，parent的平衡因子− −（即递减1）

所以我们插入结点后需要倒着往上更新平衡因子，更新规则如右

如图新增的结点是祖先一的右孩子则需要让祖先一的平衡因子进行自增1操作，又因为祖先一结点又是祖先二结点的左孩子所以要让祖先二的平衡因子进行递减1操作，最后由于祖先二是根结点（即新增结点的祖先三）的左孩子所以根结点需要进行递减1操作，最终完成了一棵树的所有平衡因子的更新。特别说明：这里的往上更新是一种最坏情况的更新即都是发生在parent结点进行值操作后等于1或-1时（即自增或递减后平衡因子值为1或-1时）的前提下进行往上更新的，下面将进一步说明更新的判定。

如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子（说明新结点的插入使得parent的左子树或右子树增高了，即改变了以parent为根结点的子树的高度，从而会影响parent的父结点的平衡因子，因此需要继续往上更新平衡因子）

如果parent的平衡因子等于0，表明无需继续往上更新平衡因子了（说明新结点插入到了parent左右子树当中高度较矮的一棵子树，插入后使得parent左右子树的高度相等了，此操作并没有改变以parent为根结点的子树的高度，从而不会影响parent的父结点的平衡因子，因此无需继续往上更新平衡因子）

由于我们插入结点后需要倒着往上进行平衡因子的更新，所以我们将AVL树结点的结构设置为了三叉链结构，这样我们就可以通过父指针找到其父结点，进而对其平衡因子进行更新（三叉链结构如图所示）

将插入结点称为current（即也是代码中的指针），将其父结点称为parent（即也是代码中的指针），那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新则必定要执行current变为parent而parent变为parent的parent的逻辑。（高度总结就是指引在跑），特别说明：当parent的平衡因子为-2或2时，current的平衡因子必定是-1或1而不会是0。理由是：若current的平衡因子是0，那么current一定是新增结点，而不是上一次更新平衡因子时的parent，否则在上一次更新平衡因子时，会因为parent的平衡因子为0而停止继续往上更新，而current是新增结点的话，其父结点的平衡因子更新后一定是-1、0、1这三兄弟之一，而不可能是-2或2，因为新增结点最终会插入到一个空树当中，在新增结点插入前，其父结点的状态有以下两种可能：①其父结点是一个左右子树均为空的叶子结点，其平衡因子是0，新增结点插入后其平衡因子更新为-1或1。②其父结点是一个左子树或右子树为空的结点，其平衡因子是-1或1，新增结点插入到其父结点的空子树当中，使得其父结点左右子树当中较矮的一棵子树增高了，新增结点后其平衡因子更新为0。所以得出的结论就是当parent的平衡因子为-2或2时，cur的平衡因子必定是-1或1而不会是0

在更新平衡因子的过程当中出现了平衡因子为-2或2的结点时，我们则需要对以该结点为根结点的树进行旋转处理，而旋转处理分为四种，在进行分类之前我们首先需要进行分析

根据上述分析后我们可以将旋转处理分为四类，继下所述

如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理（说明此时parent结点的左右子树高度之差的绝对值已经超过1了，不满足AVL树的要求，因此需要进行旋转处理）

而每更新完一个结点的平衡因子后，都需要进行如右所描述的判断

更新平衡因子，如果出现不平衡，则需要进行旋转

AVL树的插入

如此进行下去，直到找到与待插入结点的key值相同的结点判定为插入失败，或者最终走到空树位置进行结点插入

演示图（parent的因子为2即值为10对应的结点的因子为2，而当前节点current就是值13对应的结点而它的平衡因子为1，故需要进行左单旋转）

左单旋（即当parent的平衡因子为2，current的平衡因子为1时）

演示图（parent的因子为-2即值为7对应的结点的因子为-2，而当前节点current就是值5对应的结点而它的平衡因子为-1，故需要进行右单旋转）

右单旋（即当parent的平衡因子为-2，current的平衡因子为-1时）

演示图（parent的因子为-2即值为7对应的结点的因子为-2，而当前节点current就是值5对应的结点而它的平衡因子为1，故需要进行左右旋转）

左右双旋（即当parent的平衡因子为-2，current的平衡因子为1时）

演示图（parent的因子为2即值为10对应的结点的因子为2，而当前节点current就是值13对应的结点而它的平衡因子为-1，故需要进行右左旋转）

右左双旋（即当parent的平衡因子为2，current的平衡因子为-1时）

平衡化旋转（依据上述分析进行演示）

所有情况旋转图

先找到待删除的结点

若找到的待删除结点的左右子树均不为空，则需要使用替换法进行删除

删除结点的方法和二叉搜索树相同

AVL树的删除

最坏情况下，删除结点后更新平衡因子时也会一路更新到根结点（如图）

找到实际需要被删除的结点后，先不进行实际的删除，而是先进行平衡因子的更新，不然后续更新平衡因子时特别麻烦。而更新平衡因子时的规则与插入结点时的规则是相反的，更新规则：①删除的结点在parent的右边，parent的平衡因子− −（递减1操作）。②删除的结点在parent的左边，parent的平衡因子+ +（自增1操作）。并且每更新完一个结点的平衡因子后，都需要进行三个判断：①如果parent的平衡因子等于-1或者1，表明无需继续往上更新平衡因子了（说明原来parent的左子树和右子树高度相同，现在我们删除一个结点，并不会影响以parent为根结点的子树的高度，从而变化影响parent的父结点的平衡因子，因此无需继续往上更新平衡因子）。②如果parent的平衡因子等于0，表明还需要继续往上更新平衡因子（说明本次删除操作使得parent的左右子树当中较高的一棵子树的高度降低了，即改变了以parent为根结点的子树的高度，从而会影响parent的父结点的平衡因子，因此需要继续往上更新平衡因子）。③如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理（说明此时parent结点的左右子树高度之差的绝对值已经超过1了，不满足AVL树的要求，因此需要进行旋转处理）。

更新完平衡因子后，我们再进行实际删除结点的操作，因为实际删除结点的左右子树当中至少有一个为空树，因此我们实际删除结点时的逻辑是：①若实际删除结点的左子树为空，则让其parent链接到实际删除结点的右子树，最后再删除结点即可。②若实际删除结点的右子树为空，则让其parent链接到实际删除结点的左子树，最后再删除结点即可。（注意：因为结点是三叉链结构，因此在链接结点的过程中需要建立两个结点之间的双向关系）

当parent的平衡因子为-2，parent的左孩子的平衡因子为-1时，进行右单旋

当parent的平衡因子为-2，parent的左孩子的平衡因子为0时，也进行右单旋

当parent的平衡因子为-2，parent的左孩子的平衡因子为1时，进行左右双旋

当parent的平衡因子为2，parent的右孩子的平衡因子为-1时，进行右左双旋

当parent的平衡因子为2，parent的右孩子的平衡因子为1时，进行左单旋

当parent的平衡因子为2，parent的右孩子的平衡因子为0时，也进行左单旋

而在进行删除旋转处理时，我们将其分为六种情况

与插入结点不同的是，删除结点时若是进行了旋转处理，那么在进行旋转处理后我们必须继续往上更新平衡因子，因为旋转的本质就是降低树的高度，旋转后树的高度降低了，就会影响其父结点的平衡因子，因此我们还需要继续往上更新平衡因子（特别说明：在情况三或情况六下，旋转后无需继续往上更新平衡因子，因为这两种情况旋转后树的高度并没有发生变化）

知识回顾：替换法删除指的是 让待删除结点左子树当中key值最大的结点，或待删除结点右子树当中值最小的结点代替待删除结点被删除，然后再将待删除结点的key值以及value值都改为代替其被删除的结点的值即可。（高度概括：最终找到的实际被删除的结点的左右子树当中至少有一个为空树）

AVL树

哈夫曼树是给定n个权值作为n个叶子结点（即也是n个度为0的根结点）进行构造的一棵二叉树，若该树的带权路径长度达到最小时则称这样的二叉树为最优二叉树则也称为哈夫曼树(Huffman Tree)

构造n棵只有根结点的二叉树森林，每棵二叉树都只有一个带有权值的根结点

在二叉树森林中选最小的两个，作为左右子树构建一棵新的二叉树，新二叉树的根结点的权值为左右子树根结点的权值之和

在原来二叉树森林里删除这两棵二叉树

把新的二叉树加入二叉树森林

重复步骤，直到F中只剩下一棵树

构造Huffman树

当前森林中最小的两个权值分别是G和F，将其作为一棵新二叉树的左右子树（默认规定权值小的为左孩子）

开始时的二叉树森林为集合{A、B、C、D、E、F、G}其对应权值如图所示

继续选取森林中权值最小的两棵树继续进行构造（即FG和C）

由于上步骤已完成了GF的二叉结合现二叉树森林集合为{A、B、C、D、E、FG}

继续选取森林中权值最小的两棵树继续进行构造（即FGC和E）

续上步骤则当前的二叉树森林为{A、B、D、E、FGC}

继续选取森林中权值最小的两棵树继续进行构造（即FGCE和B）

续上步骤则当前的二叉树森林为{A、B、D、FGCE}

继续选取森林中权值最小的两棵树继续进行构造（即A和D）

续上步骤则当前的二叉树森林为{A、D、FGCEB}

最终将森林中的最后两棵树进行构造（即AD和FGCEB）完成了一开始的所有森林树构造成一棵新的二叉树过程。特别地我们可以将所有左孩子线索一律标记为0而右孩子线索一律标记为1（此举将用于后续讲述哈夫曼编码过程所用）

最终当前的二叉树森林为{AD、FGCEB}

步骤演绎

在数据通信中经常把传输的文字转换成二进制字符0和1组成的二进制串，这叫做编码

什么是编码

在信息传输过程中，一个字母出现地越多，那么我们希望它越瘦小（编码短）这样占用的编码就越少，其实编码长的字母也是让频率比它多的字母把编码短的位子都占用后，它才去占用当前最短的编码。至此让总的编码长度最短，且要保证长编码的不与短编码的字母冲突（比如不能出现读码读到01还有长编码的字母为011，如果短编码为一个长编码的左起子串，这就是冲突，意思就是说读到当前位置已经能确定是什么字母时不能因为再读取一位或几位让这个编码能表示另外的字母）。

编码的问题

因为哈夫曼是从叶子节点开始构造，构造到根节点的，而且构造时，都是计算两个权值的节点的和再与其他叶子节点再生成一个父节点来组成一个新的树。并且不允许任何带有权值的节点作为他们的父节点。这也保证了所有带有权值的节点都被构造为了叶子节点。然后最后编码的时候是从根节点开始走到叶子节点而得出的编码。(高度总结：因为哈夫曼树的它的字母都在叶子节点上，因此不会出现一个字母的编码为另一个字母编码左起子串的情况)

在上述的构造哈夫曼树中生成对应的字符编码如图（每个字符的二进制编码为[从根节点 数到对应的叶子节点，路径上的值拼接起来就是叶子节点字母的应该的编码]）

那么哈夫曼树怎么避免左起子串问题呢？

哈夫曼编码

Huffman编码

Huffman树

B树

红黑树

堆

树结构

图结构

数据结构