数据结构 树 Tree
树的相关术语
一个树结构包含一系列存在父子关系的节点，每个节点都有一个父节点已经零个或多个子节点。
位于树顶部的节点，叫做根节点，它没有父节点，书中的每个元素都叫做节点，节分为内部节点和外部节点，没有子元素的节点成为外部节点或者叶子节点。
一个节点可以有祖先和后代
有关树的另一个术语是子树，子树由节点和它的后代组成。
节点的一个属性是深度，节点的深度取决于它的祖先节点的数量
树的高度取决于所有节点深度的最大值。
N 叉树
二叉搜索树
AVL 树
自平衡二叉树搜索是计算机科学中的一类数据结构，为改进的二叉搜索树。一般的二叉搜索树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。
而 AVL 树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在 AVL 树中，任一节点对应的两棵子树的最大高度差为 1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是${\displaystyle O(\log {n})}$。
AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 Evgenii Landis，他们在 1962 年的论文《An algorithm for the organization of information》中公开了这一数据结构。
AVL 树增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。
红黑树
红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在 1972 年由鲁道夫·贝尔发明，当时被称为"对称二叉 B 树"。
红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在${\displaystyle {\text{O}}(\log n)}{\displaystyle {\text{O}}(\log n)}$时间内完成查找、插入和删除
红黑树和 AVL 树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用，如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为基础模板的价值；
一般工业界把红黑树作为一种更通用的平衡搜索数来用，Java用它来实现TreeMap, C++的std::set/map/multimap等等。
B 树和 B+ 树
二叉平衡搜索树的问题在于每次插入和删除都有很大可能需要进行重新平衡，数据就要不停的搬来搬去，在内存中这问题不是特别大，可如果在磁盘中，这个开销可能就大了。
有兴趣的朋友还可以看看2-3-4 tree，它等价于红黑树，可以互相转换。它每个节点可以最多有四个孩子，重新平衡操作的次数稍稍少了一点点。以上这些树绝大多数应用都是作为内存中的数据结构。
B/B+ 树就是N叉（N-ary）平衡树了，每个节点可以有更多的孩子，新的值可以插在已有的节点里，而不需要改变树的高度，从而大量减少重新平衡和数据迁移的次数，这非常适合做数据库索引这种需要持久化在磁盘，同时需要大量查询和插入操作的应用。
B 树
在计算机科学中，B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种资料结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。
与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。
B树这种数据结构可以用来描述外部存储。这种资料结构常被应用在数据库和文件系统的实现上。
B+ 树
B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。
B+ 树元素自底向上插入，这与二叉树恰好相反。PS: 同时也让 B+ 树的理解和实现变得困难。
B+ 树 VS B 树
B+树仅在叶子节点存储数据，非叶子节点仅存储关键字。
B+树叶子节点间用链表相互连接，只要扫描叶子节点就可以完成一次遍历操作，B 树只能使用中序遍历
Trie 树
Trie并不是平衡树，也不一定非要有序。它主要用于前缀匹配，比如字符串，比如说ip地址，如果字符串长度是固定或者说有限的，那么Trie的深度是可控制的，你可以得到很好的搜索效果，而且插入新数据后不用平衡。