（1） 红黑树的了解（平衡树，二叉搜索树），使用场景
把数据结构上几种树集中的讨论一下：
1. AVLtree
定义：先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度 大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和坏情况 下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这 个树。
节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有 平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为 是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或 从可能存储在节点中的子树高度计算出来。
一般我们所看见的都是排序平衡二叉树。
AVLtree使用场景：AVL树适合用于插入删除次数比较少，但查找多的情况。插 入删除导致很多的旋转，旋转是非常耗时的。AVL 在linux内核的vm area中使用。
2. 二叉搜索树
二叉搜索树也是一种树，适用与一般二叉树的全部操作，但二叉搜索树能够实现 数据的快速查找。
二叉搜索树满足的条件：
非空左子树的所有键值小于其根节点的键值
非空右子树的所有键值大于其根节点的键值
左右子树都是二叉搜索树
二叉搜索树的应用场景：如果是没有退化称为链表的二叉树，查找效率就是 lgn，效率不错，但是一旦退换称为链表了，要么使用平衡二叉树，或者之后的 RB树，因为链表就是线性的查找效率。
