[数据结构与算法]红黑树和哈希表（小菜一碟）

哈希表（看视频很容易了解）

转载：带你快速理解 哈希表（散列表）的运作原理_哔哩哔哩_bilibili

红黑树（这篇文章图案不错）

转载：C++ 数据结构 红黑树 图文详解_FARO_Z的博客-CSDN博客_c++红黑树

前言：

?以前没认真研究哈希表和红黑树，以为哈希表和红黑树很nb,很难。今天刚开始看，红黑树看一会儿没看大懂，然后看哈希表，看文章一阵头疼，什么乱七八糟的文章写一推数学公式。看完哈希表视频，突然一阵懵逼，这不是以前数据结构和考研的时候东西，什么线性探测法。看完视频就都回忆起来。然后回去看红黑树，再仔细看一下，想起来当初考研的时候，也学过什么左旋右旋、但是只是没有什么红黑标记而已，跟以前平衡二叉树很像，还有数据插入，就是从根节点比大小，然后插入叶子节点，最后进行旋转。

重点：

1.hashmap是平均O(1),map是平均O(lnN)的

2.模运算（取余）

哈希表

?哈希表扩容机制

存储的数组超过70%的时候，再创建一个以前数组大小两倍的数组，将数据搬到新的数组中，和vector扩容机制一样。

哈希表的使用方法

主要用于查找：比如传入一个数A查找是否在数组中，将数据通过存储数据的哈希算法进行模运算，查找数组的位置是否存在数据，如果存在数据但不是A,则按哈希算法规则，比如查找下一个位置是否是A,直到遇到空数据（说明不存在）或者找到自身。

红黑树：

红黑树插入法原理是：右孩子一定大于父节点，左孩子一定小于父节点。

?红黑树的特质有5个：

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是NIL节点，即NULL）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

左旋和右旋的原理：
如果是右子树需要旋转，则进行左旋

如果是左子树需要旋转，则进行右旋

旋转原理是：

?

红黑树的使用方法

直接对节点进行比较大小进行查找。