3分钟速读原著《Java数据结构与算法》(三)

第六章 递归

1.小结

• 1.1 一个递归的方法每次用不同的参数值反复调用自身
• 1.2 某种参数值使递归的方法,而不再调用自身.这成为基值情况,也称为是递归算法的出口,递归算法必须要有出口,不然就会造成死循环
• 1.3 三角数字就是它本身以及所有比它小的数字的和.例如4的三角数组是10,因为4+3+2+1 =10
• 1.4 三角数字和阶乘都可以通过递归来实现
• 1.5 任何可以用递归完成的操作都可以用一个栈来实现
• 1.6 递归的方法可能效率很低,如果是这样的话,有时可以用一个简单的循环或者是一个基于栈的方法来替代它
• 1.7 二分查找法可以基于递归来进行实现,出口就是最终找到的那个值
• 1.8 分治算法:递归的二分查找法就是分治算法的一个例子,把一个大问题分成两个相对来说的更小的问题,并且分别解决每一个小问题,对每一个小问题的解决方法是一样的,这里有个前提就是对每个小问题的解决方法都是一样的,这种情况才能够实现递归,如果每次解决的方法是不一样的那么就无法实现递归的操作了
• 1.9 汉诺塔问题可以使用递归算法来解决
• 1.10 归并排序和递归算法
  • 归并排序的思想是把一个数组分成两个部分进行排序,排序完成之后再合并起来
  • 递归的思想则是不断的进行分裂,
  • 最终递归算法下的归并排序就是把一个数组不断的细分,最终变成两个数的比较,之后再不断的合并,直到合并成为一个,形成一个完整的排序.
  • 归并排序的效率相对简单排序当中的冒泡排序是比较高的

2.递归算法的一些实际应用

• 2.1 求一个数的乘方
• 2.2 背包问题:

假设一个背包有20磅重,并且有5个可以选择放入的数据项,它们的重量依次为11磅,8磅,7磅,6磅,5磅,当选择的数据量不大的时候,人类很善于通过观察就可以解决这个问题.于是可以计算出只有8磅,7磅,5磅的数据项加在一起和为20磅, 如果要把它设计成为一个算法指令,则:

• 2.2.1 如果在这个过程中的任何时刻,选择的数据项的总和符合目标重量,工作就完成了
• 2.2.2 从选择第一个数据项开始,剩余数据项的加和必须符合背包的目标重量减去第一个数据项的重量,这是一个新的目标重量
• 2.2.3 逐个的尝试每种剩余数据组合的可能性.但是,注意并不需要去试所有的组合,因为只要数据项的和大于目标重量的时候,就停止添加数据项
• 2.2.4 如果没有组合合适的话,放弃第一个数据项,并且从第二个数据开始重复一遍整个过程
• 2.2.5 继续从第三个数据项开始,如此下去直到你已经试过所有的组合,这时就知道没有解决答案

第七章 高级排序

1.希尔排序

希尔排序基于插入排序进行操作,迄今为止,除了在一些特殊的情况下,还没有人能够从理论上分析希尔排序的效率

• 1.1 希尔排序将增量应用到插入排序,然后组件缩小增量
• 1.2 n-增量排序表示每隔n个元素进行排序
• 1.3 被称为间隔序列或者间距序列的数列决定了希尔排序的排序问题
• 1.4 重用的间隔排序是有递归表达式h=3*h+1生成的,h的初始值为1

第八章 二叉树

树通常结合了另外两种数据结构的优点:一种是有序数组,另一种是链表,在二叉树当中查找数据项的速度和在有序数组当中查找一样的快,并且插入数据项和删除数据项的速度也和链表一样,二叉树则表示树当中最多只能有两个子节点,二叉树又分为了平衡二叉树和非平衡二叉树,平衡二叉树表示的就是树的两边的总量是相同的,非平衡二叉树则表示树的两边总量存在不同的情况,可能一边二叉树的子节点有多个,而另一边的二叉树子节点只有一个,像这种情况就称之为非平衡二叉树.

树的不平衡原因往往来源于插入的数据的不平衡,如果数据是随机插入的,这样相对的整棵树都会比较平衡一些,如果数据插入的时候是一味的升序或者一味的降序,那就会导致所有的数据都被分到了树的左边或者树的右边,这样就会导致整个树的不平衡的情况产生

1.小结

• 1.1 树是由边连接的节点组成
• 1.2 根是树当中最顶端的节点,它没有父节点
• 1.3 二叉树当中,每个节点最多有两个子节点
• 1.4 二叉搜索树当中,所有A节点左边子孙节点的关键字都比A小,所有右边子孙节点的关键字值都大于或者等于A
• 1.5 树执行查找,插入,删除的时间复杂度都是O(logN)
• 1.6 节点表示的是保存在树当中的数据对象
• 1.7 程序当中通常用节点到子节点的引用来表示边
• 1.8 遍历树是按照某种顺序访问树种所有的节点
• 1.9 最简单的遍历方法是前序,中序和后序
• 1.10 非平衡树是指根左边的后代比右边的多,或者相反
• 1.11 查找节点需要比较要找的关键字值和节点的关键字值,如果要找的节点关键值小,就转向那个节点的左子节点,如果大就转向右子节点
• 1.12 插入需要找到要插入的新节点的位置改变它的父节点的子字段来指向它
• 1.13 中序遍历按照关键字升序访问节点
• 1.14 前序和后序遍历对解析代数表达式是有用的
• 1.15 如果一个节点没有子节点,删除它只要把它的父节点的子字段设置为nul,xml本身也类似于解析这样的一个document的树
• 1.16 如果一个节点有一个子节点,把它父节点的子字段设置为它的子节点就可以删除它
• 1.17 如果一个节点有两个子节点,删除它需要用它的后继来替代它
• 1.18 A节点的后继是以A的右子节点为根的子树中关键值最小的那个节点
• 1.19 哈夫曼树是二叉树,但不是二叉搜索树,用于数据压缩算法

第九章 红黑树

在前面一章当中我们学到了二叉搜索树,它具有查询快,插入和删除也很快的特性,算是一个非常不错的数据存储结构了,但是二叉搜索树的缺点就是如果树插入的是随机数据,那么执行效果会很好,但是面对一些如果单纯的有序数据,就会导致二叉树缺失平衡,最终导致插入和删除以及查询都变得很慢了,红黑树就是用于去解决这个问题的

1.红黑树的特征

• 1.1 节点都有颜色
• 1.2 在插入和删除的过程中,要遵循保持这些颜色的不同排列的规则
• 1.3 在红黑树当中,每一个节点都是黑色的或者是红色的,也可以是任意的两种颜色,蓝色多和黄色也是可以的,实际上,所说的节点有颜色是任意的彼方.可以使用其他类似的方法来表示,比如可以说每个节点不是深色就是浅色的,或者说不是阴就是阳,简单来说就是比二叉搜索树多了一个判断标准来保持树两边的平衡,从而提升树的性能
• 1.4 红黑树的规则

当插入或者删除一个新节点的时候,必须要遵循一定的规则,他们被称为红黑-规则,如果遵循这些规则,那么树就是平衡的,规则如下

• 1.4.1 每一个节点不是红色就是黑色的
• 1.4.2 根总是黑色的
• 1.4.3 如果节点是红色的那么它的子节点必须是黑色的,反之不一定成立
• 1.4.4 从根到叶节点或空子节点的每条路径,都必须包含相同数目的黑色节点
• 1.5 修正违规的情况

假若颜色的规则被违反了,遵循以下规则进行修正

• 1.5.1 改变节点的颜色
• 1.5.2 执行旋转操作

2.红黑树的效率

和一般的二叉搜索树类似,红黑树的查找,插入和删除的时间复杂度是相同的,在红黑树中的查找时间和在普通二叉搜索树的时间几乎完全一样,区别仅在于在每个节点当中需要增加一点储存空间来储存红黑树的颜色

3.小结

• 3.1 保持二叉树的平衡是非常重要的,这样可以使得找到给定节点是所必须的时间尽可能的短
• 3.2 插入有序的数据将创建最不平衡的树
• 3.3 在红黑平衡的方法中,每个及诶单都有一个新的特征,它的颜色不是红的就是黑的
• 3.4 当插入或者删除一个节点时都需要应用红黑树的规则
• 3.5 一次颜色变换把一个黑色节点和它的两个红色子节点改成一个红色节点和两个黑色子节点
• 3.6 在一次旋转中,指定一个节点为顶端节点
• 3.7 右旋把顶端节点移动到它的右节点的位置,并把顶端节点的左子节点移动到顶端节点的位置
• 3.8 左旋把顶端节点移动到它的左子节点的位置,并且把顶端节点的右子节点移动到顶端节点的位置
• 3.9 当顺着树乡下查找新节点的插入位置时,应用颜色变换,并且有时应用旋转,颜色变换通过简单的方法,使得树在插入后恢复称为正确的红黑树
• 3.10 新节点插入之后,再次检查红红冲突,如果发现有违背红黑规则的现象,执行适当的旋转使得树恢复红黑正确性
• 3.11 在二叉树中加入了红-黑平衡对平均执行效率只有很小的负面影响,然而却避免了对有序的数据操作的最欢的性能