Skip List
這種數(shù)據(jù)結(jié)構(gòu)翻譯成中文贸宏，大家一般叫它跳表颓哮，非常直譯磕仅，其實(shí)我接觸這種數(shù)據(jù)結(jié)構(gòu)比較早珊豹，但是看很多技術(shù)分享的時(shí)候一直聽(tīng)到有人說(shuō)跳表，跳表榕订，但我始終沒(méi)有把它和skip list聯(lián)系起來(lái)店茶。
Skip List也是鏈表的一種變形，同樣是在node結(jié)構(gòu)上做文章劫恒，它的出發(fā)點(diǎn)非常簡(jiǎn)單直接贩幻，因?yàn)橐粋€(gè)有序數(shù)組我們支持二分查找，那么一個(gè)有序鏈表我們是不是也能支持類(lèi)似的快速查找呢两嘴？于是跳表就出現(xiàn)了丛楚，它是典型的空間換時(shí)間的一個(gè)具體實(shí)現(xiàn)，下圖引用自Skip List
每個(gè)節(jié)點(diǎn)都有一個(gè)指針數(shù)組指向不同的節(jié)點(diǎn)憔辫，在每一層上看都是一個(gè)節(jié)點(diǎn)有序的鏈表鸯檬，其實(shí)也有一些實(shí)現(xiàn)是基于unrolled list的，就在每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)有序數(shù)組螺垢，但是那種方式牽涉到每個(gè)節(jié)點(diǎn)需要維護(hù)多少個(gè)值的問(wèn)題喧务，也是需要在實(shí)際的環(huán)境中去調(diào)優(yōu)的，說(shuō)遠(yuǎn)了枉圃，還是回到跳表實(shí)現(xiàn)的本身功茴，我們需要注意的是一般跳表的實(shí)現(xiàn)在查找的時(shí)候都不能保證二分查找，要完美支持二分查找的話(huà)孽亲，跳表的實(shí)現(xiàn)復(fù)雜度相當(dāng)大坎穿，而且結(jié)構(gòu)的重整非常頻繁，反而得不償失返劲，一般跳表插入元素的時(shí)候會(huì)有個(gè)隨機(jī)數(shù)來(lái)表示這個(gè)節(jié)點(diǎn)需要擴(kuò)展到多高的高度玲昧，大于這個(gè)高度的那層鏈表不必包含這個(gè)新增的節(jié)點(diǎn)，低于這個(gè)高度的鏈表必須包含這個(gè)節(jié)點(diǎn)篮绿，在插入節(jié)點(diǎn)后孵延，具體要更新哪些節(jié)點(diǎn)的next數(shù)組的哪些位置的值可以在查找插入位置的過(guò)程中把它記下來(lái)，這些需要更新的節(jié)點(diǎn)數(shù)量不會(huì)超過(guò)跳表節(jié)點(diǎn)的最高高度亲配，
template < typename T >
struct SkipListNode{
? ? SkipListNode** next; //dynamic allocate
? ? int length; //next array length and also is node level
? ? T data
}
以上尘应。
