关键词：

20172313 2018-2019-1 《程序设计与数据结构》第七周学习总结

教材学习内容总结

• 概述
  • 二叉查找树：二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，而父结点又小于或等于右孩子。二叉查找树的定义是二叉树定义的扩展。
  • 二叉查找树的各种操作

操作	说明
addElement	往树中添加一个元素
removeElement	从树中删除一个元素
removeAllOccurrences	从树中删除所指定元素的任何存在
removeMin	删除树中的最小元素
removeMax	删除树中的最大元素
findMin	返回一个指向树中最小元素的引用
findMax	返回一个指向树中最大元素的引用

• 用链表实现二叉查找树：每个BinaryTreeNode对象要维护一个指向结点所存储元素的引用，另外还要维护指向结点的每个孩子的引用。
• addElement操作：我们只要利用二叉查找树的特性（即对每个父结点，它的左子树中所有项的值小于父结点中的值，而它的右子树中所有项的值都大于T中的值），找到只对应的插入位置即可，如果树为空，则这个新元素就将成为新结点，如果树非空，沿着树查找（根据element的大小来判断向左还是向右）。假如我们现在要插入element为4的结点，如果找到element(4),则什么也不做，否则将element插入到遍历的路径上的最后一个点，如下图所示：
  
• removeElement操作：对于二叉查找树来说，删除元素的时候要考虑三种情况：
  • ①如果要删除的结点q恰好是叶子结点，那么它可以立即被删除
  • ② 如果要删除的结点q拥有一个孩子结点，则应该调整要被删除的父结点(p.left 或 p.right)指向被删除结点的孩子结点（q.left 或 q.right）
  • ③如果要删除的结点q拥有两个孩子结点，则删除策略是用q的右子树的最小的数据替代要被删除结点的数据，并递归删除用于替换的结点(此时该结点已为空)，此时二叉查找树的结构并不会被打乱，其特性仍旧生效。采用这样策略的主要原因是右子树的最小结点的数据替换要被删除的结点后可以满足维持二叉查找树的结构和特性，又因为右子树最小结点不可能有左孩子，删除起来也相对简单些。
    
• removeAllOccurrences操作：可以看做调用了removeElement,当在树中找不到指定元素是，则抛出ElementNotFoundException异常，如果指定的元素不是Comparable，则removeAllOccurrences方法也会抛出ClassCaseException异常。只要树中还含有目标元素，就会再次调用removeElement方法。

    public void removeAllOccurrences(T targetElement)
            throws ElementNotFoundException
    
        removeElement(targetElement);

        try
        
            while (contains((T)targetElement))
                removeElement(targetElement);
        

        catch (Exception ElementNotFoundException)
        
        
    

• removeMin和removeMax操作：对于findMin()，则需要从根结点开始并且只要有左孩子就向左进行即可，其终止点即为最小值的元素；而对于findMax()，也需要从根结点开始并且只要有右孩子就向右进行即可，终止点即为值最大的元素。
  
• 用有序列表实现二叉查找树：add操作和remove操作都可能导致树变得不平衡。

操作	说明	LinkedList	BinarySearchTreeList
removeFirst	删除列表的首元素	O(1)	O(logn)
removeLast	删除列表的末元素	O(n)	(logn)
remove	删除列表中的一个特定元素	O(n)	O(logn)*
first	考察列表前端的那个元素	O(1)	O(logn)
last	考察列表末端的那个元素	O(n)	O(logn)
contains	判断列表是否含有一个特定元素	O(n)	O(logn)
is Empty	判定列表是否为空	O(1)	O(1)
size	判定列表中的元素数目	O(1)	O(1)
add（有序列表特有）	向列表添加一个元素	O(n)	O(logn)*

• 平衡二叉查找树：如果没有平衡假设，最坏情况下addElement操作的实践复杂性是O（n）而不是O（logn），因为可能存在树根是树中的最小元素，而将被插入的元素可能是树中的最大元素，这种情况下，它的效率比链表的还低，因为每个结点还附带额外的开销。
  
• AVL树的旋转：当一棵树的最大路径长度大于log2^n，或最小路径长度小于log2^n-1时，就要平衡化该树。对于AVL树，树中的每一个结点，我们都会跟踪其左右子树的高度。对于树中的任何结点，如果其平衡因子（左右子树的高度差）大于1或小于-1，则以该节点为树根的子树需要重新平衡。
  
• 上左图是一棵平衡二叉树，它每个结点的左子树和右子树的高度最多相差1，它同时也是一棵二叉查找树，而上右图虽然也是一棵二叉查找树，但是它每个结点的左子树和右子树的高度相差为2，所以它不是平衡二叉树。当引起结点数量变化时，即进行删除和插入操作，如下图，插入一个新的结点，原本的平衡二叉树就失去了平衡。
  
• 既然二叉树失去了平衡，我们就要使用适当的操作来使它恢复平衡。如果某结点的平衡因子为-2，左孩子的平衡因子是-1，这就意味着该结点的左子树中有一条过长的路径，所以应该采用右旋。在原始AVL树插入7结点后，结点9变为失衡点，树再满足AVL性质，因此需要对9结点进行左左单旋转(即向右旋转)后，得到下右图，我们发现此时并没有操作树的根结点(6)，实际上这是因为正常情况下，不必从树的根结点进行旋转，而是从插入结点处开始，向上遍历树，并更新和修复在这个路径上的每个结点的平衡及其平衡信息(高度)即可。（左旋类似，当某结点的平衡因子是+2，右孩子的平衡因子是+1的时候使用左旋，左旋中的“左”，意味着“被旋转的结点将变成一个左结点”。右旋同理）
  
• 当某结点的平衡因子是+2，如果其右孩子的平衡因子是-1，这时子树太“深”了，无论是左旋还是右旋，都无法使操作后的数成为AVL树，这个时候就需要使用双旋，首先让出初始结点右孩子的左孩子，绕着初始结点的右孩子进行一次右旋，然后再让初始结点的右孩子，绕着初始结点进行一次左旋。（左右旋类似，当某结点的平衡因子是-2，左孩子的平衡因子是+1的时候使用左右旋）
  
• 红黑树
  • 树中的每一个结点都储存着一种颜色（红色或黑色，通常使用一个布尔值来实现，值false等价于红色）。
  • 根结点为黑色。
  • 每个叶子结点（null）是黑色。（**注意：这里的叶子结点，是指为空(null)的叶子结点！）
  • 从树根到树叶的每条路径都包含有同样数目的黑色结点。
  • 如果一个结点的颜色为红色，那么它的子结点必定是黑色。
  • 在红黑树中，元素的查找仍然是一种O(n)操作，由于红色结点不能有红色孩子，于是路径中至多有一半结点时红色结点、至少有一半结点是黑色结点，据此我们可以论证红黑树的最大高度约为2*logn，于是遍历最长路径的序仍然是logn。
    
• 红黑树的添加操作：红黑树本身就是一棵二叉查找树，所以当添加元素或删除元素后，我们仍然需要使所得到的是一棵二叉查找树，这就使得我们要对红黑树进行重新着色。我们先来回头看上面所说的红黑树的性质，如果要保证从树根到树叶的每条路径都包含有同样数目的黑色结点，那么我们把插入的元素设置为红色，就可以保持，接下来我们只需从该结点向上遍历，保证红色结点的子结点必定为红色即可满足红黑树的所有要求。我们把要插入的结点设置为红色，那么根据父结点的颜色又可以分为三种情况。
  • ①被插入的结点是根结点。（我们可以直接将该结点涂成黑色）
  • ②被插入的结点的父结点是黑色。 （我们无需进行操作，插入之后仍为红黑树）
  • ③被插入的结点的父结点是红色。（我们对该种情况要进行着重讨论，因为被插入的结点的父结点是红色，所以该结点的祖父结点必定存在（即父结点的父结点），父结点的兄弟结点也必定存在。（即“叔叔”结点，即使叔叔结点为空，我们也视之为存在，空结点本身就是黑色结点）我们根据叔叔结点的颜色又可以分成三种情况）

情况	处理方式
当前结点的父结点是红色，且当前结点的祖父结点的另一个子结点（叔叔结点）也是红色。	①将“父结点”设为黑色。 ② 将“叔叔结点”设为黑色。 ③ 将“祖父结点”设为“红色”。 ④ 将“祖父结点”设为“当前结点”(红色结点)；指针current由指向插入的结点变为“当前结点“”，之后继续对“当前结点”向上进行操作。
当前结点的父结点是红色，叔叔结点是黑色，且当前结点是其父结点的右孩子	①将“父结点”作为“新的当前结点”。 ②以“新的当前结点”为支点进行左旋。
当前结点的父结点是红色，叔叔结点是黑色，且当前结点是其父结点的左孩子	① 将“父节点”设为“黑色”。 ②将“祖父节点”设为“红色”。 ③以“祖父结点”为支点进行右旋。

• 如上图介绍了如何进行操作，下面我们再来谈谈为什么要这么操作。
  • 第一种情况，由于红色结点的子结点不能是红色，所以我们把父结点要变为黑色，但当我们把父结点变为黑色以后，从树根到树叶之间的黑色结点的个数就不相等了，所以把祖父结点变为红色，同样的，因为红色结点的子孩子不能是红色，所以要把叔叔结点变为黑色。祖父结点一定是黑色吗？答案是肯定的，因为在元素添加之前，该二叉树就是红黑树，父结点是红色的，那么祖父结点一定是黑色的。按照上述步骤处理之后，当前结点，父结点，叔叔结点都满足了红黑树的性质。若此时，祖父结点是根结点，直接将祖父结点设为“黑色”，那就完全解决这个问题了；若祖父结点不是根结点，那我们需要将“祖父结点”设为“新的当前结点”，接着对“新的当前结点”进行分析。
  • 第二种情况，我们在上面表中说到，要以父结点为支点进行左旋，那么为什么要进行左旋呢？处理红黑树的核心思想：将红色的节点移到根节点；然后，将根节点设为黑色。新插入的结点为红色，破坏了整棵红黑树，所以我们要通过左旋来将它上移。上移之后，如果该结点变成了根结点，那么直接把它涂成黑色，若该结点不是 根结点，那么我们需要对父结点进行操作（在下图中也就是40） ，为什么不直接对60的当前结点进行操作，而是转而处理原来的父结点40呢？因为通过左旋之后，原来的父结点（40）变成了子结点（60）的子结点，而处理红黑树的时候需要从下往上处理，所以要先对40的结点操作。
    
  • 第三种情况，当按照上图第二种情况左旋后，就变成了下面这种情况。由于（40）和（60）两个结点都是红色，所以我们可以先把（60）结点变为黑色，但变为黑色的话，由根结点经过（60）结点的路径黑色结点数就会增加，所以我们可以让（60）的父结点（即（80））变为红色，并以该父结点作为支点进行右旋。
    
• 红黑树的删除操作：红黑树的删除和常规二叉树删除元素的操作一样，也分为三种情况。
  • ①被删除的结点没有子结点（即叶子节点），直接将该结点删除。
  • ②被删除的结点有一个子结点，将该结点删除，并让父结点指向该结点的子结点。（可以看前文的示意图）
  • ③被删除的结点有两个子结点，用该结点的右子树的最小的数据替代要被删除结点的数据，并递归删除用于替换的结点。（前文有，在此不再过多赘述）
• 在删除结点的时候，我们先来想一下所删结点的位置，如果删除的是根结点，那么根结点就可能不为黑色，如果它有子结点，删除后可能会导致红色结点的子结点有红色结点还有可能会导致从根到各个路径的黑色结点的数量不同。我们就来解决上面上说的这些问题。

教材学习中的问题和解决过程

• 问题一：在学习教材的时候，p225的代码中有这样一行判断条件“(！(element instanceof Comparable))”,不是很理解这行代码的意思。
• 问题一解决方法：原来是学习过的，时间久了有些忘记。java 中的instanceof 运算符是用来在运行时指出对象是否是特定类的一个实例。instanceof通过返回一个布尔值来指出，这个对象是否是这个特定类或者是它的子类的一个实例。用法：result = object instanceof class参数：Result：布尔类型。Object：必选项。任意对象表达式。Class：必选项。任意已定义的对象类。说明：如果 object 是 class 的一个实例，则 instanceof 运算符返回 true。如果 object 不是指定类的一个实例，或者 object 是 null，则返回 false。 举例：

interface A
    class B implements A

    
    class C extends B 

    

    class instanceoftest 
        public static void main(String[] args)
            A a=null;
            B b=null;
            boolean res;

            System.out.println("instanceoftest test case 1: ------------------");
            res = a instanceof A;
            System.out.println("a instanceof A: " + res);

            res = b instanceof B;
            System.out.println("b instanceof B: " + res);

            System.out.println("/ninstanceoftest test case 2: ------------------");
            a=new B();
            b=new B();

            res = a instanceof A;
            System.out.println("a instanceof A: " + res);

            res = a instanceof B;
            System.out.println("a instanceof B: " + res);

            res = b instanceof A;
            System.out.println("b instanceof A: " + res);

            res = b instanceof B;
            System.out.println("b instanceof B: " + res);

            System.out.println("/ninstanceoftest test case 3: ------------------");
            B b2=(C)new C();

            res = b2 instanceof A;
            System.out.println("b2 instanceof A: " + res);

            res = b2 instanceof B;
            System.out.println("b2 instanceof B: " + res);

            res = b2 instanceof C;
            System.out.println("b2 instanceof C: " + res);
        
    

• 问题二：在学习红黑树的时候，书上提到终止迭代的条件也可以是“current.parent.color == black”，子树的结点不也可以是黑色的吗？为什么判断当前结点的父结点的颜色就可以终止迭代了呢？

代码调试中的问题和解决过程

• 问题1：在做编程项目pp9_3的时候，不知道怎么计算程序的执行时间。
• 问题一解决方案：

一般输出日期时间经常会用到Date这个类：

 SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");//设置日期格式
 System.out.println(df.format(new Date()));// new Date()为获取当前系统时间

（1）以毫秒为单位计算
  static long currentTimeMillis() ， 该方法返回值是从1970年1月1日凌晨到此时刻的毫秒数
  
 long startTime=System.currentTimeMillis();   //获取开始时间
 doSomeThing();  //测试的代码段
 long endTime=System.currentTimeMillis(); //获取结束时间
 System.out.println("程序运行时间： "+(end-start)+"ms");

（2）以纳秒为单位计算
 long startTime=System.nanoTime();   //获取开始时间
 doSomeThing();  //测试的代码段
 long endTime=System.nanoTime(); //获取结束时间
 System.out.println("程序运行时间： "+(end-start)+"ns");

代码托管

（statistics.sh脚本的运行结果截图）

上周考试错题总结

??这周没有错题哦~

结对及互评

• 参考示例

点评过的同学博客和代码

• 本周结对学习情况
  • 结对同学学号1
  • 结对照片
  • 结对学习内容
    • XXXX
    • XXXX
    • ...
• 上周博客互评情况
  • 学号1
  • 学号2
  • 学号3
  • 学号4
  • ...

其他（感悟、思考等，可选）

xxx
xxx

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	5000行	30篇	400小时
第一周	200/200	2/2	20/20
第二周	300/500	2/4	18/38
第三周	500/1000	3/7	22/60
第四周	300/1300	2/9	30/90

• 计划学习时间:XX小时

• 实际学习时间:XX小时

• 改进情况：

(有空多看看现代软件工程 课件
软件工程师能力自我评价表)

参考资料

• java数据结构之树

201723132018-2019-1《程序设计与数据结构》第七周学习总结(代码片段)

201723132018-2019-1《程序设计与数据结构》第七周学习总结教材学习内容总结概述二叉查找树：二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，而父结点又小于或等于右孩子。二叉查找树的定义是二叉树定义的... 查看详情

程序设计与算法

程序设计与算法[北京大学] 第一周：枚举完美立方生理周期称硬币熄灯问题讲义加群：597225218　　输入：博客园程序设计与算法第一章第二周：递归（一）阶乘汉诺塔N皇后波兰表达式讲义加群：597225218　　输入：博客园程序... 查看详情

201723272018-2019-1《程序设计与数据结构》实验三：查找与排序

201723272018-2019-1《程序设计与数据结构》实验三：查找与排序课程：《Java软件结构与数据结构》班级：201723姓名：马瑞蕃学号：20172327实验教师：王志强实验日期：2018年11月19日必修/选修：必修一、实验内容：实验二查找与排序-1... 查看详情

20172328《程序设计与数据结构》实验三：查找与排序

20172328《程序设计与数据结构》实验三：查找与排序课程：《软件结构与数据结构》班级：1723姓名：李馨雨学号：20172328实验教师：王志强老师实验日期：2018年11月19日-2018年11月25日必修选修：必修一、实验要求内容实验1：定义... 查看详情

20172308实验三《程序设计与数据结构》查找与排序实验报告(代码片段)

201723082018-2019-1实验3《查找与排序》报告课程：《程序设计与数据结构》班级：1723姓名：周亚杰学号：20172308实验教师：王志强实验日期：2018年10月20日必修/选修：必修1.实验内容查找与排序-1：定义一个Searching和Sorting类，并在... 查看详情

《程序设计与数据结构》第八周学习总结

学号20172326《程序设计与数据结构》第八周学习总结教材学习内容总结后绑定在程序执行时执行多态性可由继承与接口实现排序有选择法排序与插入法排序搜索分为线性搜索与二分搜索算法，同一类型的不同方法可能解决同一问... 查看详情

程序设计基石与实践专栏引导

本博文主要对通过程序设计基石与实践专栏归类,主要分为C语言与C++语言.下面对程序设计基石与实践专栏博文的索引:（待定未完待续）C语言话谈C语言让你成为一名Top的C语言程序员C语言程序员必读的5本书让你成为... 查看详情

计算机专业毕业设计(论文)题目汇总表.doc

考试报名数据处理系统设计与实现、基于WEB的车票预订信息系统设计与实现、全文搜索引擎的设计与实现、图书借阅管理信息系统设计与实现、图书销售管理信息系统设计与实现、学生选课信息系统设计与实现、运动会成绩管理... 查看详情

红书《题目与解读》第一章数学题解《acm国际大学生程序设计竞赛题目与解读》(代码片段)

...计划红书《题目与解读》第一章数学题解《ACM国际大学生程序设计竞赛题目与解读》全书目录：《题目与解读》红书训练笔记目录《ACM国际大学生程序设计竞赛题目与解读》目录红书《题目与解读》第一章数学题解《ACM国际... 查看详情

风螺旋与飞行程序设计

精简版的课件分享。风螺旋课题的一个阶段性总结，后续将从理论向实践进行转变，希望取得更多的实践成果，再与大家分享！全文完，谢谢！  查看详情

RESTful URL 设计：公共与私有 API、分层 API 设计模式、URI 与 URL 设计？

】RESTfulURL设计：公共与私有API、分层API设计模式、URI与URL设计？【英文标题】：RESTfulURLdesign:publicvsprivateAPI,hierhachyAPIdesignpattern,URIvsURLdesign?【发布时间】：2013-12-1923:00:23【问题描述】：我经常遇到这样的问题，与HierarchicalRESTfulUR... 查看详情

程序设计语言与语言处理程序基础

重点1编译过程2文法定义 一颗语法树 有限自动机正规式7数据类型与程序控制结构8表达式9传值与传址传址调用10各程序语言特点  查看详情

201823222019-2020-1《数据结构与面向对象程序设计》第四周学习总结

教材学习内容总结1.编写类与方法（构造方法的结构和用途）2.实际参数与形式参数、public与private、return与void的区别与含义、3.UML类图的含义与形式4.静态类（Math类）静态变量、静态方法5.类间关系（依赖关系、聚合关系、继承... 查看详情

概要设计与具体设计

概要设计与具体设计在写概要设计与具体设计的时候,对于内容以及他们之间的界限非常easy模糊.今天写点自己的想法.有问题请大家不吝赐教:[email protected]首先大家要注意这2个文档最后2字,都是设计.设计就是设计,不是代码因... 查看详情

数学题解《acm国际大学生程序设计竞赛题目与解读》(代码片段)

...计划红书《题目与解读》第一章数学题解《ACM国际大学生程序设计竞赛题目与解读》全书目录：《题目与解读》红书训练笔记目录《ACM国际大学生程序设计竞赛题目与解读》目录红书《题目与解读》第一章数学题解《ACM国际... 查看详情

201723292017-2018-2《程序设计与数据结构》第十周学习总结

201723292017-2018-2《程序设计与数据结构》第十周学习总结教材学习内容总结第十三章一、集合与数据结构1、集合：是一种对象，类似于保存其他对象的存储库；2、作用：表示一个专用与保存元素的对象，并且该对象还提供增添、... 查看详情

系统分析与设计复习

文章目录系统分析与设计复习第1章系统分析与设计概述系统特性DevOps第2章系统规划**系统规划步骤**规划模型诺兰模型**CMM模型**系统规划方法战略集合转换法SST关键成功因素法CSF企业资源规划法BSPCSB三者联系和区别第3章系统分... 查看详情

win10系统程序与功能查找，卸载程序

win10系统程序与功能查找，卸载程序  查看详情