当前位置:网站首页>跳表的实现
跳表的实现
2022-07-28 15:00:00 【今天也要写bug、】
跳表的实现
一般跳表会设计一个最大层数maxLevel(在Redis中为32)的限制,其次会设置一个多增加一层的概率p(在Redis中为0.25)。
产生越高的节点层数,概率越低。
- 节点层数至少为1。而大于1的节点层数,满足一个概率分布。
- 节点层数恰好等于1的概率为1-p。
- 节点层数大于等于2的概率为p,而节点层数恰好等于2的概率为p(1-p)。
- 节点层数大于等于3的概率为p2,而节点层数恰好等于3的概率为p2 *(1-p)。
- 节点层数大于等于4的概率为p3,而节点层数恰好等于4的概率为p3*(1-p)。
当p=1/2时,每个节点所包含的平均指针数目为2。当p=1/4时,每个节点所包含的平均指针数目为1.33。
struct SkipNode
{
//跳表的一个节点
SkipNode(int val,int level)
{
_val=val;
_next.resize(level,nullptr);
}
//当前节点的值
int _val;
//当前节点指向下一个节点的指针数组
vector<SkipNode*>_next;
};
class Skiplist {
private:
typedef struct SkipNode Node;
//带一个头结点
Node* _head;
//最大高度为32
size_t _max_level=32;
double _p=0.25;
public:
Skiplist() {
//头结点一开始为1层
_head=new Node(-1,1);
srand(time(0));
}
bool search(int target) {
Node*cur=_head;
//当前的层数,用下标表示
int level=_head->_next.size()-1;
//如果查找到小于0的下标,说明没有找到
while(level>=0)
{
//target和cur->next[level]->_val比较
//比它小向下走,比它大向右走
//当前节点下一个位置是空时也往下走
if((cur->_next[level]&&cur->_next[level]->_val>target)||cur->_next[level]==nullptr)
{
level--;
}
else if(cur->_next[level]->_val<target)
{
cur=cur->_next[level];
}
else//相等,找到了
{
return true;
}
}
return false;
}
//找寻num之前的节点的指针
vector<Node*> FindPreNode(int num)
{
//保存插入位置每一层,前一个节点的指针
vector<Node*>prev(_max_level,_head);
Node*cur=_head;
//然后找插入的位置
int level=_head->_next.size()-1;
while(level>=0)
{
//如果比下一个位置大或者等于,往下走
//我们将该值插到相等值的最前面
if((cur->_next[level]&&cur->_next[level]->_val>=num)||cur->_next[level]==nullptr)
{
//往下走的时候,记录这些值,方便插入的时候使用
prev[level]=cur;
level--;
}
//比下一个位置的值小于,往右走
else if(cur->_next[level]&&cur->_next[level]->_val<num)
{
cur=cur->_next[level];
}
}
return prev;
}
void add(int num) {
//记录应该插入的位置
vector<Node*> prev=FindPreNode(num);
//获取随机的层数
int n=RandomLevel();
Node*newnode=new Node(num,n);
//判断获取的层数和当前头节点的层数
//当前头结点的层数有可能比新获取的层数小
if(_head->_next.size()<n)
{
_head->_next.resize(n,nullptr);
}
//链接prev和newnode
for(int i=0;i<n;i++)
{
newnode->_next[i]=prev[i]->_next[i];
prev[i]->_next[i]=newnode;
}
}
int RandomLevel()
{
int level=1;
//RAND_MAX是rand()产生的最大值,乘上0.25,可以保证有0.25的几率进入while循环
while(rand()<=RAND_MAX*_p&&level<_max_level)
{
++level;
}
return level;
}
bool erase(int num) {
//找到每一层的前一个
vector<Node*> prev=FindPreNode(num);
//第一层不存在,或者第一层下一个位置比num大,比如1(prev) 5(prev[0]->_next)这种情况
//说明num不在表中,比如num=3
if(prev[0]->_next[0]==nullptr||prev[0]->_next[0]->_val!=num)
{
//没找到这个值
return false;
}
else
{
//prev[0]->_next[0]=num,此时需要删掉这个节点
Node* del=prev[0]->_next[0];
//del节点每一层的前后指针链接起来
for(int i=0;i<del->_next.size();++i)
{
prev[i]->_next[i]=del->_next[i];
}
delete del;
//删完以后,头结点可能需要降低高度
//比如删除的节点高度是10,删完之后,整个表最高的节点只有5,但是头结点仍然为10
int i=_head->_next.size()-1;
while(i>=0)
{
//从上往下找到第一个非空的节点,然后删掉它
if(_head->_next[i]==nullptr)
{
i--;
}
else
{
break;
}
}
_head->_next.resize(i+1);
}
return true;
}
};
skiplist跟平衡搜索树和哈希表的对比
- skiplist相比平衡搜索树(AVL树和红黑树)对比,都可以做到遍历数据有序,时间复杂度也差不多。skiplist的优势是:a、skiplist实现简单,容易控制。平衡树增删查改遍历都更复杂。 b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链,平衡因子/颜色等消耗。skiplist中p=1/2时,每个节点所包含的平均指针数目为2;skiplist中p=1/4时,每个节点所包含的平均指针数目为1.33;
- skiplist相比哈希表而言,就没有那么大的优势了。相比而言a、哈希表平均时间复杂度是O(1),比skiplist快。b、哈希表空间消耗略多一点。skiplist优势如下:a、遍历数据有序 b、skiplist空间消耗略小一点,哈希表存在链接指针和表空间消耗。c、哈希表扩容有性能损耗。d、哈希表再极端场景下哈希冲突高,效率下降厉害,需要红黑树补足接力。
边栏推荐
猜你喜欢

Solve the problem that the right-click menu "edit with idle" of the 『 py 』 file is invalid or missing

High precision absolute angle sensor application high speed angle monitoring

激光测距仪非接触式地表裂缝监测仪

2021 Kent interview question 3

MLX90640 红外热成像仪测温传感器模块开发笔记(八)

One channel encoder, two channels Di speed measurement, RS485 serial port connected to one channel do alarm module ibf151

高精度绝对角度传感器应用高速度角度监测

12V脉冲转速测量转24V电平信号转换变送器

占空比开关量输出高速脉冲计数器RTUModbus模块IBF63

Two special functions (arrow function and method)
随机推荐
Remote serial port server (adapter) UART to 1-wire application
js中的for循环总结
仅需三步 轻松实现远程办公
js 栈
Principle and application of low cost / small volume module rs485/232 to analog signal ibf33
Learning methods 123
便携式钻孔测斜仪数据采集仪测量原理与测斜探头的连接及使用方法
使用py,根据日志记录自动生成周报
【直播预约】数据架构演进下的新挑战——上海站
光学雨量计对比翻斗式雨量计的优势
What are the process specifications of software testing? How to do it?
2021 肯特面试题2
One channel encoder, two channels Di speed measurement, RS485 serial port connected to one channel do alarm module ibf151
记录一下 clearfix 清除浮动
占空比开关量输出高速脉冲计数器RTUModbus模块IBF63
JS queue
Have you seen the management area decoupling architecture? Can help customers solve big problems
JS linked list 01
A failed cracking experience
激光测距仪非接触式地表裂缝监测仪