- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
书接前文.
前文书 《红黑树是怎么来的》 我们讲了通过红黑树(本质上是 2-3 树或者 2-3-4 树思想)来维护二叉搜索树的平衡性。从红黑树的实现来看,虽然相对于 2-3 树来说是简化了不少,但仍然是相当复杂的.
有没有更加简单的实现方案呢?
在前文 《二叉搜索树的本质》 中我们通过 将有序数组的二分查找链表化 ,最终得到二叉搜索树.
这次,我们还是从有序数组的二分查找开始,看看能否发明什么新的数据结构.
和以前不同的是,这次我们先将有序数组链表化:
如图。现在我们考虑如何在该链表中查找元素 40.
最简单的做法是从表头开始往后遍历,时间复杂度 O(n)——显然不是我们想要的.
我们的初步想法是:能否在这个链表上执行二分搜索?
对于数组来说,我们可以通过地址偏移立即定位到中间元素(15),然后发现 40 比 15 大,继续对 15 后面的元素执行二分查找即可.
链表的困境在于,它没法通过地址偏移来快速定位元素.
不过我们并不死心——有没有什么奇技淫巧来模拟链表上的二分查找?
既然对于链表,只能通过指针来遍历元素,那我们能否通过给节点 1、15、60(头尾以及二分查找涉及到的中间元素)之间建立额外的指针来实现快速跳转呢?
如图:
我们建立了一个额外的链表(1→15→60),且该链表的每个节点都有一个额外指针指向下一层的同名节点.
有什么用呢?
再来看看如何查找元素 40.
我们可以先查上面(第二层)那个链表,只需两步就走到元素 15,发现 40 介于 15 和 60(15 的下一个元素)之间,于是我们通过 15 的“下降”指针来到第一层链表同名节点 15,然后在第一层链表中继续往后查找.
如图:
和直接在原始链表上遍历不同,通过添加一层“索引”链表,我们能和二分查找一样“直达”中间元素,搜索效率一下子提升了一倍.
那么,这个查询能否再优化一下呢?
上图中,15 以后的搜索仍然是线性的。我们同样可以对 1-15、15-60 之间的两段子链表再次建立“索引链表”:
乍看有点小复杂,实际上它仍然是对二分查找的模拟.
我们从上层往下层看.
第三层相当于执行第一次二分,标的元素是 15,然后根据实际情况到 1-15 或者 15-60 区间去查找.
第二层则是在第三层(第一次二分查找)的基础上做的第二次二分,得到更细粒度的查找区间.
所以说,如果我们从最上层索引链表往最下层方向逐层查找,就相当于模拟有序数组一次次的二分查找.
妙哉! 。
我们看看建立两层索引后元素 40 的查找路径:
和一层相比,查找路径要短很多.
和普通链表相比,这种链表通过索引“跳过”了一些节点,以提升搜索效率,因而我们给它起个“望文生义”的名字就叫 跳表 (skiplist).
由于跳表本质上是对二分法的模拟,所以其搜索时间复杂度同二分搜索一样是 O(logn).
跳表的节点(最底层除外)除了要指向后继节点(如果是双向链表还要指向前驱节点),还需要指向下层同名节点,所以节点结构初步定义如下:
class Node {
key: number
val: unknown
// 后继节点
next: Node | null
// 下层节点(比普通链表多出来的指针)
down: Node | null
public constructor(key: number, val: unknown) {
// ......
}
}
上图中节点 15 表示如下:
// 第三层的 node15
const node15_l3: Node = {
key: 15,
val: 15,
next: node60_l3,
down: node15_l2,
}
// 第二层的 node15
const node15_l2: Node = {
key: 15,
val: 15,
next: node30_l2,
down: node15_l1,
}
// 第一层的 node15
const node15_l1: Node = {
key: 15,
val: 15,
next: node20_l1,
down: null,
}
我们分析一下上面的数据结构定义有没有什么问题.
首先说明一点,通过建立索引链表来提升搜索速度属于典型的用 空间换时间 .
不过,我们为同一个元素(如上例中的 15)在每一层都建立了一个独立的对象——这是不是过于铺张浪费了?
我们分析一下上面三个 object 的特点,看看有没有什么优化空间:
所以我们可以尝试将同一元素的各层节点合而为一:
class Node {
public key: number
public val: unknown
// 该节点各层的后继节点指针数组
public nexts: (Node | null)[]
public constructor(key: number, val: unknown) {
// ......
}
}
如上,我们将 next 和 down 两个指针合入到 nexts 指针数组中,nexts[i] 表示该节点在第 i + 1 层的后继节点.
改造后图示如下:
如上图,我们做了四方面的改造:
最后我们定义出完整的数据结构:
class SkipList {
// 表头指针。为方便处理,表头不表示实际节点, 作为哨兵存在
protected head: Node
// 跳表中元素个数
protected length: number
// 跳表层数
protected level: number
public constructor() {
// 创建表头
this.head = new Node(-Infinity, undefined)
this.length = 0
this.level = 0
}
}
我们看看如何查找节点 40.
任何查找都从表头 head 且从最上层开始,到第一层为止:
如图:
代码如下:
class SkipList {
// ......
/**
* 根据 key 查找 value 并返回,如果没找到则返回 undefined
* @param key
*/
public search(key: number): unknown {
if (!this.length) {
return
}
// 从 head 开始找
let node = this.head
// 从最高层开始往下搜索,直到搜到第一层
for (let i = this.level - 1; i >= 0; i--) {
// 如果当前节点该层存在后继节点,且该后继节点的 key 小于等于目标 key,则跳到该后继节点
while (node.nexts[i] && node.nexts[i].key <= key) {
node = node.nexts[i]
}
// 从 node 进入到下一层继续查找
}
return node.key === key ? node.val : undefined
}
}
超简单有没有! 。
在讲插入之前,我们先思考一个问题:链表中的某个元素应该有多少层(或者说需要给它建多少层索引)?
前面我们通过二分法推导出多层索引的概念。但如果在实际操作中,每次插入一个元素后都用二分法思想去确定元素的索引层数,可能一次插入会导致大范围的索引重建(比如原本通过二分法拿到标的节点是 a,插入新元素后再次二分拿到的标的很可能不再是 a).
我们也可以采用类似 B 树的裂变思想,比如我们规定第 n 层两个节点之间所囊括的 n - 1 层元素数量不可超过 x,一旦超过就触发裂变以生成新的索引(裂变可能是级联的)。不过其实现起来也比较复杂.
跳表的设计采用了一种简单粗暴但很有效的方法: 概率法 .
思想是这样的:我们规定第 n 层的元素数量是其下一层(n - 1)数量的 1/N。换句话说,一个元素有 1/N 的概率会向上建一层索引.
以 N = 4 为例.
假设我们想插入元素 22——该元素需要建立几层索引呢?
有 3/4 的概率不建立任何索引(也就是只有最底下一层).
有 1/4 的概率建立 1 层索引.
有 1/4 * 1/4 即 1/16 的概率建 2 层索引.
有 1/4 * 1/4 * 1/4 即 1/64 的概率建 3 层索引.
依此类推.
如此得到的数据结构本质上是一棵 N 叉树(这里是 4 叉树).
我们通过如下代码计算一个新节点的层数信息:
class SkipList {
// 最大层数限制
protected static readonly MAX_LEVEL = 32
// 上层元素数是下层数量的 1/N(相当于 N 叉树)
protected static readonly N = 4
// ......
/**
* 随机生成 level 层数
* 从最底层开始,每增加一层的概率为 1/N
*/
protected randomLevel(): number {
let level = 1
while (Math.round(Math.random()*10000000) % SkipList.N === 0) {
level++
}
return Math.min(level, SkipList.MAX_LEVEL)
}
}
这里我们通过将生成的随机数对 N 取模和 0 比较来模拟 1/N 的概率(比如 N = 4,则取模后为 0-3).
我们看如何插入元素 22.
首先要确定 22 在原始链表(第一层链表)中的位置,该过程实际就是搜索过程,时间复杂度 O(logn).
搜索过程如图:
我们找到应该在 20 和 25 两个节点之间插入 22.
假如我们通过 randomLevel() 得到层数是 5,插入后整个跳表长这样:
观察上图发现:
经上面分析发现,整个插入过程中,关键是找出每层的前驱节点。代码如下:
class SkipList {
/**
* 搜索关键字 key,返回其搜索路径上经过的每层的前驱节点数组
* 即每层返回其左边相邻节点
* @param key - 关键字
* @returns 关键字 key 在每层的前驱节点数组
*/
private searchPrevNodes(key: number): Node[] {
// 记录每层走到的最右边的位置(也就是目标节点的前驱节点)
const prevNodes: Node[] = []
// 从 head 开始
let node = this.head
// 从最上层开始往下找
for (let i = this.level - 1; i >= 0; i--) {
// 如果当前节点该层存在后继节点,且该后继节点的 key 小于 key,则跳到该后继节点
while (node.nexts[i] && node.nexts[i].key < key) {
node = node.nexts[i]
}
// 下沉之前记录该节点作为本层访问到的最右节点
prevNodes[i] = node
}
// 如果一个都没有(列表为空,this.level = 0 时),将 head 加入进去
if (!prevNodes.length) {
prevNodes[0] = this.head
}
return prevNodes
}
}
元素插入逻辑代码如下:
class SkipList {
// ......
/**
* 将 { key, val } 插入到跳表中
*/
public insert(key: number, val: unknown) {
// 获取搜索路径上的各层前驱节点
const prevNodes = this.searchPrevNodes(key)
// 创建新节点
const newNode: Node = { key, val, prev: null, nexts: [] }
// 计算新节点的索引层数
const level = this.randomLevel()
// 逐层处理 next 指针
for (let i = 0; i < level; i++) {
// prevNodes 里面仅有原先 this.level 层的最右 node,而新 level 可能高于原 level,
// 该情况下,超出的层在 prevNodes 里面没有对应节点,则直接取 head
const leftNode = prevNodes[i] ?? this.head
// 变更 next 指针
newNode.nexts[i] = leftNode.nexts[i]
leftNode.nexts[i] = newNode
}
if (level > this.level) {
this.level = level
}
this.length++
}
}
插入过程的平均时间复杂度是 O(logn).
考虑删除节点 22,删除后整个跳表结构如下:
跳表元素的删除本质就是插入的逆操作:将该节点从各层抹除,即将该节点各层的前驱节点的 next 指针指向该节点在该层的后继节点.
插入过程中可能产生新的层(head 层数随之增长),而删除则可能造成层数减少(head 层数收缩).
通过观察图示不难发现,删除后和插入前的结构竟然是一模一样的,如此的稳定性真让人叹为惊奇.
不同于其他平衡树,跳表的插入和删除不但完全互逆,而且也没有复杂的递归重建过程——这正是跳表这种 概率型数据结构 的简单性之精华所在.
删除代码如下:
class SkipList {
// ......
public delete(key: number) {
// 获取搜索路径上的各层前驱节点
const prevNodes = this.searchPrevNodes(key)
// 待删除的节点就是第一层前驱节点的该层 next 指针所指向的节点
const current = prevNodes[0].nexts[0]
if (!current || current.key !== key) {
return
}
// 从下往上,处理各层的 next 指针
// 需要处理的层:待删节点的索引层数
for (let i = 0; i < current.nexts.length; i++) {
prevNodes[i].nexts[i] = current.nexts[i]
current.nexts[i] = null
// 如果该层的前驱节点是 head,且调整后其 next 指向 null/undefined,说明该层不再有有效节点,需要将层数减 1
if (!this.head.nexts[i]) {
this.level--
}
}
this.length--
}
}
对比红黑树的插入和删除实现,你会惊于跳表的实现是如此简单。为何?
我们假设不使用概率来决定新节点的索引层数,就很可能需要采用类似 B 树的方案,通过限制两索引节点之间所辖节点数来决定索引的分裂与合并。比如规定任何两索引节点之间所辖节点数必须在 N/2 到 N 之间,小于 N/2 则谋求合并,超过 N 则分裂。如此必然会带来复杂的级联分裂与合并逻辑.
相反,跳表采用了简单粗暴但同样有效的概率法,在插入元素的时候,通过概率计算得出索引层数,而更新索引(插入和删除)仅影响该节点在各层的前驱节点,影响非常小,更新过程异常简单.
所以说,这种数据结构的 概率性带来了其简单性 .
另外, 分级索引 是人类信息检索领域的一个重要思想,图书检索、书本目录、文件系统、域名(DNS 查询)、ip 地址、操作系统页表等等的设计都体现了该思想.
本文完整代码参见 github: https://github.com/linzier/algo-ts.
为讲解的简单性,本文使用的是单向链表,github 中实现的是双向链表.
最后此篇关于有了红黑树,为啥还要跳表?的文章就讲到这里了,如果你想了解更多关于有了红黑树,为啥还要跳表?的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
关于 B 树与 B+ 树,网上有一个比较经典的问题:为什么 MongoDb 使用 B 树,而 MySQL 索引使用 B+ 树? 但实际上 MongoDb 真的用的是 B 树吗?
如何将 R* Tree 实现为持久(基于磁盘)树?保存 R* 树索引或保存叶值的文件的体系结构是什么? 注意:此外,如何在这种持久性 R* 树中执行插入、更新和删除操作? 注意事项二:我已经实现了一个
目前,我正在努力用 Java 表示我用 SML 编写的 AST 树,这样我就可以随时用 Java 遍历它。 我想知道是否应该在 Java 中创建一个 Node 类,其中包含我想要表示的数据,以及一个数
我之前用过这个库http://www.cs.umd.edu/~mount/ANN/ .但是,它们不提供范围查询实现。我猜是否有一个 C++ 范围查询实现(圆形或矩形),用于查询二维数据。 谢谢。 最佳
在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出B树以及为什么MySQL数据库索引选择
书节上回,我们接着聊二叉树,N叉树,以及树的存储。 01、满二叉树 如果一个二叉树,除最后一层节点外,每一层的节点数都达到最大值,即每个节点都有两个子节点,同时所有叶子节点都在最后一层,则这个
树是一种非线性数据结构,是以分支关系定义的层次结构,因此形态上和自然界中的倒挂的树很像,而数据结构中树根向上树叶向下。 什么是树? 01、定义 树是由n(n>=0)个元素节点组成的
操作系统的那棵“树” 今天从一颗 开始,我们看看如何从小树苗长成一颗苍天大树。 运转CPU CPU运转起来很简单,就是不断的从内存取值执行。 CPU没有好好运转 IO是个耗费时间的活,如果CPU在取值
我想为海洋生物学类(class)制作一个简单的系统发育树作为教育示例。我有一个具有分类等级的物种列表: Group <- c("Benthos","Benthos","Benthos","Be
我从这段代码中删除节点时遇到问题,如果我插入数字 12 并尝试删除它,它不会删除它,我尝试调试,似乎当它尝试删除时,它出错了树的。但是,如果我尝试删除它已经插入主节点的节点,它将删除它,或者我插入数字
B+ 树的叶节点链接在一起。将 B+ 树的指针结构视为有向图,它不是循环的。但是忽略指针的方向并将其视为链接在一起的无向叶节点会在图中创建循环。 在 Haskell 中,如何将叶子构造为父内部节点的子
我在 GWT 中使用树控件。我有一个自定义小部件,我将其添加为 TreeItem: Tree testTree = new Tree(); testTree.addItem(myWidget); 我想
它有点像混合树/链表结构。这是我定义结构的方式 struct node { nodeP sibling; nodeP child; nodeP parent; char
我编写了使用队列遍历树的代码,但是下面的出队函数生成错误,head = p->next 是否有问题?我不明白为什么这部分是错误的。 void Levelorder(void) { node *tmp,
例如,我想解析以下数组: var array1 = ["a.b.c.d", "a.e.f.g", "a.h", "a.i.j", "a.b.k"] 进入: var json1 = { "nod
问题 -> 给定一棵二叉树和一个和,确定该树是否具有从根到叶的路径,使得沿路径的所有值相加等于给定的和。 我的解决方案 -> public class Solution { public bo
我有一个创建 java 树的任务,它包含三列:运动名称、运动类别中的运动计数和上次更新。类似的东西显示在下面的图像上: 如您所见,有 4 种运动:水上运动、球类运动、跳伞运动和舞蹈运动。当我展开 sk
我想在 H2 数据库中实现 B+ Tree,但我想知道,B+ Tree 功能在 H2 数据库中可用吗? 最佳答案 H2 已经使用了 B+ 树(PageBtree 类)。 关于mysql - H2数据库
假设我们有 5 个字符串数组: String[] array1 = {"hello", "i", "cat"}; String[] array2 = {"hello", "i", "am"}; Str
我正在处理树。每个节点都有带有 Tree * 值的对象。我读取的数据如下所示: 1 2 2 ... 这意味着,将 1 作为 0 的子节点,将 2 作为 1 的子节点,将 3 作为 o 2 的子节点。在
我是一名优秀的程序员,十分优秀!