数据结构和算法分析-数据结构

摘要

表、栈、队列、树、Hash等数据结构

表、栈、队列

树

二叉树

二叉树每一个节点都不能有多于2个儿子

二叉树的一个性质是一棵平均二叉树的深度要比节点个数N小的多，其平均深度为O（根号N），而对于特殊类型的二叉查找树，其深度的平均值时O(log N)

二叉查找树

定义：对于书中的每个节点X 它的左叶子树的值都小于X中的项，而右侧的项都比X中的项大

单调性：BST的中序遍历，必然单调非降（充要条件）

完全二叉树：高度严格最小 ：logN

最困难的操作是remove，删除有几种可能：

  1. 如果节点是树叶，那么它可以被直接删除

  2. 如果节点有一个儿子，则该节点可以在其父类节点做出调整，跳过直接的链绕过该节点

  3. 复杂情况是处理具有两个儿子的节点，一般的删除策略是用其右子树的最小的数据代替该节点的数据并递归的删除那个节点

懒惰删除 ： 当一个元素要被删除时，它任然留在树中，只是被标记为删除（耗时小，其次下次如果插入相同数据时，可以避免重新分配一个新单元）

平均情况分析

我们期望所有操作花费时间都是O（log N）、

多有操作允许时间都是O（d）,d为访问节点的深度

一棵树的所有节点的深度被称为内部路径长

正常删除算法使得 左树的深度要比右树的深度深（删除时将右子树最小的节点代替该节点）

理想平衡：n个节点，高度为logn；概率极低，成本高

等价的BST：上下可变，左右不能乱

等价的BST中序遍历相同，拓扑排序不同

BBST平衡二叉搜索树
AVL树

定义：

平衡因子：左右子树高度差

平衡因子不大于+／-1；

叶子的平衡因子为-1；

时间：

插入 O（1）

结构：

AVL树的高度略大于log N，除去可能的删除了懒惰删除外，所有操作都可以以时间O(log N)执行

假如插入一个树破坏平衡：

不平衡可能有4种情况

  1. 对X的左子树的左儿子进行一次插入

  2. 对X 的左子树的右儿子进行一次插入

  3. 对X的右子树的左儿子进行一次插入

  4. 对X 的右子树的右儿子进行一次插入

1 和 4 2 和 3 关于 X 对称

第1种情况和第4种情况，该情况通过对树进行一次单旋转而完成跳转

对于第2种和第3中情况来说 需要对树进行双旋转完成

4.4.1 单旋转**

将左子树上调作为父子树，将父子树调为右子树。左子树的右节点调整到右子树的左节点

4.4.2 双旋转**

将左子树的右节点上调至父子树，左子树的右节点上调至父子树的左子树调至左子树的左节点的右子树 将左子树的右节的右子树调至右子树的左节点

红黑树

定义：

根：黑色

外部节点：黑

其余节点：若红，其父节点和子节点必然为黑

黑节点的数量一样

等效于4阶B树

B树

伸展树

定义：

当一个节点别访问后，它就要经过一系列AVL树的旋转被推倒根上。适合于重复访问的元素使用

当访问路劲长而且导致超出正常查询时间的时候，这些旋转将对未来有利，当访问耗时很少的时候，这些旋转就不那么有益

时间：

它保证从空树开始连续M此对树的操作最多花费 O(Mlog N)时间，虽然不排除单次操作花费O(N)时间

堆

二叉堆

  1. 定义：被完全填满的二叉树。
  2. 结构：

堆的父节点一定 <= 子节点。

完全填二叉树，有可能的例外是在底层，底层上的元素从左到右填入

一棵树高为h的完全二叉树有2h 到2h+1 -1 个节点 这也意味着完全二叉树的高是log N 显然它是O（log N）

对于数组上任意的 i 上的元素，其左儿子在位置2i上，右儿子在做儿子后的单元（2i + 1）上 它的父亲则在（i/2）上

这种方法的最大问题在于 最大的堆的大小需要事先估计，但一般都不成问题

一个堆的结构将由一个（Comparable对象的）数组和一个代表当前堆的大小的整数组成

  1. 时间：

生成二叉堆 O（N）

deleteMin O（log N）

  1. 实现：

insert 采用的策略叫做上滤，在下一个可用的位置创建一个空穴，然后比较父类是否比他小，大则上滤

deeteMin 采用的策略叫做下滤 删除根元素，并填充空穴，然后将最堆中最后一个元素放入空穴中，将空穴和子元素比较

我们必须保证节点只有一个儿子的前提下程序正确执行

d-堆

定义：d-堆是二叉堆的简单推广，它就像一个二叉堆，只是所有节点都有d个儿子（因此二叉堆 又是 2堆）

时间：d-堆要比二叉堆浅的多，它将insert操作时间的运行时间改进为O(logd N) 然而，对于大的d deleteMin操作费时的多。以为d个儿子中必须找出一个最小者（d-1此比较）于是将用时提高到O（d logd N）

优缺点：当优先队列太大而不能装入主存时，d-堆也是很有用的

除了不能实现find外，堆实现的最明显的缺点是 将两个堆合并和一个堆是一个困难的操作 ，这种操作叫做合并。

存在许多实现堆的方法使得一次merge操纵的运算时间是O(log N)

左堆

像二叉堆那样也具有结构性和有序性 左式堆和二叉堆都是二叉树，唯一区别是左式堆不是理想平衡的，实际上趋向非常不平衡

性质

我们把任一节点X的零路径长定义为从X 到一个不具有两个节点的最短路径长，

左式堆性质是 对于堆中的每一个节点，左儿子的零路径长 大于等于 右儿子的零路径长（它显然偏重于使树的想左增加深度）

在右路径上右R个节点，那么左式树必然有 2R- 1个节点

操作

对左式堆的基本操作时合并，注意插入只是合并的特殊情景。因为我们可以把插入看成是单节点 的堆与一个大堆的merge

处理验证数据 左引用和右引用所用的空间外，每一个节点还要有一个指示零路径的项

根值大的堆与根值小的堆的右子堆合并，若出现不零路径满足情况，将左子堆和右子堆交换

斜堆

斜堆是左手式堆的自调形式，实现起来极其简单，斜堆和左手式堆类似于伸张树和AVL树间的关系，

斜堆具有二叉堆的性质，但是不存在堆树的结构限制。

不同于左式堆，关于任意节点的零路劲信息不在保留，斜堆的有路劲子啊任何时刻都可以任意长

时间： 最坏运行时间是O(N) 总的最坏运行时间是O（M log N）

二项队列

结构：

是堆序树的集合，每一个高度上至多存在一棵二项树。

如果是连续的树，后面一棵树就是前面一棵树复制一份再连接两个树的根。

高度为K的二项树恰好有2k个节点

时间：

总共存在O（log N）棵二项树

每次操纵的最坏情景运行时间为O（log N），

插入平均花费常数时间，最坏花费O（N）

findMin的时间为 O（log N）

merge最多花费O(log N)

实现：

二项树的每一个节点将包含数据，第一儿子以及右兄弟。

二项树中各个儿子以降秩次序排列

deleteMin 二项队列H删除含有最小根的B得到H’，B删除最小根等到一个二项队列H’’，合并H’和H’’。

combine 两棵二项树中，小树的儿子➡赋值给➡大树右兄弟，大树➡赋值给➡小树的儿子。返回小树。

merge

遍历

先序遍历 ：在先序遍历中，对节点的处理工作是在它的诸多儿子节点被处理之前进行的运行时间为O(N)

后序遍历 ：在后序遍历中，一个节点处的工作是在它的诸儿子节点被计算后进行的

Hash

散列一般保证表的大小是素数

如果是2的r次幂，则hash取余均为二进制的后r个，前面的数字失效

普遍情况来说，如果N取模M，N和M有公约数k，则本来N=rM+A，（r和A随意），现在N/k=rM/k+A/k。

对于余数A/k来说，取值是1～M-1，但是其实每个数字是以k为倍数增加的，余数有数字为被映射到。

方便起见，取素数为模，避免公约数。

冲突

分离链接法

开放地址法

再Hash

建立另外一个大约两倍大的表（使用一个相关的新散列函数），扫描整个原始散列表，计算每个元素的新散列值并将其插入到新表中；

显然这是一种非常昂贵的操作， 其运行时间为 O(N)，因为有N 个元素要再散列而表的大小约为2N， 不过由于不是经常发生，所以实际效果根本不是那么差

什么时候使用：

对于使用平方探测的开放定址散列法，如果表的元素填的太满， 那么操作的运行时间将开始消耗过长，且 insert 操作可能失败， 这可能发生在有 太多的移动和插入混合的场合；把程序员从表大小的担心中解放出来， 这一点很重要， 因为在复杂的程序中散列表不能够做得任意地大；

实现：

再散列可以用平方探测以多种方法实现：

1）一种做法是：只要表满到一半就再散列；

2）另一个极端方法是：只有当插入失败时才再散列；

3）第3种方法即途中策略：当表到达某一个装填因子时进行再散列。由于随着装填因子的增加，表的性能有所下降， 因此，以好的截止手段实现的第三种策略， 可能是最好的策略；

Comments

comments powered by Disqus