https://juejin.cn/post/7025431070166237220
有序表是接口名，一个技术标准，AVL，SB树，红黑树，跳表，B树，B+树等都是有序表的具体实现类。
有序表要求的性能为logN。
有序表能够实现的功能：搜索二叉树的的增删改查。
搜索二叉树 BST
BST-Binary Search Tree又称之为二叉排序数、二插查找树。
平衡搜索二叉树 AVL
SB树 Size-Banlence-Tree
标准：
任何以叔叔结点为头的子树的结点个数不小于任何一个以自己侄子为头结点的子树的结点个数
这种平衡性在极端情况下，如果左子树节点比较少，右子树节点比较多，在满足上述规则的情况下，右子树的个数不会超过左子树个数的2倍。
因此任意节点的左右子树节点个数和的比值不会大于2，在维持这样一个平衡性的情况下，树的高度依然可以近似地维持在一个logN的水平。
SBT的优势，在删除节点的时候不进行平衡性的调整，只在添加节点的时候进行平衡性的调整，通过调整的递归行为能够保证树的平衡性，减少了删除节点是进行平衡性调整。
时间复杂度，最大添加节点个数N，logN。
基于积压结构的实现：SB，红黑树，Hash表，ArrayList
有积压结构的算法长用于磁盘IO
AVL树平衡性调整最敏感，每次增加删除数据都要进行平衡性调整，如果卸载硬盘上，硬盘IO的瓶颈频繁到来，不适合应用于硬盘结构上，而234树，红黑树，B树，B+树往往应用于硬盘结构上呢，因为没有那么频繁的调整结构，IO迎来瓶颈的时刻少。
跳表
给定一个数组arr和两个整数a和b，求arr中有多少个子数组累加和在[a,b]这个范围上。返回达标的子数组数量。
抽象化过程，分别求出以i(0=
例如Eg:
如原数组arr0-10上累加和为100，求以元素arr[10]结尾的并且子数组和在[40,80]上的所有子数组个数。
累加和数组sum[10]=100,
如果arr[2]=30，则表示肯定对应得到原数组arr3-10上的累加和为70，得到一个满足条件的子数组3-10，
如果arr[1]=10，则表示肯定对应得到原数组arr2-10上的累加和为90，得到一个不满足条件子数组2-10。
所以求解上述等价于求累加和数组sum[10]之前的元素，有几个在[20,60]范围上。
每次的累加和放在一个黑盒中，原数组遍历到i的时候，黑盒中存放的是i之前的累加和数组元素的值，该黑盒支持三种操作
- 能够存重复数字（有序表的查询）
- 能够向其中添加元素
- 能够查询
若有收获，就点个赞吧
0 人点赞
