2. 二叉查找树
概念：
二叉查找树，即左子树结点值都小于根节点，右子树结点值都大于根节点。同时具有数组的查询效率，链表的增删改效率。
通过中序遍历方式可以将二叉查找树按从小到大的方式将树各节点的值打印出来。
特点：
1. 二叉查找树左子树的所有节点的值都小于父节点的值， 右子树的所有节点的值都大于父节点的值。
2. 具有数组的查询效率，也具有链表的增删改性能。
缺点：
二叉查找树的规则只要是左子树小于右子树即可，但可能会出现 “一边倒” 的情况，那么二叉查找树就退化成链表了，二叉查找树的查询优势也无法体现出来了。
二叉查找树的概念及基本功能的代码实现：
3. 平衡二叉树（AVL 树）
概念：
平衡二叉树也称 AVL 树，主要是为了解决二叉查询树不平衡的情况下，导致查询效率低下的解决方案。二叉查找树极端情况下会出现一边倒的情况，平衡二叉树就是为了解决这一问题，通过左旋、右旋的方式，保证树的平衡。
特点：
1. 拥有二叉查找树的全部特性
2. 左子树和右子树的高度差绝对值不超过 1
3. 插入和删除数据时需要进行平衡操作，即左旋、右旋的方式，来保证树的平衡
优缺点:
平衡二叉树保证了不会出现一边倒的情况， 通过左旋、右旋来保证了二叉树的平衡，把插入、删除、查找的时间复杂度最好和最坏情况都维持在 O（logN）。但平衡二叉树这种高度差为 1 的要求太严格了，尤其是对于频繁删除、插入的场景非常浪费时间。
平衡二叉树的概念及基本功能的代码实现：
4. 红黑树
概念：
红黑树也是一种对查询效率进行优化的二叉查找树，它要求从根节点到叶子结点的最长可能路径不多于最短的可能路径的两倍长。
红黑树的特点：
- 具有二叉树所有特点。
- 每个节点只能是红色或者是黑色。
- 根节点只能是黑色，且黑色根节点不存储数据。
- 任何相邻的节点都不能同时为红色。
- 红色的节点，它的子节点只能是黑色。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
六、总结：
1. 红黑树和平衡二叉树的区别：
（1）红黑树放弃了追求完全平衡，而是追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多两次旋转，删除最多三次旋转就能达到平衡，实现起来也更为简单。
（2）平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。
所以，对于插入、删除操作较多的情况下，红黑树的效率是优于平衡二叉树的；而对于插入、删除不频繁，只是对查找要求较高，那么平衡二叉树还是较优于红黑树。
2. 为什么有了数组和链表还要引入二叉树？
针对数组和链表的优缺点，无法说链表一定优于数组，或者是数组一定优于链表，因为某些长期的需要，数组在查询方面效率高，链表在插入、删除方面效率高，所以就推出一个相对折中的二叉树。二叉树在插入、删除、查询方面效率都较好。
3. 为什么有了二叉树还要引入平衡二叉树？
有了二叉树还不算完，二叉树有一种极端的情况，就是所有的子结点偏向一端，二叉树退化成链表，这就相当于我选择了这种的二叉树，你现在罢工不干了，找了个链表来糊弄我...
所以为了解决二叉查找树退化为链表的情况，引入了平衡二叉树，即：
平衡二叉树是为了解决二叉树退化成一棵链表而诞生的。
4. 为什么有了平衡二叉树还要引入红黑树？
实际使用过程中，因为平衡二叉树追求绝对严格的平衡关系，显然这个规则在于频繁的插入、删除等操作的情景性能肯定会出现问题...
所以为了解决这个问题，进而又引入了红黑树。
平衡二叉树追求绝对严格的平衡，平衡条件必须满足左右子树高度差不超过 1，红黑树是放弃追求完全平衡，它的旋转次数少，插入最多两次旋转，删除最多三次旋转，所以对于搜索、插入、删除操作较多的情况下，红黑树的效率是优于平衡二叉树的。
