什么是動態數據結構：動態數據結構是支持動態的更新操作，里面存儲的數據是時刻在變化的，通俗一點講，它不僅僅支持查詢，還支持刪除、插入數據。而且，這些操作都非常高效。如果不高效，也就算不上是有效的動態數據結構了。所以，紅黑樹算一個，支持動態的插入、刪除、查找，而且效率都很高。

 劃重點：學習數據結構和算法，要學習它的由來、特性、適用的場景以及它能解決的問題。

總結1

散列表：插入刪除查找都是O(1), 是最常用的，但其缺點是不能順序遍歷以及擴容縮容的性能損耗。適用于那些不需要順序遍歷，數據更新不那么頻繁的。

跳表：插入刪除查找都是O(logn), 并且能順序遍歷。缺點是空間復雜度O(n)。適用于不那么在意內存空間的，其順序遍歷和區間查找非常方便。

紅黑樹：插入刪除查找都是O(logn), 中序遍歷即是順序遍歷，穩定。缺點是難以實現，去查找不方便。其實跳表更佳，但紅黑樹已經用于很多地方了。 

總結2

**基本數據結構：**

1.數組：連續的內存空間，支持按下標隨機訪問O(1)，刪除和查找設計數據搬移效率是O(n) 試用場景：數據規模較小，不經常變動。

缺點：對于內存連續性要求高。插入刪除操作效率低。

2.鏈表：查詢效率不高O(n)，插入和刪除效率高O(1)，并且內存申請可以不連續，適用場景是插入和刪除多于查詢操作。

缺點：查找效率低，實際上刪除之前先要查找，所以實際刪除效率也不高。

**動態數據結構：**

1.散列表：可以說是利用數組和鏈表兩個基本數據結構設計了一個高效的動態數據結構。利用了數組的隨機訪問特性，用于滿足根據某個屬性來隨機訪問元素�；�于key查找效率很高O(1).同時借助鏈表進行散列沖突解決方案，刪除和插入操作效率也可以接近O(1).試用場景：海量數據隨機訪問、防止重復、緩存等。

缺點：需要設計合理的散列函數，并且要考慮散列沖突和動態擴容。

2.跳表：盡管散列表效率很高，但是散列表是無序的，跳表效率和散列表類似，并且支持區間序列的輸出（因為基于鏈表）。使用場景：對有序元素的快速查找、插入和刪除。

缺點：比較占用內存。

3.紅黑樹：紅黑樹是平衡二叉查找樹的一種近似實現。紅黑樹和跳表類似，但是實現方式有所差異。紅黑樹存在的價值是，它可以實現比較高效的查找，刪除和插入。雖然相比高度平衡的AVL樹效率有所下降，但是紅黑樹不用耗費太多精力維護平衡。相比跳表，紅黑樹除了內存占用較小，其他性能并不比跳表更優。但由于歷史原因，紅黑樹使用的更廣泛。

缺點：實現比較復雜。

總結3

動態數據結構還包括以下幾種：

1.鏈表：

優勢：高效地數據插入、刪除。

缺點：隨機查找元素效率較低。

適用場景：適用于順序訪問數據，數據維護較頻繁的場合。

2.哈希鏈表

優勢：高效地數據插入、刪除、隨機查找元素。

缺點：需要設計一個好的散列函數，把元素均勻分散到散列表中。

適用場景：適用于在海量數據中隨機訪問數據的場合。

3.跳表

優勢：高效地查找、插入、刪除數據。

缺點：需要額外的空間來構建索引鏈表

適用場景：適用于需要高效查找數據的場合。

4.二叉查找樹

優勢：高效地查找、插入、刪除數據，實現簡單。

缺點：需要動態地維護左右子樹的高度平衡，否則數據查找會退化成鏈表的順序查找。

適用場景：適用于需要高效查找數據的場合。