推荐30个国外优秀的设计教程网站,深圳无间设计,什么是优化设计,热门专业平衡二叉查找树
普通平衡二叉查找树
平衡二叉树定义是按照有序排列成树状#xff0c;左子树数据大于右子树#xff0c;任意节点的左右子树高度不能大于1 优点#xff1a;可以保证绝对的平衡 缺点#xff1a;当进行删除节点和新增节点#xff0c;树进行自平衡的时候左子树数据大于右子树任意节点的左右子树高度不能大于1 优点可以保证绝对的平衡 缺点当进行删除节点和新增节点树进行自平衡的时候需要频繁树旋转性能比较低
红黑树
红黑树也是一种平衡二叉树但是定义不同红黑树要求是每个节点要么是红色节点要么是黑色节点叶子节点都是黑的如果节点是红的那么子节点一定是黑色的不可以出现连续的红节点可以出现连续的黑节点任何子树的黑节点个数需要保证相同 优点红黑树是普通红黑树的改进版本可以看出允许连续黑节点这样就可以打破任意节点的左右子树高度不能大于1的规则没有要求绝对的平衡对于删除和新增可以一定程度减少树的旋转
应用范围适用于数据的查找但是数据量比较大情况依然树的高度会很高只有二叉所以一般用于内存操作不适合IO操作比如JDK的HashMap就使用了这个结构来提高检索速度
平衡多路查找树
b树
定义一个m阶的树要求每个节点都只能包含m-1个节点也意味着每个节点只能有m-1个子节点同时也要满足平衡树的定义左右子树高度差不能大于1
优点 相对于平衡二叉树这里变成了多路可以容纳更多数据同时树的高度也不会很高这样查找效率更高 缺点效率不是很稳定因为非叶子节点也是存全量数据的同时进行范围查找也不方便需要进行中序遍历之类的。还有一点就是建立二级索引也要存全量数据很不方便而且非叶子节点存全量数据会使得单个节点在有限数据字节文件情况下存的数据比较少树的高度依然会比较高
b树
定义一个m阶的树要求每个节点都只能包含m-1个节点也意味着每个节点只能有m-1个子节点同时也要满足平衡树的定义左右子树高度差不能大于1但是全量数据只存在叶子节点非叶子节点只存关键检索数据 优点数据只存叶子节点意味着检索的性能都稳定的同时非叶子节点也只存关键字数据这样树的高度相比b树会更低同时叶子节点和非叶子节点都是有链表相连范围查询也比较方便还有可以比较方便建立二级索引不需要存全量数据只要存索引和一级索引数据相关联就可以。
应用范围适合用于大型中间件的存储树的高度很低IO操作次数很少。比如mysql数据库就是使用这种结构方便进行范围查找和二级索引的灵活建立。
