《数据结构与算法分析 java语言描述(原书第3版)》
二叉树每个节点至多有两个节点,左节点永远比右节点小,并且小于根节点。
查找最好时间复杂度O(longN), 最坏O(N)
插入删除操作时间复杂度跟查找差不多
左右子树的高度差不超过1,并且左右子树都是平衡二叉树,超过1就旋转。
比二叉树稳定,查找时间复杂度O(logN)
插入操作最多需要旋转1次,时间复杂度O(logN)左右
删除时间复杂度O(2logN)
每个节点上都有节点颜色,可以是红色或者黑色;根节点必须是黑色;每个红色节点的子节点,父节点是黑色;从任一节点到每个叶子节点的所有路径都包含相同数目的黑色节点。
查找效率最好情况下是O(logN),最坏情况下比平衡二叉树要差一些,但也比二叉树要好
插入和删除操作改变树的平衡性概率小于平衡二叉树
B+树 的中间节点不保存数据,所以磁盘页能容纳更多节点元素;
B+树查询必须查找到叶子节点,B树只要匹配到即可不用管元素位置,因此B+树查找更稳定
对于范围查找来说,B+树只需遍历叶子节点链表即可,B树却要重复地中序遍历
效率总结:https://blog.csdn.net/z702143700/article/details/49079107
区别对比:https://blog.csdn.net/wyqwilliam/article/details/82935922