跳表是一種隨機(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):