数据结构(一)--- 跳跃表 (2)

 

数据结构(一)--- 跳跃表

5、总结

在数据规模比较小时,跳跃表形成后可能不是理想的跳跃表结构,但是当数据量增大,结构越接近理想的跳跃表结构。

bw指针不是所有的语言的实现都存在,这个是参考了Redis的跳跃表实现,笔者自己加上去的。

跳跃表不同于树结构,如红黑树等,它不需要花费过多的精力进行平衡算法,这也是跳跃表的性能优越的一个方面。

跳跃表结构是拿空间换时间的一种结构,尽管空间占用不是很大。

查询、删除,平均时间复杂度都是O(logn),而插入的平均时间复杂度也是O(logn) 因为涉及到增层操作,所以这里需要注意不是O(n).

 

 此博客为笔者参考网络上各类文章总结性书写,原创手打,如有错误欢迎指正。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpgwfw.html