問下有序數組，有什麼好的數據結構可以替代？

02-02

插入/刪除一個數要移動後面的數，
要求是數據還是有序的，查找、插入、刪除的速度可以提升
遍歷的話，比如 int[100] , 就是遍歷一遍index應該很快。遍歷速度也要求~

跳躍表

簡單的實現用平衡樹比較好。

如果要進一步優化性能可以基於數據的分布特點來使用哈希表。

B+樹嘛，最合適了，葉子節點是一個鏈表，從root到葉子節點的中間節點就是Index，查詢和刪除的速度取決於樹的高度，插入比較麻煩，因為有分裂的問題，但是也比平移所有數組下標快，資料庫索引的基礎結構就是醬紫，幾千萬數據量也嗖嗖的。

圖片來自百度百科

是個語言都有map可以用吧？總之要排序的也只能要麼數組要麼平衡樹

這不是splay么？。。。

有序的平衡樹，以二叉平衡樹為例，查找，插入/刪除都是logN級別，查找比鏈錶快一些，維護有序的成本比數組少一些。

各語言里實現一般是有序的map(非hash實現的map)

數據量小點就是平衡樹吧 avl樹紅黑樹

查詢刪除新增時間複雜度logn

遍歷的話就是遍歷整棵樹 o(n)

數據量大的話 b+樹 b*樹

一維數組還是二維還是n維？

如果是寫演算法自然是指針操作的鏈表比較方便而且效率高

1. 空間消耗允許可以使用跳躍表(skiplist), 具有較好的穩定性

2. 否則平衡二叉樹

3. 再複雜點 hash_map+linked list結合體, 同時滿足增刪,查找速度要求

bbst

線索avl

紅黑樹，avl樹，跳躍表？

回答map的有一個問題就是樹遍歷會有大量的cache miss

一般來說用map就可以了

怕cache miss影響效率可以用B樹減少訪存次數（新出的語言已經注意到這個問題了，Rust的map就是用B樹實現的，雖然多數語言的map都還是各種平衡二叉樹）

問下 有序數組 ，有什麼好的數據結構可以替代？