二叉树和红黑二叉树
二叉树的定义
二叉树是树形结构的一个重要类型。 许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
二叉速树的特点：
1)树是由一个集合以及在该集合上定义的一种关系构成的。
集合中的元素称为树的结点，所定义的关系称为父子关系。
2) 父子关系在树的结点之间建立了一个层次结构。
3) 树的结点包含一个数据元素及若干指向其子树的若干分
支。
4) 在这种层次结构中有一个结点具有特殊的地位，这个结点
称为该树的根结点，或简称为树根。
平衡二叉树
在平衡二叉树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。 增加和删除节点可能需要通过一次或多次树旋转来重新平衡这个树。
红黑二叉树
红黑二叉树(简称：红黑树)，它首先是一棵二叉树，同时也是一棵自平衡的排序二叉树。
红黑树在原有的排序二叉树增加了如下几个要求：
1. 每个节点要么是红色，要么是黑色。
2. 根节点永远是黑色的。
3. 所有的叶节点都是空节点(即 null)，并且是黑色的。
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点)
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
这些约束强化了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。这样就让树大致上是平衡的。
红黑树是一个更高效的检索二叉树，JDK 提供的集合类 TreeMap、TreeSet 本身就是一个红黑树的实现。
TreeMap的使用和底层实现
TreeMap和HashMap实现了同样的接口Map，因此，用法对于调用者来说没有区别。HashMap效率高于TreeMap;在需要排序的Map时才选用TreeMap。
HashSet
其特点为：是无序、不可重复
HashSet与HashMap的关系？
HashSet是采用哈希算法实现，底层实际是用HashMap实现的(HashSet本质就是一个简化版的HashMap)，因此，查询效率和增删效率都比较高。
TreeSet的底层数据结构是：红黑树，通过内部比较器和外部比较器去掉重复元素。
Hashset自定义对象时，必须重写hashcode()方法和equals()方法，以下为课堂代码
TreeSet的使用和底层实现
TreeSet底层实际是用TreeMap实现的，内部维持了一个简化版的TreeMap，通过key来存储Set的元素。 TreeSet内部需要对存储的元素进行排序，因此，我们对应的类需要实现Comparable接口。这样，才能根据compareTo()方法比较对象之间的大小，才能进行内部排序。
TreeSet的使用
运行结果为：
遍历集合的方法总结
遍历List方法一：普通for循环
遍历List方法二：增强for循环(使用泛型!)
遍历List方法三：使用Iterator迭代器(1)
遍历List方法四：使用Iterator迭代器(2)
遍历Set方法一：增强for循环
遍历Set方法二：使用Iterator迭代器
遍历Map方法一：根据key获取value
遍历Map方法二：使用entrySet
集合体系框架总结表如下：
