数据结构之跳表

栏目: 数据库 · 发布时间: 5年前

内容简介:本篇是数据结构与算法之美学习笔记上一篇据结构之二分查找中我们知道二分查找底层依赖的是数组随机访问的特性,所以只能使用数组实现,不能再链表中实现。那链表可不可以支持类似的二分查找呢?答案当然可是可以,就是给链表加上索引,这种数据结构称为跳表。

本篇是数据结构与算法之美学习笔记

上一篇据结构之二分查找中我们知道二分查找底层依赖的是数组随机访问的特性,所以只能使用数组实现,不能再链表中实现。

那链表可不可以支持类似的二分查找呢?答案当然可是可以,就是给链表加上索引,这种数据结构称为跳表。

对于一个单链表来说,即使它存储的数据是有序的,如果我们要在其中查找某个数据,也只能从头到尾的遍历建表,这样的查找效率很低。

那怎么优化呢,可以对链表建立索引,比如每两个节点提取一个节点到上一级,抽出来的那一集叫索引或者索引层。如下图:

数据结构之跳表

如果我们想要寻找某一个节点,比如8,可以先在索引层遍历,当遍历到7的时候,我们发现下一个节点是9,那么要查找的节点就在这两个节点之间,然后通过down指针下降到原始链表的这一层继续遍历。这时候就能很快找到8节点了。

现在只是构建了一级索引,如果在构建几级索引,查询速度会更快。特别是当数据量很大的时候。

如果链表中有n个及诶单,会有几级索引呢?

假如每两个节点抽出一个作为上一级的索引节点,那第一级的索引节点的个数就是n/2,第二级的及诶单个数就是n/4,第三级就是8/n,以此类推,当第k级索引的节点个数就是第k-1级索引个数的1/2,那第k级索引节点的个数就是n/2的k次方

通过加索引就通过链表实现了类似二分查找的功能,当然索引多了,索引也会占据一定的空间,假如有n个节点,我们额外需要接近n个节点的存储空间,这就是用空间换时间的思想。

我们也可以根据实际情况,来更改抽取节点的间隔,比如每隔3个或者5个等抽取一个节点。

在实际的软件开发中,由于原始链表中很可能存储很大的对象,而索引只需要存储关键值和指针,不需要存储对象,多以当对象比索引节点大很多的时候,索引所占的额外空间就可以忽略了。

跳表不仅支持查找操作,还支持动态的插入、删除操作,速度都很快。

在链表中,插入和删除操作效率是很高的,但是,如果我们往一个有序的链表中插入一条数据,并且保证其继续有序就麻烦了,需要遍历找到要插入的位置,如果使用跳表,把遍历查找这一步简化了,相对的插入的效率也就高了。

动态更改索引:

如果我们不断的往跳表中插入数据,如果不更新索引,就有可能造成某两个结点之间的数据非常多的情况。所以如果链表中结点多了,索引也要相应的增加一些,避免复杂度退化。

那怎么避免呢,跳表示通过随机函数来维护其平衡性

当我们往跳表中插入数据的时候,我们可以选择同时将这个数据插入到部分索引层中,通过一个随机函数,来决定将这个节点插入到哪一集索引中。比如随机函数生成了k值,就把它添加到第一级到第k级这k级索引中。

跳表的一种实现方式:

package com.chs.androiddailytext.datastructure;

import java.util.Random;

public class SkipList {

  private static final int MAX_LEVEL = 16;

  private int levelCount = 1;

  private Node head = new Node();  // 带头链表

  private Random r = new Random();

  public Node find(int value) {
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      return p.forwards[0];
    } else {
      return null;
    }
  }

  public void insert(int value) {
    int level = randomLevel();
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    Node update[] = new Node[level];
    for (int i = 0; i < level; ++i) {
      update[i] = head;
    }

    // 记录update[]中小于insert值的每一层的最大值
    Node p = head;
    for (int i = level - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;// 在搜索路径中使用更新保存节点
    }

    // 在搜索路径节点中,下一个节点成为新的节点forwords(next)
    for (int i = 0; i < level; ++i) {
      newNode.forwards[i] = update[i].forwards[i];
      update[i].forwards[i] = newNode;
    }

    // 更新节点
    if (levelCount < level) levelCount = level;
  }

  public void delete(int value) {
    Node[] update = new Node[levelCount];
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      for (int i = levelCount - 1; i >= 0; --i) {
        if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
          update[i].forwards[i] = update[i].forwards[i].forwards[i];
        }
      }
    }
  }

  // 随机 level 次,如果是奇数层数 +1,防止伪随机
 private int randomLevel() {
    int level = 1;
    for (int i = 1; i < MAX_LEVEL; ++i) {
      if (r.nextInt() % 2 == 1) {
        level++;
      }
    }

    return level;
  }

  public class Node {
    private int data = -1;
    private Node forwards[] = new Node[MAX_LEVEL];
    private int maxLevel = 0;

    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();
      builder.append("{ data: ");
      builder.append(data);
      builder.append("; levels: ");
      builder.append(maxLevel);
      builder.append(" }");

      return builder.toString();
    }
  }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

MySQL性能调优与架构设计

MySQL性能调优与架构设计

简朝阳 / 2009-6 / 59.80元

《MySQL性能调优与架构设计》以 MySQL 数据库的基础及维护为切入点,重点介绍了 MySQL 数据库应用系统的性能调优,以及高可用可扩展的架构设计。 全书共分3篇,基础篇介绍了MySQL软件的基础知识、架构组成、存储引擎、安全管理及基本的备份恢复知识。性能优化篇从影响 MySQL 数据库应用系统性能的因素开始,针对性地对各个影响因素进行调优分析。如 MySQL Schema 设计的技巧......一起来看看 《MySQL性能调优与架构设计》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

SHA 加密
SHA 加密

SHA 加密工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换