注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Leo

笑:胸怀,傲:实力,才能笑傲江湖。

 
 
 

日志

 
 

跳跃链表  

2017-06-19 19:42:56|  分类: 技术管理 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

           二叉树是一种常见的数据结构。它支持包括查找、插入、删除等一系列操作。但它有一个致命的弱点,就是当数据的随机性不够时,会导致其树形结构的不平衡,从而直接影响算法的效率。

              跳跃链表(Skip List)是1987年才诞生的一种崭新的数据结构,它在进行查找、插入、删除等操作时的期望时间复杂度均为O(logn),有着近乎替代平衡树的本领。而且最重要的一点,就是它的编程复杂度较同类的AVL树,红黑树等要低得多,这使得其无论是在理解还是在推广性上,都有着十分明显的优势。

              跳跃链表的最大优势在于无论是查找、插入和删除都是O(logn),不过由于跳跃链表的操作是基于概率形成的,那么它操作复杂度大于O(logn)的概率为,可以看出当n越大的时候失败的概率越小。

              另外跳跃链表的实现也十分简单,在平衡树中是最易实现的一种结构。例如像复杂的红黑树,你很难在不依靠工具书的帮助下实现该算法,但是跳跃链表不一样,你可以很容易在半个小时内就完成其实现。

              跳跃链表的空间复杂度的期望为O(n),链表的层数期望为O(logn)


#ifndef _LEO_SKIPLIST_H_
#define _LEO_SKIPLIST_H_
#include <iostream>
#include <cstdlib>

template <typename Key, typename Type>
struct SkipListNode
{
Key key;
Type value;
SkipListNode<Key, Type>* forward[1];
};
template<typename Key, typename Type, int MaxLevel = 15>
class SkipList
{
public:
SkipList();
~SkipList();
public:
bool Insert(const Key& key, const Type& type);
bool Remove(const Key& key, Type& type);
bool Search(const Key& key, Type& type);
void Print();
int GetSize() { return m_iSize; }
private:
typedef SkipListNode<Key, Type>* TDSkipListNode;
void NewNodeOfLevel(TDSkipListNode& pSkipListNode, int iLevel = 0);
int RandomLevel();
int m_iLevel;
int m_iSize;
TDSkipListNode m_ListHeader;
TDSkipListNode m_ListEnd;
};
#endif //_LEO_SKIPLIST_H_

#include "leo_skiplist.h"
template<typename Key, typename Type, int MaxLevel>
SkipList<Key, Type, MaxLevel>::SkipList()
{
m_iSize = 0;
m_iLevel = 0;
NewNodeOfLevel(m_ListEnd);
//set max key in m_ListEnd  
m_ListEnd->key = 0x7fffffff;

NewNodeOfLevel(m_ListHeader, MaxLevel);
for (int i = 0; i < MaxLevel; i++)
{
m_ListHeader->forward[i] = m_ListEnd;
}
}
template<typename Key, typename Type, int MaxLevel>
SkipList<Key, Type, MaxLevel>::~SkipList()
{
TDSkipListNode pNode = m_ListHeader;
TDSkipListNode pTNode = NULL;
while (pNode != m_ListEnd)
{
pTNode = pNode->forward[0];
free(pNode);
pNode = pTNode;
}
//free m_ListEnd
free(pNode);
}
template<typename Key, typename Type, int MaxLevel>
void SkipList<Key, Type, MaxLevel>::NewNodeOfLevel(TDSkipListNode& pSkipListNode, int iLevel = 0)
{
int size = sizeof(SkipListNode<Key, Type>) + iLevel * sizeof(TDSkipListNode);
pSkipListNode = (TDSkipListNode)malloc(size);
}
//而插入列的“高度”较前者来说显得更加重要,也更加难以确定;
//由于它的不确定性,使得不同的决策可能会导致截然不同的算法效率;
//为了使插入数据之后,保持该数据结构进行各种操作均为O(logN)复杂度的性质;
//我们引入随机化算法(Randomized Algorithms);
template<typename Key, typename Type, int MaxLevel>
int SkipList<Key, Type, MaxLevel>::RandomLevel()
{
int iLevel = 0;
while (1)
{
if (rand() % 2 == 0) 
iLevel++;
else break;
}
return iLevel < MaxLevel ? iLevel : MaxLevel - 1;
}
template<typename Key, typename Type, int MaxLevel>
bool SkipList<Key, Type, MaxLevel>::Insert(const Key& key, const Type& type)
{
TDSkipListNode pTUpdate[MaxLevel], pNode = m_ListHeader;
//这里是倒序的,从下往上排序;
for (int i = m_iLevel; i >= 0; i--)
{
while (pNode->forward[i] != m_ListEnd && pNode->forward[i]->key < key)
{
//这里pNode设置之后,i还是前面的值,并没有从新的pNode的0开始;
//在跳表中,下一级直接从上一级的i开始,不从0开始;
pNode = pNode->forward[i];
}
//判断当前节点的下一节点如果不小于key值,那么就保存这个当前的点;
//然后在遍历当前节点的下一级,再继续比较节点;
//保存每一层位置上的最后指针的前驱;
pTUpdate[i] = pNode;
}

//找到当前节点的下一节点,如果下一节点等于key,那就只更新一下;
//返回该节点已经存在;
pNode = pNode->forward[0];
if (pNode != m_ListEnd && pNode->key == key)
{
pNode->value = type;
return false;
}
//生成一个随机数作为层次;
int iLevel = RandomLevel();
if (iLevel > m_iLevel)
{
iLevel = ++ m_iLevel;
pTUpdate[iLevel] = m_ListHeader;
}
//新建节点并准备插入跳表;
TDSkipListNode newNode;
NewNodeOfLevel(newNode, iLevel);
newNode->key = key;
newNode->value = type;
//设置该点各层的后续指向节点;
for (int i = lev; i >= 0; i--)
{
pNode = pTUpdate[i];
newNode->forward[i] = pNode->forward[i];
pNode->forward[i] = newNode;
}
//容量++;
++ m_iSize;
return true;
}
template<typename Key, typename Type, int MaxLevel>
bool SkipList<Key, Type, MaxLevel>::Remove(const Key& key, Type& type)
{
TDSkipListNode pTUpdate[MaxLevel], pNode = m_ListHeader;
for (int i = m_iLevel; i >= 0; i--)
{
while (pNode->forward[i] != m_ListEnd && pNode->forward[i]->key < key)
pNode = pNode->forward[i];
pTUpdate[i] = pNode;
}

pNode = pNode->forward[0];
if (pNode != m_ListEnd && pNode->key == key)
{
type = pNode->value;
for (int i = 0; i <= m_iLevel; i++)
{
if (pTUpdate[i]->forward[i] != pNode)
break;
pTUpdate[i]->forward[i] = pNode->forward[i];
}
free(pNode);
while (m_iLevel > 0 && m_ListHeader->forward[m_iLevel] == m_ListEnd)
m_iLevel --;
m_iSize --;
return true;
}
else
return false;
}
template<typename Key, typename Type, int MaxLevel>
bool SkipList<Key, Type, MaxLevel>::Search(const Key& key, Type& type)
{
TDSkipListNode pNode = m_ListHeader;
for (int i = m_iLevel; i >= 0; i--)
{
while (pNode->forward[i] != m_ListEnd && pNode->forward[i]->key < key)
pNode = pNode->forward[i];
}
pNode = pNode->forward[0];
if (pNode != m_ListEnd && key == pNode->key)
{
type = pNode->value;
return true;
}
return false;
}
template<typename Key, typename Type, int MaxLevel>
void SkipList<Key, Type, MaxLevel>::Print()
{
TDSkipListNode pNode = m_ListHeader;
while (pNode->forward[0] != m_ListEnd)
{
std::cout << "Key:" << pNode->forward[0]->key << "Value:" << pNode->forward[0]->value << std::endl;
pNode = pNode->forward[0];
}
}
  评论这张
 
阅读(22)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017