herb

我要靠谱→hello world!
随笔 - 14, 文章 - 0, 评论 - 0, 引用 - 0
数据加载中……

2012年4月8日

跳表使用

     摘要: 目前经常使用的平衡数据结构有:B树,红黑树,AVL树,Splay Tree, Treep等。

想象一下,给你一张草稿纸,一只笔,一个编辑器,你能立即实现一颗红黑树,或者AVL树

出来吗? 很难吧,这需要时间,要考虑很多细节,要参考一堆算法与数据结构之类的树,

还要参考网上的代码,相当麻烦。

用跳表吧,跳表是一种随机化的数据结构,目前开源软件 Redis 和 LevelDB 都有用到它,

它的效率和红黑树以及 AVL 树不相上下,但跳表的原理相当简单,只要你能熟练操作链表,

就能轻松实现一个 SkipList。  阅读全文

posted @ 2012-04-08 17:58 herb 阅读(1404) | 评论 (0)编辑 收藏