树
对于大量的输入数据，链表的线性访问时间太慢，不宜使用。有一种简单的数据结构，其大部分操作的运行时间平均为 O(logN)，这种数据结构叫做二叉查找树。二叉查找树是两种库集合类 TreeSet 和 TreeMap 实现的基础。
树(tree)可以用几种方式定义。定义树的一种自然的方式是递归的方式。一棵树是一些节点的集合。这个集合可以是空集；若不是空集，则树由称作根(root)的节点r 以及 0 个或多个非空的(子)树 T1，T2, … , T4 组成，这些子树中每一颗的根都来自根 r 的一条有向的边(edge)所连结。
每一颗子树的根 r 的儿子(child),而 r 是每一颗子树的根的父亲(parent)。如下图显示用递归定义的典型的树。
从递归定义发现，一棵树是 N 个节点和 N-1 条边的集合，其中的一个节点叫做根。存在 N-1 条边的结论是由下面的事实得出的：每条边都将某个节点连接到它的父亲，而除去根节点外每个节点都有一个父亲，如下图：
二叉树
二叉树是一棵树，其中每个节点都不能有多于两个的儿子。
下图 显示一颗由一个根和两颗子树组成的二叉树，子树 \(T_ L\) 和 \(T_ R\) 均可能为空。
二叉树的一个性质是一颗平均二叉树的深度要比节点个数 N 小得多。分析表明，其平均深度为
\(O(\sqrt{N})\)
而对于特殊类型的二叉树，即二叉查找树，其深度的平均值是 O(logN)。最坏情形的二叉树，深度可以达到 N - 1 .
AVL 树
AVL 树是带有平衡条件的二叉查找树。这个平衡条件必须要容易保持，而且它保证树的深度须是 O(logN)。最简单的想法是要求左右子树具有相同的高度。
一颗坏的二叉树。只要求在根节点平衡是不够的
当进行插入操作时，需要更新通向根节点路径上那些节点的所有平衡信息，而插入操作，插入一个节点可能破坏 AVL 树的特性（如下图，将 6 插入到图中，将破坏关键字 8 的节点处的平衡条件）。如果发生这种情况，那么就要在考虑这一步插入完成之前恢复平衡的性质。通过对树进行简单的修正来做到称为旋转。
两颗二叉查找树，只有左边的树是 AVL 树
单旋转：
双旋转：
红黑树
历史上 AVL 树流行的另一变种是红黑树。对红黑树的操作在最坏情形下花费 O(logN)时间。
红黑树是具有下列着色性质的二叉查找树：
- 每一个节点或者着色成红色，或者着色成黑色。
- 根是黑色的。
- 如果一个节点是红色的，那么它的子节点必须是黑色的。
- 从一个节点到一个 null 引用的每一条路径必须包含相同数目的黑色节点。
着色法则的一个结论是，红黑树的高度最多是 2log(N+1)。因此查找操作保证是一种对数的操作。如下图显示一颗红黑树。
和通常一样，困难在于将一个新项插入到树中。通常把新项作为树叶放到树中。如果把该项涂成黑色，那么肯定违反条件 4，因为将会建立一条更长的黑色路径。因此，这一项必须涂成红色。如果它的父节点是黑色的，则插入完成。如果它的父节点已经是红色的，那么得到连续红色的节点，这就违反了条件 3。在这种情况下，我们必须调整该树以确保满足条件 3（且又不引起条件 4 被破坏）。用于完成这项任务的基本操作是颜色的改变和树的旋转。
