鏈表算法

跳表是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)邮弹,目前開(kāi)源軟件Redis和LevelDB都有用到它累舷,它的效率和紅黑樹以及AVL樹不相上下:

考慮一個(gè)有序表:

從該有序表中搜索元素< 23, 43, 59 >,需要比較的次數(shù)分別為< 2, 4, 6 >,總共比較的次數(shù)為2 + 4 + 6 = 12次。有沒(méi)有優(yōu)化的算法嗎?鏈表是有序的,但不能使用二分查找听怕。類似二叉搜索樹,我們把一些節(jié)點(diǎn)提取出來(lái)虑绵,作為索引尿瞭。得到如下結(jié)構(gòu):

這里我們把< 14, 34, 50, 72 >提取出來(lái)作為一級(jí)索引,這樣搜索的時(shí)候就可以減少比較次數(shù)了翅睛。

我們還可以再?gòu)囊患?jí)索引提取一些元素出來(lái)声搁,作為二級(jí)索引,變成如下結(jié)構(gòu):

跳表結(jié)構(gòu):

-1表示INT_MIN,鏈表的最小值

1表示INT_MAX,鏈表的最大值捕发。

跳表具有如下性質(zhì):

(1)由很多層結(jié)構(gòu)組成

(2)每一層都是一個(gè)有序的鏈表

(3)最底層(Level 1)的鏈表包含所有元素

(4)如果一個(gè)元素出現(xiàn)在Level(x)的鏈表中酥艳,則它在Level(x-n)的鏈表中也都會(huì)出現(xiàn)。

(5)每個(gè)節(jié)點(diǎn)包含兩個(gè)指針爬骤,一個(gè)指向下一個(gè)元素充石,一個(gè)指向下面一層的元素

跳表的搜索

例子:查找元素117

(1)比較21,比21大霞玄,往后面找

(2)比較37,比37大骤铃,比鏈表最大值小,從37的下面一層開(kāi)始找

(3)比較71,比71大坷剧,比鏈表最大值小惰爬,從71的下面一層開(kāi)始找

(4)比較85,比85大惫企,從后面找

(5)比較117撕瞧,等于117,找到了節(jié)點(diǎn)狞尔。


跳表的插入

先確定該元素要占據(jù)的層數(shù)K(采用丟硬幣的方式丛版,這完全是隨機(jī)的)

然后在Level 1 ...

Level K各個(gè)層的鏈表都插入元素。

例子:插入119偏序,K = 2

如果K大于鏈表的層數(shù)页畦,則要添加新的層。

例子:插入119研儒,K = 4

丟硬幣決定K

插入元素的時(shí)候豫缨,元素所占有的層數(shù)完全是隨機(jī)的独令,通過(guò)一下隨機(jī)算法產(chǎn)生:

相當(dāng)與做一次丟硬幣的實(shí)驗(yàn),如果遇到正面好芭,繼續(xù)丟燃箭,遇到反面,則停止舍败,

用實(shí)驗(yàn)中丟硬幣的次數(shù)K作為元素占有的層數(shù)遍膜。顯然隨機(jī)變量K滿足參數(shù)為p = 1/2的幾何分布,

K的期望值E[K] = 1/p = 2.就是說(shuō)瓤湘,各個(gè)元素的層數(shù),期望值是2層恩尾。


跳表的刪除

在各個(gè)層中找到包含x的節(jié)點(diǎn)弛说,使用標(biāo)準(zhǔn)的delete from list方法刪除該節(jié)點(diǎn)。

例子:刪除71

java實(shí)現(xiàn):

http://www.cnblogs.com/acfox/p/3688607.html

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末翰意,一起剝皮案震驚了整個(gè)濱河市木人,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌冀偶,老刑警劉巖醒第,帶你破解...
    沈念sama閱讀 222,946評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異进鸠,居然都是意外死亡稠曼,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門客年,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)霞幅,“玉大人,你說(shuō)我怎么就攤上這事量瓜∷究遥” “怎么了?”我有些...
    開(kāi)封第一講書人閱讀 169,716評(píng)論 0 364
  • 文/不壞的土叔 我叫張陵绍傲,是天一觀的道長(zhǎng)扔傅。 經(jīng)常有香客問(wèn)我,道長(zhǎng)烫饼,這世上最難降的妖魔是什么猎塞? 我笑而不...
    開(kāi)封第一講書人閱讀 60,222評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮杠纵,結(jié)果婚禮上邢享,老公的妹妹穿的比我還像新娘。我一直安慰自己淡诗,他們只是感情好骇塘,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布伊履。 她就那樣靜靜地躺著,像睡著了一般款违。 火紅的嫁衣襯著肌膚如雪唐瀑。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書人閱讀 52,807評(píng)論 1 314
  • 那天插爹,我揣著相機(jī)與錄音哄辣,去河邊找鬼。 笑死赠尾,一個(gè)胖子當(dāng)著我的面吹牛力穗,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播气嫁,決...
    沈念sama閱讀 41,235評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼当窗,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了寸宵?” 一聲冷哼從身側(cè)響起崖面,我...
    開(kāi)封第一講書人閱讀 40,189評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎梯影,沒(méi)想到半個(gè)月后巫员,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,712評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡甲棍,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評(píng)論 3 343
  • 正文 我和宋清朗相戀三年简识,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片感猛。...
    茶點(diǎn)故事閱讀 40,926評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡财异,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出唱遭,到底是詐尸還是另有隱情戳寸,我是刑警寧澤,帶...
    沈念sama閱讀 36,580評(píng)論 5 351
  • 正文 年R本政府宣布拷泽,位于F島的核電站疫鹊,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏司致。R本人自食惡果不足惜拆吆,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望脂矫。 院中可真熱鬧枣耀,春花似錦、人聲如沸庭再。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 32,750評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至颅围,卻和暖如春伟葫,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背院促。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 33,867評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工筏养, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人常拓。 一個(gè)月前我還...
    沈念sama閱讀 49,368評(píng)論 3 379
  • 正文 我出身青樓渐溶,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親弄抬。 傳聞我的和親對(duì)象是個(gè)殘疾皇子茎辐,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容