什麼樣的數據結構支持快速插入，刪除和搜索

我覺得這個必須存在，但我無法想象它。是否有一個數據結構，可以保存一個排序的值列表並快速搜索（可能是log（N）時間，就像數組一樣），還支持在log（N）或常量時間插入和刪除元素？什麼樣的數據結構支持快速插入，刪除和搜索

2013-07-15 Bi Rico

你沒有說哪種語言，但排序後的鏈表使用二進制搜索算法（也用於插入和刪除）完成所有這些操作。 – kevinsa5

@ kevinsa5，我的理解是，鏈表不支持二分查找，因爲它不支持恆定時間查找，只有O（N）查找。如果我錯了，請糾正我。這也是一個語言不可知的問題，我想這樣的數據結構應該可以用任何合理的語言來實現。 –

二叉樹，然後呢？不包含時間，但O（log（n））。 – kevinsa5

這幾乎是平衡二叉搜索樹的描述，它按排序順序存儲元素，允許O（log n）插入，刪除和查找，並允許O（n）遍歷所有元素。

有很多方法可以建立均衡的BST - 有紅/黑樹，AVL樹，替罪羊樹，張角樹，AA樹，treaps，（a，b）樹等等。你的問題。其中，斜紋樹可能是最容易編碼的，其次是AA樹和AVL樹。

希望這會有所幫助！

2013-07-15 06:15:05 templatetypedef

回答