目录
前言
你好，认识一下，我是树
二叉树与二叉排序树
二叉排序树特点
为什么说二叉排序树查询效率要高于链表呢？
元素的类型
比较器
手写二叉排序树
定义一棵二叉树
增加元素
查询元素
修改元素
删除元素
遍历二叉树
重写toString
二叉排序树的极端情况
平衡二叉树
红黑树
保证平衡
红黑树的规则
红黑树的应用
散列表
向散列表中存数据
hashCode()方法特点
链表的产生原因
链表存在的问题
数组的扩容
结语
前言
学习是一个渐进的过程，如果还没看过我前面写的有关数据结构的文章可以先去看完再回来看这篇，在写这篇之前，我已经预见到了这篇博客会比较长，而且概念性的东西会比较多，如果你对树真的有兴趣，想要一看究竟，那么欢迎你继续读下去，如果你只是临时起意，劝你三思。树在各个语言领域都可谓谈之色变，九成九的程序员在开发中根本就没用过树，但实际上又在不知不觉间用了。那么树是什么？树在Java开发中又有哪些代言人，让我们通过这篇博客来认识下吧。
你好，认识一下，我是树
树，我们在数据库索引的数据结构中已经给大家介绍过，为了方便大家理解，这里给没看过的小伙伴重新写一下：
Tree就是树，顾名思义，像树一样的结构，只要是树，就一定拥有四个属性：
根结点：位于顶端且仅有一个
高度：整个树的层次
度：树中最大子节点数
叶子结点：位于最底层且没有子节点，或者说度为0的节点
看到这里，想必你已经知道了什么是树，下面，我给出一张图让大家看看树的基本数据结构：
看上去很赏心悦目，这是一棵平衡二叉树，也是二叉树的一种，仅做展示，没其他意义，请不要额外联想。在写之前，我们要先明白一件事，集合中是不能添加重复元素的，先不要问，后面你就知道为什么了。
二叉树与二叉排序树
顾名思义，度为2的树就是二叉树，上面的图就是一个二叉树，那什么是二叉排序树呢？二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。如我先前所言，这里我们又提到了链表，如果看过前面文章的小伙伴可以加深对链表的理解。
二叉排序树特点
元素不能重复
左子树中节点均小于根结点
右子树中节点均大于根节点
这一点从此图也能看的出来：
为什么说二叉排序树查询效率要高于链表呢？
如果是一个长度为n的链表，最差的结果就是查n次（单向链表，双向链表查询方式可查看前面关于链表的博客），在二叉排序树中，看图，每次比较后都会排除总量一半的数据，所以查询的效率非常高。这个二叉排序树中有7个元素，假设n为7，链表最多要查7次，这里最多也就是3次，如果数据量翻倍，差别会更大。
元素的类型
二叉排序树中的元素的类型可以是其他的引用类型，但是他们之间要能比较大小，这就需要他们都实现comparable接口，在类中定义比较的规则，这样，对象也是可以比较大小的。
比较器
比较器分为两种：
comparable：内比较器，实现该接口后，需要重写内部抽象方法，在类内部定义比较规则，Collections.sort(list)就是如此
comparator：外比较器，比较规则定义在类的外部，通常用于在不改变类原有比较规则的情况下，使用新的/临时的比较规则，此时可以在类的外部实现该接口，定义新的比较规则。Collections.sort(list,comparator)
对集合排序有一个机制，这是前提： sort方法内部会自动调用集合中元素的compareTo方法
没有这个前提，我们接下来讲的就没有意义！
说起来很笼统，所以我们通过代码来说明：
我们先定义一个学生类，并重写抽象方法：
public class Student implements Comparable<Student>{ private Integer id; private String name; private Integer age; @Override public int compareTo(Student o) { return this.id-o.getId(); } }
接着我们来把学生按照id升序排列：
List<Student> list = new ArrayList<>(); for (int i=2;i<=10;i++){ Student student = new Student(i,"student"+i,20+i); list.add(student); } Student student1 = new Student(1,"Ammy",20); list.add(student1); list.forEach(student -> System.out.println(student)); //对list按id升序排列 Collections.sort(list); list.forEach(student -> System.out.println(student));
可以看到，在学生中我们已经重写了compareTo方法，这里我们就可以直接通过sort方法来处理。
上面我们采用的是内比较器，接下来我们改变规则，采用外比较器来处理：
//按age升序排列 Collections.sort(list, new Comparator<Student>() { @Override public int compare(Student o1, Student o2) { return o1.getAge() - o2.getAge(); } }); list.forEach(student -> System.out.println(student));
如果要比较name，因为name肯定是String类型，使用String默认的比较器就可以，和age是不一样的，还是写一下吧：
//按照name升序排列 Collections.sort(list, new Comparator<Student>() { @Override public int compare(Student o1, Student o2) { return o2.getName().compareTo(o1.getName()); } }); list.forEach(student -> System.out.println(student));
手写二叉排序树
接下来是我们的重点，手写二叉排序树，带大家理解排序的逻辑和原理。
定义一棵二叉树
其本质上是数据结构，是用来存储数据的，所以我们一般用泛型，让外部告知具体类型，而不能把类型写死。
public class BinarySearchTree<E extends Comparable<E>> { }
而为了让传入的类型支持比较，必须要对泛型继承Comparable，这也是一个难点，很多人在这里容易写错。
定义完了类，那接着就需要定义根节点：
public class BinarySearchTree<E extends Comparable<E>> { //根节点 private Node root; //定义内部类表示节点 private class Node{ private E ele; //节点中保存的元素对象 private Node left; //左子树指向的节点 private Node right; //右子树指向的节点 //定义有参构造方法,用于创建节点 Node(E ele){ this.ele = ele; } } }
这时，一棵树的基本元素就定义好了，接下来就是我们所熟悉的增删改查方法，但写起来，可能并没那么简单。
