关键词：

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

教材学习内容总结

本章的内容主要讲二叉查找树，二叉查找树是对于二叉树的一种拓展，这意味着上一章中对于二叉树的操作对于二叉查找树同样适用，同时它也是一种带有附加属性的二叉树。这种附加属性即：对树中的每个结点，它的左孩子都要小于其父结点，而父结点又小于或等于它的右孩子。这意味着在所有比根结点大的元素都存在于根结点的左边，而比根结点小的元素都在根结点的右边。如图所示：

值得一提的是，对二叉查找树进行中序遍历，正好可以得到一队递增排序的元素。

例如，对于之前所示二叉查找树进行中序遍历可以等到：1，3，4，6，7，8，10，13，14。

• 二叉查找树的查找算法：因为二叉查找树的每个结点都具有特殊性质，所以说所有的元素都是以一定的顺序存在于二叉查找树中，所以对于比根结点大的元素就去根结点的左子树查找，对于比根结点小的元素就去根结点的右子树查找，这个算法如果使用递归实现会非常方便。

例如，查找10

1.查看根节点9：

2.由于10 > 9，因此查看右孩子13：

3.由于10 < 13，因此查看左孩子11：

4.由于10 < 11，因此查看左孩子10，发现10正是要查找的节点：

• 二叉查找树的插入算法：因为二叉查找树是一个其结点具有特定属性的二叉树所以它的插入算法就只需要一个方法，我觉得二叉查找树与有序列表类似，仅需一个addElement方法就可以把一个元素插入正确的位置。具体的解决方案是：
  • 首先执行查找算法，找出被插结点的父亲结点。
  • 判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
  • 若二叉树为空。则首先单独生成根结点。
• 二叉查找树的删除算法：删除结点有三种情况分别是需要删除的结点是叶结点，是仅有左子树/右子树的结点，是既有左子树又有右子树的结点。
  • 删除的结点是叶结点，直接让树结点的父结点的下一个指向null即可。
  • 删除的结点是仅有左子树/右子树的结点，将该节点删除后，将该结点的左结点/右结点提到被删除结点的位置即可。
  • 删除的结点是既有左子树又有右子树的结点，这个时候需要用到中序遍历后的前驱结点，将前驱结点提到被删除结点的位置。

• 平衡二叉查找树，它存在的意义在于提升效率，例如，一棵蜕化树看起来更像一个链表但是它的效率比链表还差。

  • 如图所示，

  • 对于一个平衡二叉查找树来说，它的查找效率会比第二种蜕化树高很多，因为在蜕化树中的每个结点附带有额外的开销，所以说我们就要想着将一些树尽可能的改变为平衡二叉查找树。将一个费平衡二叉查找树改变成为二叉查找树主要有四种方法：右旋，左旋，左右旋，右左旋。

    • 在提到四种方法之前，有一个概念需要理解，一个平衡二叉查找树的最大路径长度应该为log₂n（n为元素个数），并且最长路径必须不小于log₂n-1（n为元素个数），如果一个树的最长查找路径大于log₂n则表明它不平衡，这时候就需要一定的操作使其平衡。

    • 右旋，通常是指左孩子绕着其父结点向右旋转，一般适用于左子树长于右子树的情况
      

    • 左旋，通常是指右孩子绕着其父结点向左旋转，一般适用于右子树长于左子树的情况
      

• AVL树，在之前的基础上添加了平衡因子的说法，即左右子树的高度差，如果高度差大于1或者小于-1，则以该结点为树根的子树需要重新平衡。

• 红黑树，顾名思义，即给每个结点赋以红和黑两种颜色，对于红黑树的三点规定如下，
  • 根结点为黑色。
  • 红色节点的孩子为黑色。
  • 从树根到树叶的每条路径都包含同样树木的黑色结点。
• 红黑树的插入，总是把插入的新元素的颜色设为红色，在插入过后极大可能会导致一系列操作以再次平衡红黑树。

• 红黑树的删除，与插入类似，删除一个元素后有极大可能需要一系列操作以再次平衡红黑树。

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

• 问题一：对于红黑树存在的意义问题，为什么要单独设置一个红黑树呢？红黑树可以解决的问题AVL树也同样可以解决。
• 问题一解决方案：这个问题我在网上查找了部分答案，发现为什么需要发明红黑树。
  • 最主要就是效率问题，红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
  • 当然这也不是没有代价的，红黑树是牺牲了严格的高度平衡的优越条件为代价让红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。

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

• 问题一：对于AVL树的实现存在一些问题，原本以为书上所给的代码已经实现了AVL树，就好像那个addElement(T element)一样。
• 问题一解决：询问了结对伙伴，发现好像不是这样的，addElement(T element)这个方法只能一直添加元素，但不能使得元素成为平衡树，就好像如果一直利用这个方法添加递减的元素会导致蜕化树的出现。
• 问题二：对于AVL树的实现有一些疑惑，它的左旋、右旋、左右旋、右左旋怎么实现？
• 问题二解决：班主任在蓝墨云上的资源《红黑树(五)之 Java的实现》的博主对于树的实现有一系列的东西，不只是红黑树，我在其博客中找到了《AVL树(三)之 Java的实现》，借鉴了博主的部分代码，并且看懂了他们，感谢博主

代码托管“点这里跳转到码云”

上周考试错题总结

• 错题1：A find operation on a balanced binary search tree is O(logn) where as a find operation for binary search tree without the balance assumption is O(n).
• A.True
• B.False

• 错题1解析：平衡树查找的时间复杂度就是O(logn)。

• 错题2是那一道没有图的题。

结对及互评（待修改）

• 博客中值得学习的或问题：
  • 范雯琪同学的博客课本上的学习内容总结部分写得十分详细，值得学习。
  • 每次看到范雯琪同学的博客自己都比较惭愧，实在是非常优秀，可想而知她在博客这一方面所做出的努力，我也非常想想她学习。
• 代码中值得学习的或问题：
  • commit提交的解释清晰明了，我觉得我应该学习。
  • 有许多代码的问题都是我向她询问，我很感谢她

点评过的同学博客和代码

• 本周结对学习情况

  • 20172303

  • 结对学习内容
    • 我们一起实现了本周需要实现的一些PP项目并且给互相讲述了其中的基本原理。

其他

• 感悟：感觉自己在代码上的问题越来越少了...快要找不出问题了，怎么办...一定是我学得还不够认真

课本单词

(本部分用于收集本章节后的生词)

• binary search tree：二叉查找树
• degenerate tree：蜕化树
• right rotation：右旋
• left rotation：左旋
• rightleft rotation：右左旋
• leftright rotation：左右旋
• AVL tree：AVL树
• balance factor：平衡因子
• red/black tree：红黑树

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	5000行	30篇	400小时
第一周	0/5000	2/2	8/8	认真学习！积极向上
第二周	812/812	1/3	22/30
第三周	814/1626	1/4	20/50
第四周	1386/3012	2/6	20/70	愉快的国庆节就要结束了...
第五周	1222/3234	1/7	30/100
第六周	1327/4561	2/7	30/100	啦啦啦啦啦
第七周	1170/5631	1/8	33/133

• 计划学习时间:25小时

• 实际学习时间:33小时

• 改进情况：规范commit行为，改进博客园模版。

参考资料

• 《Java软件结构与数据结构》
• 《红黑树(五)之 Java的实现》
• 《AVL树(三)之 Java的实现》

20165309第七周学习总结

201653092017-2018-2《Java程序设计》第七周学习总结教材学习内容总结第11章JDBC与MySQL数据库JDBC的操作：(1)与一个数据库建立连接。(2)向数据库发送SQL语句。(3)处理数据库返回的结果。连接数据库P329查询操作得到SQL查询语句对象处理... 查看详情

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

201723322017-2018-2《程序设计与数据结构》第六周学习总结教材学习内容总结第九章继承1.创建子类。子类与父类的关系。子类是父类的其中一种。派生操作在子类中加保留字extends实现。子类的实例化并不依赖于父类的实例化。2.pro... 查看详情

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

20172301《程序设计与数据结构》第七周学习总结教材学习内容总结二叉查找树是一种含有附加属性的二叉树，其左孩子小于父结点，父结点小于或者等于右孩子。用链表实现二叉查找树addElement操作：根据给定元素的值，在树中的... 查看详情

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

学号20172326《程序设计与数据结构》第七周学习总结教材学习内容总结AVL树AVL树是实现平衡二叉树的一种算法实现，别的方法也可实现例如红黑树。平衡因子：右子树高度-左子树高度的差值（高度是指当前结点到叶子结点的最长... 查看详情

201723152018-2019-2《程序设计与数据结构》第七周学习总结

201723152018-2019-2《程序设计与数据结构》第七周学习总结教材学习内容总结二又查找树是一种含有附加属性的二又树，即其左孩子小于父结点，而父结点又小于或等于右孩子。每个BinaryTreeNode对象要维护一个指向结点所存储元素的... 查看详情

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

201723332018-2019-1《程序设计与数据结构》第七周学习总结教材学习内容总结《Java软件结构与数据结构》第十一章-二叉查找树一、二叉查找树的概念及相关方法①思路：二叉查找树与普通的二叉树的区别类似于有序链表与无序链表... 查看详情

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

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

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

20172311《程序设计与数据结构》第七周学习总结教材学习内容总结第十一章二叉查找树树是一种非线性结构，其中的元素被组织成一个层次结构含有m个元素的平衡n元树具有的高度为lognm树的数组实现之计算策略：如果我们存储的... 查看详情

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

201723302018-2019-1《程序设计与数据结构》第七周学习总结教材学习内容总结二叉查找树在二叉查找树中：若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；任意节点的右子树不空，则右子树上所有结点... 查看详情

201723102017-2018《程序设计与数据结构》（下）第七周学习总结(代码片段)

201723102017-2018《程序设计与数据结构》（下）第七周学习总结教材学习内容总结本章学习的是二叉查找树11.1概述二叉查找树(binayscarchtree)是种带有附加属性的二叉树，即对树中的每个结点，其左孩子都要小于其父结点，而父结点... 查看详情

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

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

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

201723192018.10.27-11.02《程序设计与数据结构》第7周学习总结目录教材学习内容总结教材学习中的问题和解决过程代码调试中的问题和解决过程代码托管上周考试错题总结结对及互评学习进度条参考资料教材学习内容总结第十一章... 查看详情

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

教材学习内容总结第十一章二叉查找树一、概述二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，父结点小于或等于右孩子（二叉查找树的定义是二叉树定义的扩展）二、用链表实现二叉查找树addElement操作：ad... 查看详情

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

教材学习内容总结概述二叉查找树：是含附加属性的二叉树，即其左孩子小于父节点，而父节点又小于或等于右孩子。二叉查找树的定义是二叉树定义的扩展。二叉查找树的各种操作用链表实现二叉查找树每个BinaryTreeNode对象要... 查看详情

20165214第七周学习任务(代码片段)

201652142017-2018-2《Java程序设计》第七周学习总结教材学习内容总结11.1介绍了如何下载MySQL社区版，我跟着流程下载成功了。11.2介绍了如何启动MySQL数据库服务器；可以使用mysqadmin-r[用户名]-p[密码]来修改密码。初始化成功后出现... 查看详情

201723282018-2019《java软件结构与数据结构》第七周学习总结(代码片段)

201723282018-2019《Java软件结构与数据结构》第七周学习总结概述Generalization本周学习了第11章：二叉查找树。在本章中，主要探讨了二叉查找树的概念和各种二叉查找树实现，考察为二叉查找树添加和删除元素的算法以及维护平衡... 查看详情

201723052018-2019-1《java软件结构与数据结构》第七周学习总结

201723052018-2019-1《Java软件结构与数据结构》第七周学习总结教材学习内容总结本周内容主要为书第十一章内容：二叉查找树(附加属性的二叉树)二叉查找树是对树中的每个结点，其左结点都要小于其父结点，而父结点又小于或等... 查看详情

2018-2019-20172329《java软件结构与数据结构》第七周学习总结(代码片段)

2018-2019-20172329《Java软件结构与数据结构》第七周学习总结教材学习内容总结《Java软件结构与数据结构》第十一章-二叉查找树一、概述1、什么是二叉查找树：二叉查找树是一种带有附加属性的二叉树，即对树中的每个结点，其... 查看详情