为了解决这样的问题，能不能找一种结构能够兼顾搜索和插入删除的效率呢？这时候红黑树便申请出战了 。
红黑树具有五个特性：
- 每个结点要么是红的要么是黑的 。
- 根结点是黑的 。
- 每个叶结点（叶结点即指树尾端NIL指针或结点）都是黑的 。
- 如果一个结点是红的，那么它的两个儿子都是黑的 。
- 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点 。
文章插图
红黑树通过将结点进行红黑着色，使得原本高度平衡的树结构被稍微打乱，平衡程度降低 。红黑树不追求完全平衡，只要求达到部分平衡 。这是一种折中的方案，大大提高了结点删除和插入的效率 。C++中的STL就常用到红黑树作为底层的数据结构 。
红黑树VS平衡二叉树
文章插图
除了上面所提及的树结构，还有许多广泛应用在数据库、磁盘存储等场景下的树结构 。比如B树、B+树等 。这里就先不介绍了诶，下次在讲述相关存储原理的时候将会着重介绍 。（其实是因为懒）
堆了解完二叉树，再来理解堆就不是什么难事了 。堆通常是一个可以被看做一棵树的数组对象 。堆的具体实现一般不通过指针域，而是通过构建一个一维数组与二叉树的父子结点进行对应，因此堆总是一颗完全二叉树 。
对于任意一个父节点的序号n来说（这里n从0算），它的子节点的序号一定是2n+1，2n+2，因此可以直接用数组来表示一个堆 。
不仅如此，堆还有一个性质：堆中某个节点的值总是不大于或不小于其父节点的值 。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆 。
文章插图
堆常用来实现优先队列，在面试中经常考的问题都是与排序有关，比如堆排序、topK问题等 。由于堆的根节点是序列中最大或者最小值，因而可以在建堆以及重建堆的过程中，筛选出数据序列中的极值，从而达到排序或者挑选topK值的目的 。
散列表散列表也叫哈希表，是一种通过键值对直接访问数据的机构 。在初中，我们就学过一种能够将一个x值通过一个函数获得对应的一个y值的操作，叫做映射 。散列表的实现原理正是映射的原理，通过设定的一个关键字和一个映射函数，就可以直接获得访问数据的地址，实现O(1)的数据访问效率 。在映射的过程中，事先设定的函数就是一个映射表，也可以称作散列函数或者哈希函数 。
文章插图
散列表的实现最关键的就是散列函数的定义和选择 。一般常用的有以下几种散列函数：
直接寻址法：取关键字或关键字的某个线性函数值为散列地址 。确定好散列函数之后，通过某个key值的确会得到一个唯一的value地址 。但是却会出现一些特殊情况 。即通过不同的key值可能会访问到同一个地址，这个现象称之为冲突 。
数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址 。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址 。
平方取中法：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址 。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址 。
取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合 。
除留取余法：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址 。这种方式也可以在用过其他方法后再使用 。该函数对 m 的选择很重要，一般取素数或者直接用 n 。
冲突在发生之后，当在对不同的key值进行操作时会使得造成相同地址的数据发生覆盖或者丢失，是非常危险的 。所以在设计散列表往往还需要采用冲突解决的办法 。
常用的冲突处理方式有很多，常用的包括以下几种：
开放地址法（也叫开放寻址法）：实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖 。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址 。如果超过最大长度，则可以对总长度取余 。这里移动的地址是产生冲突时的增列序量 。
推荐阅读
- 发酵茶和熟茶的区别,弄懂普洱茶生茶和熟茶的区别
- 一文带你彻底理解Linux的各种终端类型及概念
- 同样是面粉，8607和1355区别很大！建议弄懂后再买不踩坑，涨知识
- 都是牡蛎，海蛎子和生蚝有何区别？弄懂再买不吃亏
- 先吃饭还是先吃药？人民日报用八张图告诉你！
- 都是牛奶，“袋装”和“盒装”有啥不同？差别很大，建议弄懂再买
- 一张图引发的深思：你了解过架构设计体系吗？熬夜整理这份文章
- 未来会彻底摆脱体力劳动吗？
- 9张图看完LV全系列139款包包
- 弄懂这两点，情侣吵架非但不伤感情，还会很恩爱
