数据结构-树结构的梳理
二叉树
- 遍历（先序DLR,中序LDR,后序LRD）
- 中序遍历能够确定二叉树结构
二叉排序树
- 左子树均小于根节点，右子树均大于根节点
平衡二叉树
- 平衡是指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低
AVL树
- 自平衡的二叉查找树（通过左右旋实现平衡）
- 左右子树都是平衡二叉树
- 右旋：左节点转到根节点
- 左旋：右节点转到根节点
红黑树
- 为了提升AVL树的update维护效率引入红黑树
- 节点是红色和黑色
- 根是黑色
- 所有叶子都是黑色
- 每个红色节点必须有两个黑色的子节点
B-树
- 多路搜索树
B+树
注意：b+树是在b树的基础上增加了
- 叶子节点包含所有树干的数据
- 叶子节点间增加指针（类似链表）
B*树
- 在b+树的基础上定义了非叶子节点相同层之间的指针
参考公众号：java技术栈