一交汤、跳表的前傳
1雏赦、一個有序鏈表搜索、添加芙扎、刪除的平均時間復(fù)雜度是多少（重要星岗，竟然理解還是不到位）？
- O(n)
image.png
2戒洼、能否利用二分搜索優(yōu)化有序鏈表俏橘，將搜索、添加圈浇、刪除的平均時間復(fù)雜度降低至O(logn)寥掐？
- 不行
- 鏈表沒有想數(shù)據(jù)那樣的
高效隨機訪問（O(1)時間復(fù)雜度）禀横，所以不能像有序數(shù)組那樣直接進行二分搜索優(yōu)化
3费奸、那有沒有其他辦法讓有序鏈表搜素、添加军掂、刪除的平均時間復(fù)雜度降低至 O(logn)蠕搜？
- 有 怎茫，使用跳表（SkipList）
image.png
二收壕、跳表介紹
1妓灌、跳表的英文名是什么轨蛤？在 xxx 基礎(chǔ)上，增加了 xxx 功能虫埂？
- 跳表(SkipList)：在
有序鏈表的基礎(chǔ)上增加了“跳躍”的功能
2祥山、跳表的設(shè)計初衷是什么？對比平衡樹有什么優(yōu)點嗎掉伏？
-
初衷：為了取代平衡樹（比如紅黑樹） -
對比平衡樹優(yōu)點：①跳表的實現(xiàn)和維護會更加簡單②跳表的搜索缝呕、刪除、添加的平均時間復(fù)雜度是 O(logn)
image.png
3斧散、使用跳表優(yōu)化鏈表的思想供常？
image.png
- 如上圖所示，如果要訪問 25 要怎么走鸡捐？
- 如上圖所示栈暇，如果要訪問 18 要怎么走？
4箍镜、跳表的添加和刪除思路（把下面這張圖記牢了源祈，跳表的精髓也就掌握了）？
image.png
