温故而知新--多层索引链表-跳表

/ 默认分类 / 0 条评论 / 908浏览

数据结构

多层索引链表-跳表

一.简单介绍

链表的单单插入操作其实是高效的o(1)，但是在插入之前我们需要寻找到指定的位置，这个操作需要进行O(n)的遍历操作，但是如果我们借助二分查找的思想，那么查找的效率就会大大提高变为O(logn)，这也就是我们今天要说的跳表！

二.跳表的基本概念

跳表（Skip List）是一个非常有趣的数据结构。它在许多方面类似于平衡树，但在实现上更加简单。

跳表由多层组成，每一层都是一个【有序】的链表。 第一层包含所有的元素，而每一高层都是前一层元素的一个子集。 每个节点都包含一个值和若干指向下一个节点的指针，其中最顶层的节点指针可跨越更多节点。

当我们熟悉跳表后就会发现，所谓的向下的指针，其实就是层级数组的索引递增和递减操作，所谓的每一层的指向下一个元素的指针，其实就是节点的【下一个元素数组】。

ps.上面我说的下一个元素是一个形容词，描述的后面的数组。

三.详细描述

下面我将带你从0到1，依次从跳表的初始化到向跳表中插入元素这整个过程来了解跳表。下面涉及到的一些概念，可以先不用纠结，后面会详细介绍，主要先对跳表的查找有个认识。

3.1 初始化跳表

3.2 插入第一个元素

插入第一个元素，值为3，随机高度为2。

我们需要先寻找现有索引路径。

然后执行插入

3.2 插入第二个元素

插入第二个元素，值为5，随机高度为1

同样的，先寻找现有的随机路径。

然后插入数据

3.3 插入第三个元素

插入第三个元素，值为7，随机高度为2

先寻找现有的随机路径。

然后插入数据

四.数据结构和代码详解

跳表的节点的数据结构我们可以表示为数据属性和下一个节点的指针属性。只不过，这里我们的指针属性是一个数组，数组中索引n的元素就是表示当前节点在跳表第n层的下一个元素，数组的索引的变化也就是上下指针的移动,这句话特别重要，弄清楚这句话跳表基本上就搞明白一大半了。

下面我们来看实际的代码：

golang
package main

import (
	"errors"
	"fmt"
)

const (
	maxLevel    = 4
	probability = 0.5
	maxInt      = 0x7fffffff
)

type Node struct {
	value    int
	forwards []*Node
}

type MySkipList struct {
	head         *Node
	currentLevel int
	updateNodes  []*Node
}

func NewMySkipList() *MySkipList {
	return &MySkipList{
		head:         getNewNode(-maxInt),
		currentLevel: 0,
		updateNodes:  make([]*Node, maxLevel),
	}
}

func (s *MySkipList) initialize() {
	s.currentLevel = 0
	s.head = getNewNode(-maxInt)
	s.updateNodes = make([]*Node, maxLevel)
	for i := 0; i < maxLevel; i++ {
		s.updateNodes[i] = s.head
	}
}

func getNewNode(value int) *Node {
	node := &Node{
		value:    value,
		forwards: make([]*Node, maxLevel),
	}
	return node
}

func (s *MySkipList) insert(value int) {
	level := s.randomLevel()
	if level > s.currentLevel {
		s.currentLevel = level
	}
	s.findAndPrepareUpdateNodes(value)
	newNode := getNewNode(value)
	for i := 0; i <= level; i++ {
		newNode.forwards[i] = s.updateNodes[i].forwards[i]
		s.updateNodes[i].forwards[i] = newNode
	}
}

func (s *MySkipList) findAndPrepareUpdateNodes(value int) *Node {
	temp := s.head
	for i := s.currentLevel; i >= 0; i-- {
		for temp.forwards[i] != nil && temp.forwards[i].value < value {
			temp = temp.forwards[i]
		}
		s.updateNodes[i] = temp
	}
	return temp
}

var times = 0

func (s *MySkipList) randomLevel() int {
	if times == 0 {
		times++
		return 2
	} else if times == 1 {
		times++
		return 1
	} else if times == 2 {
		times++
		return 2
	}
	panic(errors.New("随机层数生成异常"))
	//rand.Seed(time.Now().UnixNano())
	//level := 0
	//for rand.Float64() < probability && level < maxLevel-1 {
	//	level++
	//}
	//return level
}

func (s *MySkipList) print(level int) {
	pointer := s.head.forwards[level]
	for pointer != nil {
		fmt.Printf("%d ", pointer.value)
		pointer = pointer.forwards[level]
	}
	fmt.Println()
}

func (s *MySkipList) printAllLevels() {
	for i := s.currentLevel; i >= 0; i-- {
		fmt.Printf("Level %d: ", i)
		s.print(i)
	}
	fmt.Println()
}

func main() {
	skipList := NewMySkipList()
	elements := []int{3, 5, 7}
	for _, element := range elements {
		skipList.insert(element)
	}
	skipList.printAllLevels()
}
python
import random

MAX_LEVEL = 4
PROBABILITY = 0.5
MAX_INT = 0x7fffffff

class Node:
    def __init__(self, value):
        self.value = value
        self.forwards = [None] * MAX_LEVEL

class MySkipList:

    def __init__(self):
        self.head = self.get_new_node(-MAX_INT)
        self.current_level = 0
        self.times = 0
        self.update_nodes = [self.head] * MAX_LEVEL

    def get_new_node(self, value):
        return Node(value)

    def insert(self, value):
        level = self.random_level()
        if level > self.current_level:
            self.current_level = level
        self.find_and_prepare_update_nodes(value)
        new_node = self.get_new_node(value)
        for i in range(level + 1):
            new_node.forwards[i] = self.update_nodes[i].forwards[i]
            self.update_nodes[i].forwards[i] = new_node

    def find_and_prepare_update_nodes(self, value):
        temp = self.head
        for i in range(self.current_level, -1, -1):
            while temp.forwards[i] and temp.forwards[i].value < value:
                temp = temp.forwards[i]
            self.update_nodes[i] = temp

    def random_level(self):
        if self.times == 0:
            self.times = self.times+1
            return 2
        elif self.times == 1:
            self.times = self.times+1
            return 1
        elif self.times == 2:
            times = self.times + 1
            return 2
        raise Exception("生成随机层数异常")
        # level = 0
        # while random.random() < PROBABILITY and level < MAX_LEVEL - 1:
        #     level += 1
        # return level

    def print_level(self, level):
        pointer = self.head.forwards[level]
        while pointer:
            print(pointer.value, end=" ")
            pointer = pointer.forwards[level]
        print()

    def print_all_levels(self):
        for i in range(self.current_level, -1, -1):
            print(f"Level {i}: ", end="")
            self.print_level(i)
        print()

if __name__ == "__main__":
    skip_list = MySkipList()
    elements = [3, 5, 7]
    for element in elements:
        skip_list.insert(element)
    skip_list.print_all_levels()
java
public class SkipListV2 {
    private static final int MAX_LEVEL = 4;
    private static final float P = 0.5f;
    private static final int MAX_INT = 0x7fffffff;

    class Node {
        int val;
        //当前节点的每一个层级的下一个节点元素组成的数组
        //按照二分查找的原理或者按照跳表的基本思想，可以知道，下一个节点元素最多也就是层级数，也就是这个节点在每一层都有；
        Node[] forwards = new Node[MAX_LEVEL];
    }

    private Node head;
    private int curLevel;
    private Node[] upData;

    public SkipListV2() {
        init();
    }

    /**
     * 初始化
     */
    private void init() {
        curLevel = 0;
        head = getNewNode(-MAX_INT);
        //初始化查询路径数组，该数组是每次跳表查询时候的路径，最大就是层级数
        upData = new Node[MAX_LEVEL];
        for (int i = 0; i < MAX_LEVEL; i++) {
            upData[i] = new Node();
        }
    }


    private Node getNewNode(int value) {
        Node node = new Node();
        //新建的节点的next节点数组（next节点数组是当前节点在每一层的下一个节点元素的组合，
        // 数组的索引位置就是层位置，第0层就是最下面的包含所有元素的层）的元素都是null
        for (int i = 0; i < MAX_LEVEL; i++) {
            node.forwards[i] = null;
        }
        node.val = value;
        return node;
    }

    /**
     * 插入元素
     *
     * @param value 值
     */
    public void insert(int value) throws Exception {
        //得到本次插入的随机层数，表示当前元素需要插入的层数是多少（从下到上）
        int lev = randomLevel();
        //如果本次插入的层数大于当前跳表的总层数，那么就把当前跳表的总层数更新为本次的层数
        if (lev > curLevel) {
            curLevel = lev;
        }
        //寻找每层最接近的元素，也就是为上面的查找路径数组赋值
        find(value);
        //创建一个新节点
        Node newNode = getNewNode(value);
        //插入操作
        for (int i = 0; i <= lev; i++) {
            newNode.forwards[i] = upData[i].forwards[i];
            upData[i].forwards[i] = newNode;
        }
    }

    /**
     * 查找最接近val的元素
     *
     * @param value 值
     */
    private Node find(int value) {
        //从头结点开始
        Node tem = head;
        //从最上层开始
        for (int i = curLevel; i >= 0; i--) {
            while (tem.forwards[i] != null && tem.forwards[i].val < value) {
                tem = tem.forwards[i];
            }
            //记录搜索过程中各级走过的最大节点位置
            upData[i] = tem;
        }
        return tem;
    }

    int times = 0;
    /**
     * 随机产生插入元素高度
     *
     * @return 高度
     */
    private int randomLevel() throws Exception {
        if(times == 0){
            times++;
            return 2;
        } else if (times == 1) {
            times++;
            return 1;
        }else if (times == 2) {
            times++;
            return 2;
        }
        throw new Exception("error");
    }

    public void print(int i) {
        // 遍历
        SkipListV2.Node p = head.forwards[i];
        if (p == null) {
            return;
        }
        while (p != null) {
            System.out.printf("%d  ", p.val);
            p = p.forwards[i];
        }
        System.out.printf("\n");
    }

    /**
     * 遍历所有层
     */
    public void printAll() {
        for (int i = curLevel; i >= 0; i--) {
            System.out.printf("curLevel %d:  ", i);
            print(i);
        }
        System.out.println();
    }

    public static void main(String[] args) throws Exception {
        SkipListV2 skipList = new SkipListV2();
        List<Integer> list = Arrays.asList(3, 5, 7);
        for (Integer element : list) {
            skipList.insert(element);
        }
        skipList.printAll();
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2024/05/03 22:28