原书出处
大数据日知录_架构与算法
03 大数据常用的算法与数据结构
上述算法中update数组用于临时存放查找searchKey路径时每层最后的节点,主要目的是记录信息,使得在插入节点时能像普通链表插入时一样修改新插入节点导致的各种指针变化。SkipList的插入算法整体逻辑也很清楚:首先与查找算法一样找到searchKey应该插入的位置,在查找过程中往update数组中记录查找路径每层最后的节点;如果找到相同key的节点,则只需更新其值即可,否则利用随机数确定新插入节点的层级,如果新节点层级数比目前链表中的MaxLevel要高,那么需要更新链表表头的层级指针信息并重设MaxLevel数值,然后生成新节点并插入链表,并根据update数组保留的信息调整各个层级的相关指针指向。
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html
EPUB SHA-256:e45b74c4bdd8959aef24f2a5183280eb73ec5f173108f8679a4bbf44bbd5b34d