Java——二叉树/平衡二叉树/红黑树/B Trees/B+ Trees

一、树的定义：

　　由节点组成的一个具有层次关系的集合；长的像树所以叫树；

　　撸树神器：https://www.cs.usfca.edu/~galles/visualization/

二、二叉树：

　　特性：1）左子树上所有节点的值均小于它的根节点的值；

　　　　2）?右子树上所有节点的值均大于它的根节点的值；

　　示例：一个不好会形成链表结构；

三、平衡二叉树(AVL)：

　　特性：1）在二叉树的基础上，要求两个子树的高度差不能超过1；

　　　　1）每次增删都会通过一次或多次旋转来平衡二叉树；

　　示例：重新插入123456节点；

四、红黑树：

　　特性：1）节点要么黑要么红；

　　　　2）根节点一定时黑色；

　　　　3）所有叶节点都为null，且为黑色；

　　　　4）红色节点的两个子节点都为黑色，不会有两个连续的红；

　　　　5）任意一个路径上的黑节点数，一定时相等的；

　　ps：Java中的terrMap和treeSet是红黑树实现；

五、B Trees/B+ Trees：

　　1）每个节点拥有多个值，2个位二叉，3个为三叉，超过这个值就需要分子节点；

　　2）平衡节点让路径的深度减小IO读取次数随之减少；

　　3）平衡节点中的数据是放到内存中判断的，所以速度快；

六、B+ Trees：

　　mysql的索引就是B+ Trees实现的；

　　特点：1）非子叶节点没有没有数据，只有索引；

　　　　2）所以不管查那个数据，都要从叶节点获取，每次查询的次数都是一样的；

　　　　3）mysql中的索引读取值，只需要一次哈希计算，所以速度比B Tree快；