【029-week2】算法训练营第二周学习总结

[maxyzli]

哈希表

哈希表使用hash function來對輸入的數據分配index到哈希表對應的槽中。假設有一個哈希表的size是100，而我們輸入的數據是從0～99，我們要把輸入數據儲存到哈希表中。理論上來說，該哈希表插入和查找操作的時間複雜度都是O(1)。

二叉树

二叉樹遵循右子樹大於根節點，左子樹小於根節點的原則進行數據的插入和保存。如果這個樹的平衡的，那麼，對於每個元素的插入和查找操作的時間複雜度是O(log(n))，n是樹的節點個數，log(n)通常是樹的深度。當然，對於不平衡的情況，那就需要更複雜的數據結構的樹（紅黑樹等）進行處理。

特色

• 二叉樹不會有衝突（collision），這意味著我們能夠保證二叉樹的插入和查找操作一直都是O(log(n))的時間複雜度。
• 二叉樹的空間佔用跟輸入的輸入數據一致。所以我們不需要為二叉樹預先分配固定的空間。所以，你也不需要預先知道輸入數據的size。
• 所有的元素在樹中是排序好的。

二叉搜索树

特色

• 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
• 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
• 任意節點的左、右子樹也分別為二元搜尋樹；
• 沒有鍵值相等的節點。