关键词：
学号 20172326 《程序设计与数据结构》第七周学习总结
教材学习内容总结
AVL树
- AVL树是实现平衡二叉树的一种算法实现，别的方法也可实现例如红黑树。
- 平衡因子：右子树高度-左子树高度的差值（高度是指当前结点到叶子结点的最长路径，如所有叶子结点的高度都为0，而深度则是指从根结点到当前结点的最大路径，如根结点的深度为0。），规定AVL树的平衡因子不大于1。所以在一个已经实现的AVL树中，任意一个节点的平衡因子的取值为（1，-1,0）。
- 左旋，右旋，左右旋，右左旋。当进行插入抑或是删除操作时，可能导致一个平衡二叉树失衡，因此就要对其进行调整，使其恢复平衡。可以简单的用列表遍历这个数，重新构造一个新的树，但这种方法太过简单，粗暴。所以我们可以使用旋转树，来使其恢复平衡。
- 右旋（或称为左左旋），经过计算，发现某一失衡点的左子树的深度大于右子树，这时就需要将左子树向“右”旋转，使其恢复平衡。方法：将失衡点的左结点设为当前树的新根，使原根变为新根的右结点，将新根的右结点变为原根的左结点。
- 左旋，失衡点处右子树的深度大于左子树，将右子树向左旋转。原理与右旋对称。
- 当某一子树太深时，仅通过一次右旋或左旋将无法完成，因此，我们需要使用两次旋转来实现它。因为旋转方法总是对称的，所以，只拿左右旋转为例。
- 左右旋，当左孩子的右子树太深时，进行旋转。先将其父节点变为其左孩子，同时将其左左孩子进行分配。
在执行结束操作后，通过比较每个结点的平衡因子来维持AVL树的平衡
红黑树
- 根结点为黑色；每个结点只有红色或黑色；所有的叶结点为黑色；红结点的孩子均为黑色；对于每个结点，从该结点到其叶子结点构成的所有路径上的黑结点个数相同；
- 插入结点。1.插入结点为对应的根结点，直接将其涂黑即可。2.插入结点的父节点为黑结点，那么，直接插入即可。3.插入的父节点为红色。此时将破坏红黑树的结构，因此需要将其进行旋转。 分为以下三种情况，满足之一的条件时，进行递归。
- 当插入结点的父结点为红，且叔结点也为红时，将其父结点与叔结点改为红色，祖父结点变为黑色。并将带操作结点改为祖父结点
- 当待操作结点的父节点是红色的，叔叔节点是黑色的，且插入节点是其父节点的右子节点。这时，将待操作结点改为其父结点，再将带操作结点左旋。
- 待操作结点的父结点是红色，叔叔结点是黑色，且插入结点是其父结点的左子结点。我们要做的操作有：将当前结点的父结点涂黑，将祖父结点涂红，在祖父结点为支点做右旋操作。最后把根结点涂黑，整个红-黑树重新恢复了平衡。
- 删除操作：
- 第一步：将红黑树当作一颗二叉查找树，将节点删除。
这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：
① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。
- 第一步：将红黑树当作一颗二叉查找树，将节点删除。
- 第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。
- 第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。
教材学习中的问题和解决过程
- 问题1：
Comparable<T> comparableElement = (Comparable<T>)element 为什么要使用comparable来将element转为相关格式呢？
- 问题1理解：这是添加元素方法（addElement）的一部分代码，将传入的参数转化为comparable型。为什么不在传入的时候直接将其变为comparable类型呢?况且直接变为comparable型数据，在之后的维护平衡树时有助于进行插入元素之间的比较。我们知道，在方法中传入一个comparable参数看似简单，但在真正通过输入数据的时候，可能是一个string值，也可能是一个int值，但是，想传入一个comparable类型数据，基本不可能，所以，选择了在方法中进行类型转化。
- 问题2:红黑树的平衡问题
- 问题2理解：首先，我们知道，红黑树通过颜色来控制平衡。尤其是黑色结点，通过每条路径有相同数目的黑色结点。同时，每个红色结点的孩子结点为黑色。可以想象，想沿着一边子树的一个方向插入众多的结点将不可实现，从而实现了平衡。同时，根据二叉查找树的性质可知，若删除一个结点，除非该结点为根结点且为红色，否则必需经过一些操作以维持平衡。
- 在课堂上，大家发现了一个问题。这种时候，应该怎样操作，对于结点（7）结点（8），无论将其变为黑色还是红色，都符合要求。那么，为什么还要将其涂为红色呢?
涂为红色，有什么变化呢？相较于涂为黑色，黑色结点减少，且其孩子结点为黑色。如果是黑色呢？该树整体黑色结点增多。但问题恰恰就在这里，如果这是一颗单独的树还好说，但如果是某一棵树的子树呢？只有这一部分的黑色结点增加，别的均不变，这直接导致违反了规定。所以，从中也可以看出，对于红黑树，黑色结点的变化是相当慎重的。从规定插入的结点默认为红色也可以看出这点。
代码托管
其他（感悟、思考等，可选）
本章的知识不好理解，尤其是红黑树，涉及了大量的不同情况，令人头秃，而且网上的知识有漏洞的也很多，继续自己体会。
学习进度条
| 代码行数（新增/累积） | 博客量（新增/累积） | 学习时间（新增/累积） | 重要成长 | |
|---|---|---|---|---|
| 目标 | 5000行 | 30篇 | 400小时 | |
| 第一周 | 0/0 | 1/1 | 3/3 | |
| 第二周 | 409/409 | 1/2 | 5/8 | |
| 第三周 | 1174/1583 | 1/3 | 10/18 | |
| 第四周 | 1843/3426 | 2/5 | 10/28 | |
| 第五周 | 539/3965 | 2/7 | 20/48 | |
| 第六周 | 965/4936 | 1/8 | 20/68 | |
| 第七周 | 766/5702 | 1/9 | 20/88 |
参考资料
20172301《程序设计与数据结构》第七周学习总结(代码片段)
20172301《程序设计与数据结构》第七周学习总结教材学习内容总结二叉查找树是一种含有附加属性的二叉树，其左孩子小于父结点，父结点小于或者等于右孩子。用链表实现二叉查找树addElement操作：根据给定元素的值，在树中的... 查看详情
201723132018-2019-1《程序设计与数据结构》第七周学习总结(代码片段)
201723132018-2019-1《程序设计与数据结构》第七周学习总结教材学习内容总结概述二叉查找树：二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，而父结点又小于或等于右孩子。二叉查找树的定义是二叉树定义的... 查看详情
20172311《程序设计与数据结构》第七周学习总结(代码片段)
20172311《程序设计与数据结构》第七周学习总结教材学习内容总结第十一章二叉查找树树是一种非线性结构，其中的元素被组织成一个层次结构含有m个元素的平衡n元树具有的高度为lognm树的数组实现之计算策略：如果我们存储的... 查看详情
201723332018-2019-1《程序设计与数据结构》第七周学习总结(代码片段)
201723332018-2019-1《程序设计与数据结构》第七周学习总结教材学习内容总结《Java软件结构与数据结构》第十一章-二叉查找树一、二叉查找树的概念及相关方法①思路：二叉查找树与普通的二叉树的区别类似于有序链表与无序链表... 查看详情
201723062018-2019-2《java程序设计与数据结构》第七周学习总结(代码片段)
201723062018-2019-2《Java程序设计与数据结构》第七周学习总结教材学习内容总结概述二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，而父结点又小于或等于右孩子。二叉查找树的定义是二叉树定义的扩展。二叉... 查看详情
201723102017-2018《程序设计与数据结构》（下）第七周学习总结(代码片段)
201723102017-2018《程序设计与数据结构》（下）第七周学习总结教材学习内容总结本章学习的是二叉查找树11.1概述二叉查找树(binayscarchtree)是种带有附加属性的二叉树，即对树中的每个结点，其左孩子都要小于其父结点，而父结点... 查看详情
20172322《程序设计与数据结构》第七周学习总结(代码片段)
20172322《程序设计与数据结构》第七周学习总结教材学习内容总结本章的内容主要讲二叉查找树，二叉查找树是对于二叉树的一种拓展，这意味着上一章中对于二叉树的操作对于二叉查找树同样适用，同时它也是一种带有附加属... 查看详情
20172308《程序设计与数据结构》第七周学习总结(代码片段)
教材学习内容总结第十一章二叉查找树一、概述二叉查找树是一种含有附加属性的二叉树，即其左孩子小于父结点，父结点小于或等于右孩子（二叉查找树的定义是二叉树定义的扩展）二、用链表实现二叉查找树addElement操作：ad... 查看详情
201723142018-2019-1《程序设计与数据结构》第七周学习总结(代码片段)
教材学习内容总结概述二叉查找树：是含附加属性的二叉树，即其左孩子小于父节点，而父节点又小于或等于右孩子。二叉查找树的定义是二叉树定义的扩展。二叉查找树的各种操作用链表实现二叉查找树每个BinaryTreeNode对象要... 查看详情
201723282018-2019《java软件结构与数据结构》第七周学习总结(代码片段)
201723282018-2019《Java软件结构与数据结构》第七周学习总结概述Generalization本周学习了第11章：二叉查找树。在本章中，主要探讨了二叉查找树的概念和各种二叉查找树实现，考察为二叉查找树添加和删除元素的算法以及维护平衡... 查看详情
20165214第七周学习任务(代码片段)
201652142017-2018-2《Java程序设计》第七周学习总结教材学习内容总结11.1介绍了如何下载MySQL社区版，我跟着流程下载成功了。11.2介绍了如何启动MySQL数据库服务器；可以使用mysqadmin-r[用户名]-p[密码]来修改密码。初始化成功后出现... 查看详情
2018-2019-20172329《java软件结构与数据结构》第七周学习总结(代码片段)
2018-2019-20172329《Java软件结构与数据结构》第七周学习总结教材学习内容总结《Java软件结构与数据结构》第十一章-二叉查找树一、概述1、什么是二叉查找树：二叉查找树是一种带有附加属性的二叉树，即对树中的每个结点，其... 查看详情
达拉草201771010105《面向对象程序设计（java）》第七周学习总结(代码片段)
达拉草201771010105《面向对象程序设计（java）》第七周学习总结实验七继承附加实验实验时间2018-10-111、实验目的与要求（1）进一步理解4个成员访问权限修饰符的用途；（2）掌握Object类的常用API用法；（3）掌握ArrayList类用法与... 查看详情
2018-2019-20172321《java软件结构与数据结构》第七周学习总结(代码片段)
2018-2019-20172321《Java软件结构与数据结构》第七周学习总结教材学习内容总结第11章二叉查找树一、概述二叉查找树是一种含有附加属性的二叉树，该属性即其左孩子小于父节点，而父节点又小于等于其右孩子。如下图所示。根结... 查看详情
20165309第七周学习总结
201653092017-2018-2《Java程序设计》第七周学习总结教材学习内容总结第11章JDBC与MySQL数据库JDBC的操作：(1)与一个数据库建立连接。(2)向数据库发送SQL语句。(3)处理数据库返回的结果。连接数据库P329查询操作得到SQL查询语句对象处理... 查看详情
《面向对象程序设计（java）》第七周学习总结(代码片段)
...；（5）结合本章知识，理解继承与多态性两个面向对象程序设计特征，并体会其优点；（6）熟练掌握Java语言中基于类、继承技术构造程序的语法知识（ch1-ch5）；（7）利用已掌握Java语言程序设计知识，学习设计 查看详情
201723272018-2019-1《程序设计与数据结构》第七周学习总结
201723272018-2019-1《程序设计与数据结构》第七周学习总结教材学习内容总结第十一章二叉查找树概述1.二叉查找树是一种带有附加属性的二叉树，即对树的每个结点都有左结点小于父结点，右结点小于或等于父结点。2.二叉查找树... 查看详情
201723322017-2018-2《程序设计与数据结构》第七周学习总结
201723322017-2018-2《程序设计与数据结构》第六周学习总结教材学习内容总结第九章继承1.创建子类。子类与父类的关系。子类是父类的其中一种。派生操作在子类中加保留字extends实现。子类的实例化并不依赖于父类的实例化。2.pro... 查看详情