动态数据结构的动态是什么意思？

动态是指在运行时该数据结构所占的内存会扩大或缩小。

数组是一种静态的数据结构，在创建时内存大小已经确定，不管有没有插入数据。而链表是动态的数据结构，插入数据 alloc 内存，删除数据 release 内存。

栈、队列、散列表、跳表、树都是抽象的数据结构，它们在内存中存在的形式都要依赖于数组或者链表。

如果用链表实现，很明显它们是动态的数据结构；如果用数组实现，那么在扩容的时候会创建更大内存的数组，原数组被废弃，从抽象角度看，它们仍旧是动态的。

红黑树的节点颜色，是如何确定的，如何知道在新增一个节点时，该节点是什么颜色？

从红黑树需要满足的四个要求来看：
1. 根节点为黑色
2. 所有叶子节点为黑色，且不存储数据
3. 相邻两个节点不能都为红色
4. 从某节点到其所有叶子节点的路径中，黑色节点数相同

从这四点要求，好像我一根树全是黑色，也是满足其定义的。这里用红黑两色区分各节点，意义是啥？

谢谢老师

**基本数据结构：**

1.数组：连续的内存空间，支持按下标随机访问O(1)，删除和查找设计数据搬移效率是O(n) 试用场景：数据规模较小，不经常变动。

缺点：对于内存连续性要求高。插入删除操作效率低。

2.链表：查询效率不高O(n)，插入和删除效率高O(1)，并且内存申请可以不连续，适用场景是插入和删除多于查询操作。

缺点：查找效率低，实际上删除之前先要查找，所以实际删除效率也不高。

**动态数据结构：**

1.散列表：可以说是利用数组和链表两个基本数据结构设计了一个高效的动态数据结构。利用了数组的随机访问特性，用于满足根据某个属性来随机访问元素。基于key查找效率很高O(1).同时借助链表进行散列冲突解决方案，删除和插入操作效率也可以接近O(1).试用场景：海量数据随机访问、防止重复、缓存等。

缺点：需要设计合理的散列函数，并且要考虑散列冲突和动态扩容。

2.跳表：尽管散列表效率很高，但是散列表是无序的，跳表效率和散列表类似，并且支持区间序列的输出（因为基于链表）。使用场景：对有序元素的快速查找、插入和删除。

缺点：比较占用内存。

3.红黑树：红黑树是平衡二叉查找树的一种近似实现。红黑树和跳表类似，但是实现方式有所差异。红黑树存在的价值是，它可以实现比较高效的查找，删除和插入。虽然相比高度平衡的AVL树效率有所下降，但是红黑树不用耗费太多精力维护平衡。相比跳表，红黑树除了内存占用较小，其他性能并不比跳表更优。但由于历史原因，红黑树使用的更广泛。

缺点：实现比较复杂。

动态数据结构还包括以下几种：
1.链表：
优势：高效地数据插入、删除。
缺点：随机查找元素效率较低。
适用场景：适用于顺序访问数据，数据维护较频繁的场合。

2.哈希链表
优势：高效地数据插入、删除、随机查找元素。
缺点：需要设计一个好的散列函数，把元素均匀分散到散列表中。
适用场景：适用于在海量数据中随机访问数据的场合。

3.跳表
优势：高效地查找、插入、删除数据。
缺点：需要额外的空间来构建索引链表
适用场景：适用于需要高效查找数据的场合。

4.二叉查找树
优势：高效地查找、插入、删除数据，实现简单。
缺点：需要动态地维护左右子树的高度平衡，否则数据查找会退化成链表的顺序查找。
适用场景：适用于需要高效查找数据的场合。