树

二叉查找树

平衡二叉树（AVL Tree，Self-balancing binary search tree）


红黑树

1.节点带有颜色，为红色和黑色
2.根节点是黑色的
3.每个叶子节点都是黑色的（叶子是NIL节点）
4.每个红色结点的两个子结点一定都是黑色（从叶子到根节点的所有简单路径上不可能有两个连续的红色节点）
5.任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
从性质5又可以推出：

  • 性质5.1：如果一个结点存在黑子结点，那么该结点肯定有两个子结点

地址：https://www.jianshu.com/p/e136ec79235c

平衡多路查找树（Balance-Tree）

B+Tree

B*Tree