【数据结构Python描述】跳跃表简介及使用跳跃表实现有序映射

时间:2021-2-20 作者:admin

文章目录

对于之前通过列表保存键值对的方式所实现的类字典映射,当映射中的键值对按照键的大小排序时,由于可以利用二分查找算法,因此查找某键值对可实现

O

(

l

o

g

n

)

O(logn)

O(logn)的最坏时间复杂度,但由于对映射进行这样的修改类操作的最坏时间复杂度为

O

(

n

)

O(n)

O(n)(当在列表索引为0的位置元素需要移动移动所有其他位置的元素),因此M[k] = vdel M[k]M为映射实例对象)操作的最坏时间复杂度为

O

(

n

)

O(n)

O(n)

事实上,在已知某节点位置的情况下,单链表可以在该位置处实现最坏时间复杂度为

O

(

1

)

O(1)

O(1)的节点增删等修改类操作,但单链表的缺点是不能像列表一样支持根据索引快速的进行查找操作,而是需要从头遍历链表。

因此,为了既能够实现快速的查找也能够实现快速的修改操作,本文即将介绍的跳跃表就通过改善链表在查找和修改操作之间找到了较好的效率平衡。

一、跳跃表简介

1. 跳跃表引入

首先,我们通过对普通单向线性链表进行一步一步的延展来引出跳跃表,假定单链表中元素有序排列

  • 如果需要对以下一般链表进行查找操作,则最坏时间复杂度为

    O

    (

    n

    )

    O(n)

    O(n)

【数据结构Python描述】跳跃表简介及使用跳跃表实现有序映射

  • 如果在上述一般链表基础上,每

    2

    1

    =

    2

    2^1=2

    21=2个节点,都有1个节点保存了从其位置往后第

    2

    1

    =

    2

    2^1=2

    21=2个节点的引用(如头结点除保存了元素3所在节点的引用,保存了元素6所在节点的引用),此时查找操作的最坏时间复杂度为

    n

    /

    2

    1

    +

    1

    \lceil {\left.n\middle/2^1\right.} \rceil+1

    n/21+1

【数据结构Python描述】跳跃表简介及使用跳跃表实现有序映射

  • 如果在上述链表基础上,每

    2

    2

    =

    4

    2^2=4

    22=4个节点中,都有1个节点保存了从其位置往后第

    2

    2

    =

    4

    2^2=4

    22=4个节点的引用(如头结点除保存了元素3和6所在节点的引用,保存了元素9所在节点的引用),此时查找操作的最坏时间复杂度为

    n

    /

    2

    2

    +

    2

    \lceil {\left.n\middle/2^2\right.} \rceil+2

    n/22+2

【数据结构Python描述】跳跃表简介及使用跳跃表实现有序映射

  • 如果在上述链表基础上,每

    2

    3

    =

    8

    2^3=8

    23=8个节点中,都有1个节点保存了从其位置往后第

    2

    3

    =

    8

    2^3=8

    23=8个节点的引用(如头结点除保存了元素3、6和9所在节点的引用,保存了元素21所在节点的引用),此时查找操作的最坏时间复杂度为

    n

    /

    2

    3

    +

    3

    \lceil {\left.n\middle/2^3\right.} \rceil+3

    n/23+3

【数据结构Python描述】跳跃表简介及使用跳跃表实现有序映射

因此,一般地,如果在普通链表基础上,对于所有满足

2

i

<

n

2^i\lt{n}

2i<n的正整数

i

i

i(即

i

log

2

n

i\le\lceil{\log_2n}\rceil

ilog2n),每

2

i

2^i

2i个节点中,都有1个节点还保存了从其位置往后第

2

i

2^i

2i个节点的引用,此时查找操作的最坏时间复杂度为

log

2

n

\lceil{\log_2n}\rceil

log2n

2. 跳跃表定义

上述经逐步优化的链表虽然可实现较为高效的查找操作,但是增删节点等修改类操作却十分不易实现,为此下面正式引入跳跃表:

首先,为描述方便,如果每

2

i

2^i

2i个节点中,都有1个节点还保存了从其位置往后第

2

i

2^i

2i个节点的引用,我们就称该节点具有

i

i

i阶引用,需要注意的是,这意味该节点还具有

i

1

i-1

i1

i

2

i-2

i2

\cdot\cdot\cdot

1

1

1阶引用。

基于以上假设,对于上述逐步优化的链表,其中100%的节点具有1阶引用,50%的节点具有2阶引用,25%的节点具有3阶引用,12.5%的节点具有4阶引用,以此类推。

然而,如果我们假设所有节点所具有的最高引用阶数为不大于

log

2

n

\lceil{\log_2n}\rceil

log2n的随机值,且仅限定具有不同最高阶引用的节点数量间的比例保持不变(如下图所示),这就形成了所谓的跳跃表(Skip List)。

此时,任意节点的

i

i

i阶引用并非一定指向从其位置开始第

2

i

1

2^{i-1}

2i1个节点,而是任何下一个至少具有

i

i

i阶引用节点或NIL(表示跳跃表的尾哨兵节点)

【数据结构Python描述】跳跃表简介及使用跳跃表实现有序映射

事实上,上述跳跃表的特征是具有

i

i

i阶引用的节点数量为具有

i

1

i-1

i1阶引用节点数量的

1

/

2

{\left.1\middle/2\right.}

1/2(其中

i

i

i为正整数且

i

log

2

n

i\le\lceil{\log_2n}\rceil

ilog2n),一般地跳跃表中该比例可以是

1

/

p

{\left.1\middle/p\right.}

1/p(其中

p

p

p是任意正整数),且跳跃表中任意节点所具有的最高阶数为

l

o

g

1

/

p

n

\lceil{log_{\left.1\middle/p\right.}n}\rceil

log1/pn,其中

n

n

n跳跃表当前所能容纳节点的最大数量

3. 跳跃表的几种阶数

关于跳跃表的引用阶数,有如下几个不同的定义:

  • 跳跃表最大引用阶数:一般用MaxLevel表示,决定了跳跃表节点可能拥有的最高引用阶数,该阶数确保在跳跃表中的节点个数不超过

    p

    M

    a

    x

    L

    e

    v

    e

    l

    p^{MaxLevel}

    pMaxLevel个时,跳跃表的相关操作效率不会大幅降低;

  • 节点最大引用阶数:一般用lvl表示,代表某具体节点所拥有的最高引用阶数;
  • 跳跃表当前引用阶数:一般用level表示,代表跳跃表所有的节点中,最高引用阶数的最大值。

一般而言,上述三个值之间的相对大小关系为lvl <= level <= MaxLevel

二、跳跃表分析

本节将开始介绍当跳跃表的每一个节点按照键的大小保存了键值对后,如何查找、插入和删除某键值对,其中:

  • 查找操作将返回和键相关的键值对,或当键不存在时抛出异常;
  • 插入操作将新增节点并保存键值对,当键已存在则替换原键对应的值;
  • 删除操作将删除和键相关的键值对,或当键不存在时抛出异常。

1. 节点描述

一般地,一个跳跃表的节点可以如下图表示,即存在:

  • 保存键值对的元素域;
  • 保存后续若干个节点引用的指针域:

【数据结构Python描述】跳跃表简介及使用跳跃表实现有序映射

2. 查找算法

当需要查找跳跃表中某一个键值对时,需要从头节点的最高阶引用开始往后遍历,在当前节点最高阶引用所指向的下一个节点的键第一次大于待搜索的键时,沿着当前节点的次阶引用继续搜索,如果假定待搜索的键值对在跳跃表中,则要么一直到沿着节点的1阶引用进行搜索后找到了期望的节点,或者在此之前就已经可以找到。

为了对上述流程进行更清晰的描述,下图描述了当在跳跃表中搜索键为19的键值对时的搜索路径:

【数据结构Python描述】跳跃表简介及使用跳跃表实现有序映射

针对上述分析,下面先给出跳跃表的搜索算法的伪代码:

SkipSearch(list, searched_key)
	x := list->header
	for i := list->level downto 1 do:
		while x->forward[i]->key < searched_key do:
			x := x->forward[i]
	/* 
	执行上述代码后,必定有:
	x->key < searched_key <= x->forward[1]->key 
	*/
	x := x->forward[1]
	if x->key = searched_key then:
		return x-> value
	else:
		return False

3. 阶数选择

在介绍插入算法之前,需要确定后续新插入节点所具有的最高引用阶数。如前所述,对于新插入的节点,其最高引用阶数满足以下两点:

  • 首先是小于

    l

    o

    g

    1

    /

    p

    n

    \lceil{log_{\left.1\middle/p\right.}n}\rceil

    log1/pn的正整数即可;

  • 其次是

    1

    /

    p

    {\left.1\middle/p\right.}

    1/p具有

    i

    i

    i阶引用的节点也具有

    i

    +

    1

    i+1

    i+1阶引用。

针对上述分析,下面给出生成节点最高引用阶数的伪代码:

randomLevel()
	lvl := 1
	// random()函数生成[0.0, 1.0)之间的随机浮点数
	while random() < p and lvl < MaxLevel do:
		lvl := lvl + 1
	return lvl

需要注意的是,对于一个跳跃表,任意节点所具有的最高阶数为

l

o

g

1

/

p

n

\lceil{log_{\left.1\middle/p\right.}n}\rceil

log1/pn,一般将其记为MaxLevel

4. 插入算法

为正确地向跳跃表中插入一个节点,需要:

  • 先查找到从左起最后一个满足特定条件的节点,即该节点元素域的键小于待插入节点元素域的键;
  • 然后将待插入节点置于上述节点之后,最后将待插入节点和其前后节点之间进行链接。

为更清晰地对跳跃表插入算法进行描述,下图给出了对跳跃表进行节点17进行插入前后的描述:

【数据结构Python描述】跳跃表简介及使用跳跃表实现有序映射

需要注意的是,为了能够在上述插入算法的第二步正确地进行节点链接,在第一步查找的过程中,需要使用数组变量cursor,使得cursor[i]保存至少具有

i

i

i阶引用的节点,且该节点不仅需要满足在待插入节点左侧,还需满足距离待插入节点距离最近。例如:

  • cursor[4]保存了元素域的键为6的节点引用;
  • cursor[3]保存了元素域的键为6的节点引用;
  • cursor[2]保存了元素域的键为9的节点引用;
  • cursor[1]保存了元素域的键为12的节点引用;

针对上述分析,下面先给出跳跃表的插入算法的伪代码:

SkipInsert(list, key2search, value2insert)
	cursor[1..MaxLevel]
	x := list->header
	for i := list->level downto 1 do:
		while x->forward[i]->key < key2search do:
			x := x->forward[i]
	/* 
	执行上述代码后,必定有:
	x->key < searched_key <= x->forward[1]->key 
	*/
		cursor[i] = x
	x := x->forward[1]
	if x->key = key2search then:
		x->value := value2insert
	else:
		lvl := randomLevel()
		if lvl > list->level then:
			for i := list->level + 1 to lvl do:
				cursor[i] := list->header
			list->level := lvl
		x := makeNode(lvl, key2search, value2insert)
		for i := 1 to list->level do:
			// 先将新节点和其右侧节点进行链接
			x->forward[i] := cursor[i]->forward[i]
			// 然后将新节点和其左侧节点进行链接
			cursor[i]->forward[i] := x

5. 删除算法

跳跃表的节点删除算法可以视为插入算法的逆操作,只需要:

  • 先遍历整个跳跃表找到从左起最后一个满足特定条件的节点,即该节点元素域的键小于待删除节点元素域的键;
  • 然后同样需要使用数组变量cursor,使得cursor[i]保存至少具有

    i

    i

    i阶引用的节点,且该节点不仅需要满足在待插入节点左侧,还需满足距离待插入节点距离最近;

  • 最后将待删除节点的左右节点进行直接链接以旁路待删除节点即可(如使用需程序员手动管理内存的语言实现如:C语言,还需要释放待删除节点的内存空间)。

下面是节点删除算法的伪代码:

SkipDelete(list, key2search)
	cursor[1..MaxLevel]
	x := list->header
	for i := list->level downto 1 do:
		while x->forward[i]->key < key2search do:
			x := x->forward[i]
		cursor[i] := x
	x := x->forward[1]
	if x->key == key2search then:
		for i := 1 to list->level do:
			if cursor[i]->forward[i] != x then:
				// 循环从i = 0开始,如从i = self.level开始则使用continue,但不如使用break相对高效
				break
			else:
				// 直接通过链接待删除节点的左右节点
				cursor[i]->forward[i] := x->forward[i]
		free(x)
		// 当跳跃表中存在头节点的某阶引用直接指向尾部哨兵节点时,跳跃表当前阶数需降低
		while list->level > 1 and list->header->forward[list->level] == NIL do:
			list->level := list->level - 1

三、跳跃表实现

1. 节点实现类_SkipNode

class _SkipNode:
    """
    表示跳跃表节点的类
    """

    def __init__(self, key, value, level):
        self.key = key
        self.value = value
        self.forward = [None] * (level + 1)

    def __str__(self):
        return '(' + str(self.key) + ', ' + str(self.value) + ')'

2. 初始化方法__init__

def __init__(self, max_level, portion):
    """
    创建一个空的跳跃表
    :param max_level: 跳跃表所有节点引用所可能达到的最高阶数
    :param portion: 具有i-1阶节点引用同时具有i阶引用的比例
    """
    self.MAX_LEVEL = max_level
    self.portion = portion
    self.header = self._make_node(self.MAX_LEVEL, None, None)
    self.level = 0  # 跳跃表当前引用阶数
    self.n = 0

3. 返回跳跃表节点个数方法__len__

def __len__(self):
    """
    返回跳跃表的节点个数
    """
    return self.n

4. 节点封装方法_make_node

def _make_node(self, lvl, key, value):
    """
    创建新的跳跃表节点
    :param lvl: 新节点所具有的最高引用阶数
    :param key: 键
    :param value: 值
    :return: 新节点的引用
    """
    node = _SkipNode(key, value, lvl)
    return node

5. 节点最高阶数生成方法_random_lvl

def _random_lvl(self):
    """
    生成新节点的最高引用阶数
    :return: 新节点的最高引用阶数
    """
    lvl = 0
    while random.random() < self.portion and lvl < self.MAX_LEVEL:
        lvl += 1
    return lvl

6. 跳跃表查找实用方法_utility_search

def _utility_search(self, key2search):
    """
    查找的实用非公有方法
    :param key2search: 待查找节点的键
    :return: 元组
    """
    cursor = [None] * (self.MAX_LEVEL + 1)
    current = self.header
    for i in range(self.level, -1, -1):
        # 当跳跃表为空时,current.forward[0]为None
        while current.forward[i] and current.forward[i].key < key2search:
            current = current.forward[i]
        cursor[i] = current
    current = current.forward[0]
    return current, cursor

7. 跳跃表节点查找方法skip_search

def skip_search(self, key2search):
    """
    在跳跃表中查找并返回键为key2search的键值对,当不存在时抛出KeyError异常
    """
    current, _ = self._utility_search(key2search)
    if current and current.key == key2search:
        return current
    else:
        raise KeyError('key {} does not exist!'.format(key2search))

8. 跳跃表节点插入方法skip_insert

def skip_insert(self, key2search, value2insert):
    """
    向跳跃表中插入由键值对封装后得到的节点
    """
    current, cursor = self._utility_search(key2search)
    if current and current.key == key2search:
        current.value = value2insert
    else:
        lvl = self._random_lvl()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                cursor[i] = self.header
            self.level = lvl
        node = self._make_node(lvl, key2search, value2insert)
        for i in range(lvl + 1):
            node.forward[i] = cursor[i].forward[i]
            cursor[i].forward[i] = node
        self.n += 1

9. 跳跃表节点删除方法skip_delete

def skip_delete(self, key2search):
    """
    从跳跃表中删除键为key2search的节点
    """
    current, cursor = self._utility_search(key2search)
    if current is not None and current.key == key2search:
        ret = current
        for i in range(self.level + 1):
            if cursor[i].forward[i] != current:
                break  # 循环从i = 0开始,如从i = self.level开始则使用continue,但不如使用break相对高效
            cursor[i].forward[i] = current.forward[i]
        while self.level > 0 and self.header.forward[self.level] is None:
            self.level -= 1
        self.n -= 1
        return ret

10. 跳跃表按节点阶数遍历方法skip_display

def skip_display(self):
    print("\n*****Skip List******")
    header = self.header
    for lvl in range(self.level + 1):
        print("Level {}: ".format(lvl), end=" ")
        node = header.forward[lvl]
        while node is not None:
            print(node.key, end=" ")
            node = node.forward[lvl]
        print('')

四、跳跃表效率分析

方法名称 时间复杂度
__len__

O

(

1

)

O(1)

O(1)

skip_search

O

(

l

o

g

n

)

O(logn)

O(logn)

skip_insert

O

(

l

o

g

n

)

O(logn)

O(logn)

skip_delete

O

(

l

o

g

n

)

O(logn)

O(logn)

五、跳跃表完整测试代码

import random


class _SkipNode:
    """
    表示跳跃表节点的类
    """

    def __init__(self, key, value, level):
        self.key = key
        self.value = value
        self.forward = [None] * (level + 1)

    def __str__(self):
        return '(' + str(self.key) + ', ' + str(self.value) + ')'


class SkipList:
    """
    跳跃表具体实现类
    """

    def __init__(self, max_level, portion):
        """
        创建一个空的跳跃表
        :param max_level: 跳跃表所有节点引用所可能达到的最高阶数
        :param portion: 具有i-1阶节点引用同时具有i阶引用的比例
        """
        self.MAX_LEVEL = max_level
        self.portion = portion
        self.header = self._make_node(self.MAX_LEVEL, None, None)
        self.level = 0  # 跳跃表当前引用阶数
        self.n = 0

    def __len__(self):
        """
        返回跳跃表的节点个数
        """
        return self.n

    def _make_node(self, lvl, key, value):
        """
        创建新的跳跃表节点
        :param lvl: 新节点所具有的最高引用阶数
        :param key: 键
        :param value: 值
        :return: 新节点的引用
        """
        node = _SkipNode(key, value, lvl)
        return node

    def _random_lvl(self):
        """
        生成新节点的最高引用阶数
        :return: 新节点的最高引用阶数
        """
        lvl = 0
        while random.random() < self.portion and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

    def _utility_search(self, key2search):
        """
        查找的实用非公有方法
        :param key2search: 待查找节点的键
        :return: 元组
        """
        cursor = [None] * (self.MAX_LEVEL + 1)
        current = self.header
        for i in range(self.level, -1, -1):
            # 当跳跃表为空时,current.forward[0]为None
            while current.forward[i] and current.forward[i].key < key2search:
                current = current.forward[i]
            cursor[i] = current
        current = current.forward[0]
        return current, cursor

    def skip_search(self, key2search):
        """
        在跳跃表中查找并返回键为key2search的键值对,当不存在时抛出KeyError异常
        """
        current, _ = self._utility_search(key2search)
        if current and current.key == key2search:
            return current
        else:
            raise KeyError('key {} does not exist!'.format(key2search))

    def skip_insert(self, key2search, value2insert):
        """
        向跳跃表中插入由键值对封装后得到的节点
        """
        current, cursor = self._utility_search(key2search)
        if current and current.key == key2search:
            current.value = value2insert
        else:
            lvl = self._random_lvl()
            if lvl > self.level:
                for i in range(self.level + 1, lvl + 1):
                    cursor[i] = self.header
                self.level = lvl
            node = self._make_node(lvl, key2search, value2insert)
            for i in range(lvl + 1):
                node.forward[i] = cursor[i].forward[i]
                cursor[i].forward[i] = node
            self.n += 1

    def skip_delete(self, key2search):
        """
        从跳跃表中删除键为key2search的节点
        """
        current, cursor = self._utility_search(key2search)
        if current is not None and current.key == key2search:
            ret = current
            for i in range(self.level + 1):
                if cursor[i].forward[i] != current:
                    break  # 循环从i = 0开始,如从i = self.level开始则使用continue,但不如使用break相对高效
                cursor[i].forward[i] = current.forward[i]
            while self.level > 0 and self.header.forward[self.level] is None:
                self.level -= 1
            self.n -= 1
            return ret

    def skip_display(self):
        print("\n*****Skip List******")
        header = self.header
        for lvl in range(self.level + 1):
            print("Level {}: ".format(lvl), end=" ")
            node = header.forward[lvl]
            while node is not None:
                print(node.key, end=" ")
                node = node.forward[lvl]
            print('')


if __name__ == '__main__':
    skip_list = SkipList(10, 0.5)
    skip_list.skip_insert(3, 5)
    skip_list.skip_insert(12, 9)
    skip_list.skip_insert(26, 7)
    skip_list.skip_insert(7, 13)
    skip_list.skip_insert(21, 3)
    skip_list.skip_insert(25, 4)
    skip_list.skip_insert(6, 6)
    skip_list.skip_insert(17, 8)
    skip_list.skip_insert(19, 10)
    skip_list.skip_insert(9, 14)
    print(len(skip_list))  # 10
    print(skip_list.skip_search(3))  # (3, 5)
    print(skip_list.skip_delete(19))  # (19, 10)
    print(len(skip_list))  # 9
    skip_list.skip_display()

*****Skip List******
Level 0: 3 6 7 9 12 17 21 25 26
Level 1: 6 12 17 21
Level 2: 17
Level 3: 17

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。