設置的複雜性::插入

我已經讀過插入操作集只需要log（n）時間。這怎麼可能？設置的複雜性::插入

要插入，首先我們在新元素必須坐的排序數組中找到位置。使用二進制搜索它需要log（n）。然後爲了插入該位置，所有繼承它的元素都應該向右移動一個位置。又過了n次。

我的疑問是基於我的理解，set是作爲數組實現的，元素按排序順序存儲。如果我的理解錯誤，請糾正我。

2012-10-08 bibbsey

你假設'std :: set'被實現爲一個有序數組。爲什麼？ –

來自cppreference：*集合通常實現爲紅黑樹* – chris

@KonradRudolph：現在我只知道集合是用紅黑樹實現的。感謝Chris – bibbsey

std::set通常實現爲紅黑二叉搜索樹。因爲樹保持平衡，所以在該數據結構上的插入具有O（log（n））複雜度的最壞情況。

2012-10-08 06:39:09 cdhowie

不完全：修改可能需要重新平衡，這又是一次O（log n）操作。 –

使用紅黑樹，即使考慮到重新平衡，插入應該具有O（log（n））的最壞情況。 – cdhowie

是的，當然，我沒有反對。但是你說修改樹是O（1）。 *那是錯的。 –

回答