不同的字典實現

Question

我在算法分析和後準備考試我已經學會了C＃和以不同的方式我感到困惑的優勢/劣勢實施字典..

因此，這裏是我的問題：

使用無序數組而不是總是有序數組實現字典的原因是什麼？

重新實現Dicitonary使用總是有序數組而不是無序數組？

使用二進制搜索樹而不是總是排序的數組實現字典的原因？

Answer 1

如果您使用無序數組，您可以將項目粘貼到末尾或將數組複製到新數組中，並在原始填滿時粘貼項目。 O（1）或O（n）根據這兩種情況插入，但O（n）做任何查找。

對於有序數組，您可以根據其內容（通過二進制搜索或其他酷搜索）更快速地搜索它，但它增加了插入成本，因爲每次都必須在數組中移動它們你插入它，除非你只是按排序順序添加東西，這種情況甚至可能是最壞的情況，對每個元素都是O（n）。

使用二叉搜索樹，您可以根據您在O（log n）時間內分叉樹的任何內容輕鬆地找到您要尋找的任何節點，但這隻能在平衡二叉樹上實現。用一個不平衡的二叉搜索樹（基本上是一個鏈表），你可能會得到O（n）的最差情況。然而，對於平衡樹，插入可能會更加昂貴，因爲它需要重新組織通常爲O（n log n）的樹，但是O又是最糟糕的情況，大多數平衡二叉搜索樹可以更快速地完成大部分插入操作。