上一讲介绍了线性结构，下面来看一下树状结构。Java集合中使用的树状结构是二叉树，更具体来说，是红黑树。具体红黑树是什么，读者可以去查阅一下相关的资料。我们这里只做一个简单的说明，红黑树是一颗伪平衡的排序树。那么，什么又是平衡树？什么又是排序树呢？

　　先来说明排序树。排序树要求根结点的左子树都要小于根，而左子树都要大于根。这样的好处是在查找时效率比较高，实际上就是通常说的拆半查找。比如，我说有一个数介于1－100之间，那么你猜什么？一定是先猜50，然后根据大小在缩小查找范围。这就是拆半查找。

　　再来看平衡树。在排序树中，要求左子树小于根，而右子树大于根。但如果左子树没有，所以的结点都在右子树上，那么就退化成链表了。这样就无法实现拆半查找了。所以排序树最好的状态应该是左、右子树数目差不多。平衡树严格来说就是左、右子树的深度之差的绝对值不能大于1。红黑树不能达到这一点，但左右子树也基本平衡，所以说它是平衡树。

　　Java集合中用到了红黑树的包括TreeMap和TreeSet。因为要排序，所以必须要知道两个对象之间谁是大的，谁又是小的。这就需要有一个比较规则。现在你应该明白了，为什么加入TreeSet或TreeMap的元素都要实现Comparable接口，或提供Comparator排序子。因为这样才有可能排序，即自然排序或完全排序。