接上文

二叉树

二叉树(BinaryTree)由一个节点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成

1、排序二叉树

特点：

 左子树上所有节点的值均小于它的根节点的值。
 右子树上所有节点的值均大于它的根节点的值。

优点：

查找、插入、删除操作的时间复杂度都为O(logn)，效率较高。
可以进行排序和统计操作。

缺点：

如果插入的数据是有序的，二叉排序树会退化成链表，导致操作效率降低。
对于极端情况，如插入的数据是有序的或者是倒序的，二叉排序树的效率会变得很低。

应用

排序：二叉排序树可以对数据进行排序，其时间复杂度为O(nlogn)，比冒泡排序、插入排序等算法更快。
查找：二叉排序树可以快速地查找某个元素，其时间复杂度为O(logn)，比线性查找更快。
数据的统计：二叉排序树可以统计数据中小于、大于某个值的元素个数，也可以计算树的高度、节点个数等信息。

排序二叉树本身实现了排序功能，可以快速检索。但如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将退化成普通的链表，其检索效率就会很差，所以出现了平衡二叉树。

2、平衡二叉树

在平衡二叉树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。 增加和删除节点可能需要通过一次或多次树旋转来重新平衡这个树。

节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树

平衡二叉树追求绝对平衡，实现起来比较麻烦，每次插入新节点需要做的旋转操作次数不能预知。

优点：

使二叉树的结构更好(即不会出现“偏拐”严重的情况)，从而提高了查找操作的速度。

缺点：

使插入和删除操作复杂化，从而减低了插入和删除操作的速度。

应用：

平衡二叉树适用于二叉查找树一经建立就很少进行插入和删除操作，而主要进行查找操作的应用场合上。由于其在查找过程中和给定值进行比较的关键字个数不超过树的深度。因此，在平衡二叉树上进行查找的时间复杂度为O（log2n）

红黑树

特点

 左子树上所有节点的值均小于它的根节点的值。
 右子树上所有节点的值均大于它的根节点的值。
 每个节点要么是红色，要么是黑色。
 根节点永远是黑色的。
 所有的叶节点都是空节点(即 null)，并且是黑色的。
 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点)
 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

未完待续。。。