为啥用树

存储一组数据 ==》数组 ==》链表 ==》树

数组：
需要连续的空间(需要指定长度)、扩容时很麻烦
链表：
不需要连续的空间(用指针连接前后节点)、
与数组一样，检索时需要遍历
二叉排序树 Binary Sort Tree
比链表检索速度更快(要求key值不能重复)
中序遍历即可得到一组排好序的
平衡二叉树 AVL Tree
二叉排序树对根节点选取要求太高，因为后续插入的节点分布在跟节点两侧，
极端情况下（如后续插入的都比跟节点大，全部分布在右侧，就退化成链表了）效率不高；
平衡二叉树在插入新节点时会根据负载因子重新选取根节点(为保证根节点在中间,加入新节点时，
看起来像在旋转这棵树，让整棵树左右两侧达到平衡，所以叫平衡二叉树)
红黑树
根节点为黑色，节点是红色或黑色，所以叫红黑树。
红黑树是相对平衡的，比AVL容易实现，又解决了二叉查找树退化成链表的问题
Balance Tree
多路自平衡搜索树，每个节点允许有多个子节点(每个Node，二叉树里是对象，B树可以用链表实现吧)
如磁盘文件管理，不可能所有数据都放到内存吧，用B Tree查找文件时能有效减少与磁盘的交互次数；
B+ Tree
B+ Tree的内节点(非叶子节点)不存储数据(如数据库的索引)，每个内节点数据更多，查找范围更大，
进一步减少与磁盘的交互次数(降低了树的高度)

树的应用