最经典的就是Heap的应用, 效率也相当高, 当时操作仅限Put Pop. 无法实现Rank, Index等操作, 很多时候结构使用局限性较大. 甚至会出现一些每次需要Index, Rank的时候, 先Copy一个数组, Sort(排序一次), 通过数组Index. 数据量非常小的情景下, 实则怎么操作都没什么大问题. 量巨大的时候, 效率异常低下. 所以以下是我曾经为了优先队列的一些研究, 我写文章很随意, 如果有错的我后面更正, 我写完自己都不会看.
AVL 无论什么情况都是优于红黑树, 实在想put速度快, 设置高度差为3旋转, 或者优化成按照当前高度旋转,效率更高一些. 红黑树测试来看没多大意义. 不认可也可以自己去测试, 或者找相关测试观测一下.
- SkipList
跳表是一个随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis和LevelDB, Rocksdb中都有用到。 它采用随机技术决定链表中哪些节点应增加向前指针以及在该节点中应增加多少个指针。跳表结构的头节点需有足够的指针域，以满足可能构造最大级数的需要，而尾节点不需要指针域。 采用这种随机技术，跳表中的搜索、插入、删除操作的时间均为O(logn)，然而，最坏情况下时间复杂性却变成O(n)。相比之下，在一个有序数组或链表中进行插入/删除操作的时间为O(n)，最坏情况下为O(n)。
- 这里更正一下, 我个人认为跳表的Put效率远不如红黑树,AVL, 而且有大量测试都验证不如. 如果有异议可以纠正我错误.
- 跳表有index属性, 优先排序等. 所以我认为indextree 可以处理成更好的一个处理结构.
- Size Balance Tree
简称SBT 可以从链接山查看具体介绍, 拥有与跳表一样的Rank, Select(Index), 等属性, 平衡树put,remove的操作都涉及范围内的旋转与调整, 需要锁树, 但是链表, 可以只锁相邻节点. 达到高效的并行处理.
- 通过各种语言和测试, 并不像论文所述, 并不优于AVL 和 RBTree. 感觉有夸大的嫌疑. 如果有异议可以纠正我错误.
- Index Balance Tree
简称[IBT] 这个树是我根据宽度平衡的一些构想并实现, 我在实现这个树结构的时候,完全不知道SBT的存在(知道我不会写了). 通过大量的结果测试, 写出由一个平衡因子作旋转的平衡树, 具体以后再写. 实测性能不输RBTree(红黑), AVLTree, SBT SkipList并且有 SBT等同的属性. 在一些特殊倾斜的数据集会略输. 后面我想用vbt代替skiplist实现一个可以并行处理的顺序写简单例子(工作不忙的前提下).
- Put 单位: 纳秒/操作
| Put(ns\op) | 500 | 5000 | 50000 | 500000 | 5000000 |
|---|---|---|---|---|---|
| SkipList | 65 | 91 | 222 | 975 | 1921 |
| IndexTree | 81 | 102 | 248 | 614 | 1155 |
| SBT | 73 | 100 | 208 | 701 | 1323 |
| AVLTree | 68 | 88 | 189 | 545 | 1059 |
| RBTree | 73 | 88 | 195 | 589 | 1084 |
- Get 单位: 纳秒/操作
| Get(ns\op) | 500 | 5000 | 50000 | 500000 | 5000000 |
|---|---|---|---|---|---|
| SkipList | 38 | 64 | 212 | 1009 | 2156 |
| IndexTree | 31 | 48 | 129 | 454 | 956 |
| SBT | 30 | 45 | 148 | 443 | 905 |
| AVLTree | 31 | 47 | 113 | 455 | 931 |
| RBTree | 37 | 55 | 170 | 531 | 1027 |
git submodule init #初始化模块
git submodule update #更新子模块
sh run.sh #运行测试rm -f bin/main
g++ -std=c++17 -fpermissive -g -O2 -Wno-unused-parameter -Wno-unused-function -Wno-sign-compare -Wno-maybe-uninitialized -Iinclude -Llib src/compare.hpp src/indextree.hpp src/sbt.h src/main.cpp src/avl.hpp -o bin/main
* Put 单位: 纳秒/操作
| Put(ns\op) | 500 | 5000 | 50000 | 500000 | 5000000 |
| ---------- | --- | ---- | ----- | ------ | ------- |
| SkipList | 65 | 91 | 222 | 975 | 1921 |
| IndexTree | 81 | 102 | 248 | 614 | 1155 |
| SBT | 73 | 100 | 208 | 701 | 1323 |
| AVLTree | 68 | 88 | 189 | 545 | 1059 |
| RBTree | 73 | 88 | 195 | 589 | 1084 |
* Get 单位: 纳秒/操作
| Get(ns\op) | 500 | 5000 | 50000 | 500000 | 5000000 |
| ---------- | --- | ---- | ----- | ------ | ------- |
| SkipList | 38 | 64 | 212 | 1009 | 2156 |
| IndexTree | 31 | 48 | 129 | 454 | 956 |
| SBT | 30 | 45 | 148 | 443 | 905 |
| AVLTree | 31 | 47 | 113 | 455 | 931 |
| RBTree | 37 | 55 | 170 | 531 | 1027 |-
skiplist 效果并不如所述的理想. 只是在并行处理上有巨大的优势(仅在对树理解不深的情况下).
-
实际优先队列的选择上我更推荐平衡树带Size属性的实现. 这里有一个go的实现 https://github.com/474420502/structure/tree/master/tree/itree (换了更好的实现.最终版, 限制在logn + 1高度内, 因为size没高度信息, 如果不递归到底部不可能达到avl的高度平衡)
-
SBT 它有个递归旋转的维护, 导致put效率肯定比其他树低. 但是由于递归对size平衡很好. 所以Get性能和avl接近.